Back to help contents.

Contents

Overview

Menus

Create Mode

Solve Mode

Algorithms

CSP Specification

Overview

This applet is designed to let you create such a problem and solve it using and experimenting with a variety of stochastic local search algorithms.

Menus

File Menu

• Create New CSP - Discard the current CSP and start creating from an empty CSP.
• Load Sample CSP - Load a problem from a set of sample problems.
• Load From File - Load a problem from the local disk.
• Load From URL - Load a problem by specifying a URL where the CSP is located.
• Save CSP - Save the CSP to the local disk.
• Print - Prints the canvas as displayed in Solve mode.
• Quit - Close the SLS Applet window.

Edit Menu

• Undo - lets you undo the last operation if applicable. This is only available in "Create" mode.
• View/Edit Text Representation - Opens a window containing the text representation of the CSP. The text can be edited in create mode. The CSP can be updated from the text representation window by clicking the "Update CSP" button. With this feature, a CSP can be indirectly loaded from a  locally saved text file by pasting the text representation of a CSP to the text representation window.
• View Current Text Representation - in solve mode, this allows you to export the current state of the CSP (with domains restricted to the current assignments).

View Menu

• Font Size - Set the font size used in the CSP.
• Line Width - Set the width of lines displayed in the CSP.
• Autoscale - Adjust the CSP to be fitted in canvas.
• Pan/Zoom - Select which mode to be in. Then when right-clicking and dragging the mouse on canvas, you can pan or zoom the CSP on the canvas.
• Arrange Constraints - This will adjust the CSP so that each constraint is arranged directly between its corresponding variables.
• Enable Anti-Aliasing - Enables/disables anti-aliasing.
• Show Message Panel - Show or hide the message prompts above the main canvas.
• Show Button Text - Show or hide the text on the buttons in the toolbar.
• Show Buttons - Show or hide the removable toolbar buttons.

Hill Options Menu

• Auto Solve Speed - Set how fast AutoSolve takes place.
• Algorithm Options... - Opens the Algorithm Options dialog allowing you to specify the Stochastic Local Search algorithm and modify parameters.
• Batch Run Options... - Opens the Batch Run Options dialog allowing you to specify number of attempts in a batch run and the max steps in each attempt.

Help Menu

• Legend for Nodes/Edges - Opens a dialog with a legend for describing what the graph shapes/colours mean.

• Help - Opens this web page, which provides general help on the Decision Tree Learning applet.

• Tutorials - Opens up the Tutorial web page. Tutorials walk through how to use the applet.

• About CIspace - Provides brief information about the CIspace project.

• About this Applet - Identifies the applet version and names of developers.

Create Mode

Create a Variable

• To create a variable, press the "Create Variable" button and click on the white canvas at the location you want the variable to appear. This will bring up a dialog box where you can enter the name, domain type, and domain values of the variable represented by the variable you're creating.
• The variable name can be almost anything you want as long as it has no spaces, and no "<", ">". It's best if the variable name is capitalized and starts with an alphabetic character.
• The default domain type is boolean, and a boolean domain initially consists of {true, false}. To get a different domain type, simply select the appropriate radio button next to "Domain Type:" of the type you want the variable to be. The other domain types are initially empty.
• When you've selected a domain type you can enter domain values in the text field next to "Domain:". String values can be almost anything; it's best if they have no spaces and contain no commas. Integers must be integers for instance; 1,2,35,10001. Boolean values must be either "true" or "false". An example of how to enter domain values appropriately for the specified domain type is below the text field.
• Click "OK" when you are done and the new variable will appear.

Creating a Constraint

• There are four actions to initiate the creation of a constraint.
  • With the "Create Constraint" button depressed:
    • click on a blank space in the canvas to create a constraint with no variables
    • click on a variable and then click on a blank space in the canvas to create a constraint with one variable
    • click on a variable and then click on another variable to create a binary constraint.
  • With the "Add Variable to Constraint" button depressed:
    • click on an existing constraint and then on an existing variable or vice versa to add that variable to the constraint, allowing for k-ary constraints.
• Once it has been initiated, the variable dialog will open with Custom constraint selected. You can modify the truth table of the custom constraint by clicking on the table and selecting the appropriate true/false values. You can label custom constraints by typing the name that you want to have appear on the canvas in the text area next to "Custom Name."
• You can select a built-in constraint type by selecting one from the pull down list of available constraint types for this constraint's variables next to "Constraint Type:".
• Click "OK" when finished, and the new constraint (with its label) will appear.
  

Selecting/Modifying/Removing Variables and Constraints

• You can select and move variables and constraints by pressing the "Select" button and clicking and dragging an entity.
• You can delete an entity by pressing "Delete" and clicking on variables and constraints. In this manner you can also remove a variable from a constraint by clicking on an edge connecting a variable to a constraint.
• To modify variable and constraint properties, simply click on them when the "Set Properties" button is selected, and an appropriate dialog will appear.

