Back to help contents.
Contents
Overview
A constraint satisfaction problem, or CSP, is a problem which can be expressed
as a set of variables, each with a particular domain, and a set of constraint
relations between variables. A solution to a CSP is an assignment of a
unique value to each variable such that all the of the constraint relations
are satisfied.
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 rightclicking 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 AntiAliasing  Enables/disables antialiasing.
 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 kary 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 builtin 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 CutandPaste:
 The user can save the text representation of the current CSP by cutandpaste from the Text Representation Frame
(the frame is displayed by selecting the "View/Edit Text Representation"
item in the "Edit" menu). In UNIXbased systems, you select the text,
and then middleclick on a window where you want the text to be stored,
such as a textediting program. In Windowsbased systems, you can use CtrlC
to copy and CtrlV 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 variablevalue 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 variablevalue assignments or select a variablevalue
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:
Domains are discrete sets of elements of the following 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 nQueens 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.