Editing the Text Representation

• Sometimes the graphical user interface isn't efficient for creating the CSP you want. By selecting "View/Edit Text Representation" from the edit menu, you can directly edit the text representation of the CSP. This is useful if you have many identical domains with lots of elements and you'd like to avoid retyping all the domain elements for each Variable. It's also useful if you want to modify a variable after you've created it. Simply make the changes you want, and then click the "Update" button to load the new CSP.

Creating a New CSP

• To delete the current CSP and start with a blank canvas, select "Create New CSP" in the "File" menu.
• Loading CSPs:
  • A set of sample CSPs is available for loading from "Load Sample CSP" in the "File" menu.
  • A CSP can be loaded from a URL from "Open Location" in the "File" menu.
  • A CSP can be loaded from a saved file on the local disk by selecting "Open CSP" in the "File" menu.
• Saving CSPs:
  • The current CSP can be saved to a file on the local disk by selecting "Save" in the "File" menu.
• Loading and Saving CSPs by Cut-and-Paste:
  • The user can save the text representation of the current CSP by cut-and-paste from the Text Representation Frame (the frame is displayed by selecting the "View/Edit Text Representation" item in the "Edit" menu).  In UNIX-based systems, you select the text, and then middle-click on a window where you want the text to be stored, such as a text-editing program. In Windows-based systems, you can use Ctrl-C to copy and Ctrl-V to paste.
  • To load a previously saved CSP, just paste the text representation into the "View/Edit Text Representation" window, and click the "Update CSP" button.

Solve Mode

Manually Stepping Through the algorithm:

• First, click the "Initialize" button to assign one value to each variable from its domain. Green arcs between variables connected by a constraint mean that constraint is satisfied with the given variable assignment. Red arcs mean the constraint is inconsistent.
• To run through the chosen SLS algorithm manually, click the "Step" button. This automatically selects an arc on the queue, according to the chosen SLS algorithm, and makes it consistent by choosing another value assignment for the variable from its domain.
• For some algorithms, clicking on the "Fine Step" button allows the user to step through the algorithm and see the applet select a variable and the change the domain independently.
• Alternatively you can select new assignments by clicking on a variable and clicking on the new value from the domain of the variable in the dialog that appears.

Auto Solve:

• Again, the CSP needs to be initialized first by clicking on the "Initialize" button.
• Clicking on the "Auto Solve" button will start Auto Solving. It continues until all constraints are satisfied or the termination step number is reached. It can also be stopped by clicking on the "Stop" button. To adjust the speed of Auto Solve, select the appropriate check box under "Auto Solve Speed" under the "Hill Options" menu.

The Trace window:

• After the "Initialize" button is pressed, click the "Show Trace" button and a "Trace" window will appear showing the initial variable-value assignment and showing the number of remaining conflicts. As you solve the CSP with any of the above methods, the "Trace" window will show value assignments and remaining conflicts with each step. With the trace window you can also step back through the variable-value assignments or select a variable-value assignment from the trace by clicking on a row and then set the CSP back to that assignment.

Plotting the Attempt:

• The change at each step can be visualized as a plot of the number of unsatisfied constraints to steps taken.
• To show the plot press the "Show Plot" button.

Batch Run:

• A batch run performs a set of attempts to solve the current CSP with the current algorithm. Successes are plotted versus the number of steps needed in a "runtime distribution".
• To start a batch run click the "Batch Run" button.
• To view statistics on currently completed runs click on the appropriate plot button in the legend of the plot or click on the "Statistics & Settings" button.
• Other batch run options can be set by opening the "Batch Run" dialog box by clicking on "Batch Run Options..." under the "Hill Options" menu.

Algorithms

This applet implements several Stochastic Local Search algorithms for solving CSPs. The algorithm to use while solving the CSP can be selected and the appropriate options for that algorithm set by opening the "Algorithm Options" dialog box by clicking on "Algorithm Options..." under the "Hill Options" menu. The implemented algorithms are:

Random Sampling

At each step this algorithm randomly creates a new solution. For each variable a new value is randomly chosen.

Random Walk

At each step this algorithm randomly chooses a new solution from the set of neighbouring solutions. The set of neighbouring solutions is defined in this applet as the solutions where a single variable has a different value.

Options: You may choose between a one or two stage heuristic. In the first case, the variable and value are chosen together; in the second case, the variable is chosen first and then the value.

Greedy Descent

At each step this algorithm chooses a value which improves the graph.

Options: You may choose between a one or two stage heuristic. In a one stage heuristic the variable and value are chosen together. In the two stage heuristic the variable is chosen first and then the value. The variable with the greatest number of conflicts in its edges is chosen and then the value which resolves the highest number of conflicts is chosen from this variable's set of values.

Greedy Descent with the Min Conflict Heuristic

The Min Conflict Heuristic is one of the first heuristics used for constraint satisfaction problems. (Minton et Al, 1992). It chooses a variable randomly from the set of variables with conflicts (red edges). The value which results in the fewest conflicts is chosen from the possible assignments for this variable. This heuristic is almost identical to Greedy Descent with Random Walk with a two stage heuristic choosing any red node 100% and best value 100%. The only difference is the MCH may return to the previous assignment.

Greedy Descent with Random Walk

At each step this algorithm probabilistically decides whether or not to take a greedy step (change to the best neighbour) or to take a random walk (change to any neighbour)

Options: You may choose between a one or two stage heuristic. In the first case, the variable and value are chosen together; in the second case, the variable is chosen first and then the value. To increase the random walk percentage increase the "random ..." values.

Greedy Descent with Random Restart

This algorithm proceeds like the Greedy Descent algorithm but resets the variables to a new random solution at regular intervals.

Options: Reset Graph specifies the number of steps between random resets of the graph.

Greedy Descent with all Options

This algorithm provides all the options associated with Random Resets, Random Walk and Greedy Descent enabling free experimentation with these algorithms.

Simulated Annealing

Simulated annealing performs random guesses in the set of neighbours. If the temperature is very high it accepts most of the guesses irrespective of how much "better" they are than the current value. The temperature is decreased according to a schedule. As the temperature decreases the chance of accepting a guess which does not improve the solution decreases.

Options:

• Starting Temperature: the initial temperature at which the search begins. A higher temperature means that more guesses will be accepted. A temperature of 0 means that only guesses which decrease the cost function will be accepted.
• Boltzman Constant (K) : A constant which is multiplied by the temperature when the probability of accepting a guess must be determined. P(accepting guess) = exp( -dE/ KT ) where dE is a measure of how much this guess would improve the solution.
• Descent Function: Determines how the temperature is decreased.
• Constant: it stays at the Starting Temperature.
• Linear: it decreases by the value of the Descent Rate each adjustment. New T = Old T - Descent Rate
• Logarithmic: it decreases by a factor of the Descent Rate each adjustment. New T = Old T x (1 - Descent Rate)
• Descent Rate: Determines how large each adjustment is. Is used differently by different descent functions.
• Maintain Temperature: Determines how many guesses the temperature will remain constant before it is adjusted.

CSP Specification

Domain Types:

• Boolean - A domain consisting of only "true" or "false" values, there can be an unlimited number of either.
• Integer - A domain consisting of only integer values, ...-3,-2,-1,0,1,2,3...
• String - A domain consisting of a set of strings

Constraint Types:

Constraints consist of a set of variables and a relation which determines a truth value for each combination of elements from the set of variables. Constraints can have any number of variables but the relations are undetermined if a variable's domain is empty. Some constraint types are restricted in the variable types they accept. In all cases the variables can be reordered via the constraint dialog.

• Custom - User decides the truth value for each variable assignment. Any combination of variables are accepted.
• False - This constraint is always false. Any combination of Variables are accepted. The complement can be taken and is equivalent to the True constraint.
• True - This constraint is always true. Any combination of Variables are accepted. The complement can be taken and is equivalent to the False constraint.

Boolean Constraints, accept only boolean variables. In all cases complement can be taken.

• And - Logical And, all of the variables are true.
• Or - Logical Or, one of the variables is true.
• XOr - Exactly one of the variables is true.
• Implies (->) - Implication of first variable with the conjunction (And) of the remaining variables. True unless the first variable is false and all remaining variables are true.

Number Constraints, accept only integer variables. In all cases complement can be taken.

• Equal (=) - true if all variables are equal.
• LessThan (<) - true if each variable is strictly less than all variables following it in the constraint.
• GreaterThan (>) - true if each variable is strictly greater than all variables following it in the constraint.
• Queens - Implements Queens constraint as in the n-Queens problem. This problem tries to put as nQueens on a chessboard such that in one move no Queen can take another Queen (for each queen there is no queen along its diagonals or in the same row or column. User specifies the number of rows separating adjacent variables in the constraint. The integer value of each variable specifies the column.

String Constraints, accept only strings. In all cases complement can be taken.

• LengthEqual - true if the length of all string elements in question have the same number of characters.
• LengthLess - true if each variable has strictly fewer characters than all variables following it in the constraint.
• LengthGreat - true if each variable has strictly more characters than all variables following it in the constraint.
• Crossword - Takes two arguments, X and Y, from the user. It is true if the Xth character of the first variable is equal to the Yth character of all other variables.