JConstraints Wiki
Java Framework to implement solutions to solve constraints problems
Brought to you by:
julioheitor
Menu
▾
▴
Home
How to use JConstraints to solve your constraint satisfaction problems
JConstraints is a Java framework strongly based on the constraint satisfaction paradigm. There are three main concepts that describes any constraint problem:
1) Variables: the variables represents the "agents" that compound the constraint problem. For example, in the N-queens problem, each queen could be a variable in the problem. Each variable has to be assigned a value that don't harm any constraint attached to it.
2) Values: the values that can be assigned to the variables. The set of values that a variable can be assigned is called domain.
3) Constraints: the restrictions that has to be satisfied in order to find a solution to the problem.
Based on these three main concepts, JConstraints provides a set of interfaces/classes that enables developers to model any kind of constraint problem easily:
jconstraints.elements.Variable: In the majority of the problems, the developer won't have do inherit from
this class. Just set it's values domain and name in order to use it in any constraint problem.jconstraints.elements.Value: This interface has to be implemented in order to represent any kind of value
that the problem demands. Just override the method equals(Value value) to allow the framework to differ one
value from the others.jconstraints.elements.Constraint: This abstract class has to be inherited in order to represent a constraint specific to the problem. Just implement the method satisfies(), allowing the framework to know when the constraint is satisfied.
jconstraints.elements.ComposedVariable: Class that extends from jconstraints.elements.Variable to represent a composed variable. Usually useful for constraints with order higher than 2 (N-ary constraints).
jconstraints.elements.ComposedValue: Class that extends from jconstraints.elements.Value to represent
a value composed by other values. Useful when handling N-ary constraints. Store this kind of values inside a ComposedVariable.
After modeling the problem using the above classes/interfaces, the developer is able to use the classes below to initiate the problem resolution:
jconstraints.elements.CSPSolver: The solver that will find a solution to the problem.
jconstraints.elements.CSPAlgorithm: An Enum that provides an array of algorithms to be chosen by the developer that will solve the problem. Just set the chosen algorithm in the CSPSolver using the method setAlgorithm(). At the end of this tutorial, there is a list of algorthms that can be used to solve constraints problems.
jconstraints.elements.CSPProblem: Class that represent a problem to be solved. The problem is passed to the CSPSolver before initiate the resolution process.
jconstraints.elements.PerformanceReport: Class that stores the performance report of the last resolution process. This class provides information about the number of backtracks performed, backjumps realized, the number of tries that a local search does and etc.
So, after this massive amount of information, let's show how to use the framework by examples.
Example 1: N-Queens problem
The N-Queen problem is described as a set of queens in a board and each of then has to be placed in a manner that no queen attacks each other (no queen in the same line, column and diagonal).
First, create a class that implements the Value interface in order to represent the position of the queen on the board:
:::java
public class QueenValue implements Value{
private int colValue;
private int lineValue;
public int getColValue() {
return colValue;
}
public void setColValue(int colValue) {
this.colValue = colValue;
}
public int getLineValue() {
return lineValue;
}
public void setLineValue(int lineValue) {
this.lineValue = lineValue;
}
@Override
public boolean equals(Value value) {
QueenValue v = (QueenValue) value;
if(colValue == v.getColValue() && lineValue == v.getLineValue()){
return true;
}
return false;
}
public String toString(){
return "line "+lineValue+" column "+colValue;
}
}
Then, extends the abstract class Constraint to model the queen constraint (no queen can attack each other):
:::java
public class QueenConstraint extends Constraint {
private Variable var1;
private Variable var2;
public QueenConstraint(ArrayList<Variable> variables) {
super(variables);
var1 = variables.get(0);
var2 = variables.get(1);
}
@Override
public boolean satisfies() {
if (!var1.hasAssignedValue() || !var2.hasAssignedValue()) {
return true;
}
if (var1 != var2) {
QueenValue value1 = (QueenValue) var1.getAssignedValue();
QueenValue value2 = (QueenValue) var2.getAssignedValue();
if (value1.getColValue() == value2.getColValue()
|| value1.getLineValue() == value2.getLineValue()) {
return false;
}
//Is it at the same diagonal?
if (Math.abs(value1.getColValue() - value2.getColValue()) == Math
.abs(value1.getLineValue() - value2.getLineValue())) {
return false;
}
}
return true;
}
}
The last step is to create the variables, the domain of each variable and set a relation between the variables using the constraints (in the N-Queen problem, each variable has constraints connecting each of the others):
:::java
public static void main(String args[]) {
//Number of queens
int QUEEN_NUMBER = 9;
ArrayList<Variable> variables = new ArrayList<Variable>();
ArrayList<Constraint> constraints = new ArrayList<Constraint>();
// Creates a domain for each variable
ArrayList<Value> domain = null;
for (int i = 0; i < QUEEN_NUMBER; i++) {
if (domain == null) {
domain = new ArrayList<Value>();
for (int line = 0; line < QUEEN_NUMBER; line++) {
for (int col = 0; col < QUEEN_NUMBER; col++) {
QueenValue value = new QueenValue();
value.setColValue(col);
value.setLineValue(line);
domain.add(value);
}
}
}
//Creates a variable
Variable variable = new Variable(domain);
variable.setName("Queen " + (i + 1));
variables.add(variable);
}
// Create the constraints between each variable
for (Variable var1 : variables) {
for (Variable var2 : variables) {
if (var1 != var2) {
ArrayList<Variable> vars = new ArrayList<Variable>();
vars.add(var1);
vars.add(var2);
QueenConstraint constraint = new QueenConstraint(vars);
constraints.add(constraint);
}
}
}
//Creates the solver, set an algorithm and run the resolution process.
CSPSolver solver = new CSPSolver();
solver.setAlgorithm(CSPAlgorithm.BACKTRACKING);
variables = solver.solve(new CSProblem(variables, constraints));
if (variables == null) {
System.out.println("No solution!");
} else {
System.out.println("Used algorithm: "
+ solver.getReport().getAlgorithmName());
for (Variable var : variables) {
System.out.println(var.getName() + " line: "
+ ((QueenValue) var.getAssignedValue()).getLineValue()
+ " column: "
+ ((QueenValue) var.getAssignedValue()).getColValue());
}
// Print the performance report
System.out.println("");
System.out.println("Number of Backtracks:"
+ solver.getReport().getBackTracksNumber());
System.out.println("Total time: "
+ solver.getReport().getTotalTime() + " seconds");
}
}
To create an unary constraint is also simple. For example, in the N-Queen problem, one could add a constraint saying that no queen can be in the first slot of the board ([0,0] position). First, create a class representing the unary constraint:
:::java
public class QueenUnaryConstraint extends Constraint{
private Variable var;
public QueenUnaryConstraint(ArrayList<Variable> variables) {
super(variables);
var = variables.get(0);
}
@Override
public boolean satisfies() {
// No queen can be in the (0,0) position
if (((QueenValue) var.getAssignedValue()).getColValue() == 0
&& ((QueenValue) var.getAssignedValue()).getLineValue() == 0) {
return false;
}
return true;
}
}
After that, just instanciate this constraint for each pair of variable during the creation of the others constraints:
:::java
// Create the constraints between each variable
for (Variable var1 : variables) {
for (Variable var2 : variables) {
if (var1 != var2) {
ArrayList<Variable> vars = new ArrayList<Variable>();
vars.add(var1);
vars.add(var2);
QueenConstraint constraint = new QueenConstraint(vars);
constraints.add(constraint);
// Create an unary constraint in which any queen can't be in
// the (0,0) position.
vars = new ArrayList<Variable>();
vars.add(var2);
QueenUnaryConstraint unaryConstraint = new QueenUnaryConstraint(
vars);
constraints.add(unaryConstraint);
}
}
}
Example 2: N-ary Constrains problem
N-ary constraints problems are kinds of problem on which a variable depends on two or more variables simultaneously. In other words, a variable is restricted by two or more other variables using the same constraint. As an example, let's find the solution for the equation X + Y = Z, i.e, find values for X and Y to satisfy this equation.
The domain of each variable are Dx = {1,2}, Dy = {3,4} and Dz = {5,6}. Notice that the Z variable depends on the X and Y variables simultaneously. To model this kind of problem, it's necessary to create a composed variable to represent the relation of the set (X,Y) with Z. The composed variable has in it's domain the cartesian product of each value of X's domain with the values of Y's domain. A constraint linking the relation between (X,Y) and Z is necessary.
First, create the class representing the value of a variable:
:::java
public class NaryValue implements Value {
private int value;
/**
* @param value
*/
public NaryValue(int value) {
super();
this.value = value;
}
@Override
public boolean equals(Value value) {
NaryValue nvalue = (NaryValue) value;
if (this.value == nvalue.getValue()) {
return true;
}
return false;
}
public int getValue() {
return value;
}
}
Next, implement your own Constraint to link the composed variable with the Z variable:
:::java
public class ComposedVariableConstraint extends Constraint {
public ComposedVariableConstraint(ArrayList<Variable> variables) {
super(variables);
}
@Override
public boolean satisfies() {
ComposedVariable composedVariable = (ComposedVariable) getVariables()
.get(1);
if (getVariables().get(0).getAssignedValue() == null
|| composedVariable.getAssignedValue() == null) {
return true;
}
Variable Z = getVariables().get(0);
int zValue = ((NaryValue) Z.getAssignedValue()).getValue();
int xValue = ((NaryValue) composedVariable.getVariables().get(0)
.getAssignedValue()).getValue();
int yValue = ((NaryValue) composedVariable.getVariables().get(1)
.getAssignedValue()).getValue();
//Z = X + Y ?
if (zValue == (xValue + yValue)) {
return true;
}
return false;
}
}
Notice the class ComposedVariable. It will be used below to compose any number of single variables. The final step is build the variables, the variable's domains (using ComposedValue class) and the constraint between them:
:::java
public class Main {
public static void main(String args[]) {
ArrayList<Variable> variables = new ArrayList<Variable>();
ArrayList<Constraint> constraints = new ArrayList<Constraint>();
// Creates a domain for each variable
ArrayList<Value> domain = new ArrayList<Value>();
domain.add(new NaryValue(5));
domain.add(new NaryValue(6));
Variable variable = new Variable(domain);
variable.setName("Z");
variables.add(variable);
ArrayList<Variable> vars = new ArrayList<Variable>();
domain = new ArrayList<Value>();
domain.add(new NaryValue(1));
domain.add(new NaryValue(2));
Variable varX = new Variable(domain);
varX.setName("X");
vars.add(varX);
domain = new ArrayList<Value>();
domain.add(new NaryValue(3));
domain.add(new NaryValue(4));
Variable varY = new Variable(domain);
varY.setName("Y");
vars.add(varY);
// Create a cartesian product of the domains of the variables that
// participates on the composition.
domain = new ArrayList<Value>();
for (Value value1 : varX.getDomain()) {
for (Value value2 : varY.getDomain()) {
ComposedValue composedValue = new ComposedValue();
ArrayList<Value> values = new ArrayList<Value>();
values.add(value1);
values.add(value2);
composedValue.setValues(values);
domain.add(composedValue);
}
}
//Composed variable containing the X and Y variables.
ComposedVariable composedVariable = new ComposedVariable(domain);
composedVariable.setVariables(vars);
variables.add(composedVariable);
ComposedVariableConstraint constraint = new ComposedVariableConstraint(
variables);
constraints.add(constraint);
CSPSolver solver = new CSPSolver();
solver.setAlgorithm(CSPAlgorithm.LOCAL_SEARCH);
variables = solver.solve(new CSProblem(variables, constraints));
if (variables == null) {
System.out.println("No solution!");
} else {
System.out.println("Used algorithm: "
+ solver.getReport().getAlgorithmName());
for (Variable var : variables) {
if (!(var instanceof ComposedVariable)) {
System.out.println(var.getName() + " = "
+ ((NaryValue) var.getAssignedValue()).getValue());
} else {
for (Variable var1 : ((ComposedVariable) var)
.getVariables()) {
System.out.println(var1.getName()
+ " = "
+ ((NaryValue) var1.getAssignedValue())
.getValue());
}
}
}
System.out.println("");
System.out.println("Number of Backtracks:"
+ solver.getReport().getBackTracksNumber());
System.out.println("Total time: "
+ solver.getReport().getTotalTime() + " segs");
}
}
}
An important statement has to be told: One could use single variables instead of composing the X and Y variables in one single composed one, linking each one to the Z variable using a constraint. It would work. But, a decrease in performance would be experienced because the algorithms were implemented thinking in binary constraints. So, don't be lazy and always use composed variables on those cases.
Available and Customizable Heuristics
There is a number of pre-implemented heuristics that one can use in order to enhance the algorithms performance. Before calling the solve() method, provide a heuristic to the CSPSolver. Depending of the chosen algorithm, choosing an useless heuristic for the algorithm has no effect. Below, there is a list of pre-implemented heuristics and it's corresponding CSPSolver.setXXXHeuristic() methods, along with the algorithms that can be enhanced with each of heuristics:
- jconstraints.heuristics.ChooseVariableHeuristic: A default heuristic that will select the next variable to be assigned with a value. The rule for the variable selection is the number of values prunned from its domain. The variable with more prunned values is selected (smallest domain size). With exception of the local search and tabu search algorithms, all algorithms uses this heuristic to choose the next variable to be assigned. If one want to use another heuristic, extends this class and override the method getNonAssignedVariable(). Then, set the new heuristic in the CSPSolver using the method setChooseVariableHeuristic().
- jconstraints.heuristics.backjump.ConflictSetVariableHeuristic: Default heuristic to choose a variable from a conflict set to be backjumped whenever the backjump algorithms encounter a dead-end branch. One can extends this class and override the method getConflictSetVariable() to implement any other heuristic for the basic backjumping algorithm or to be used in the conflic-directed backjumping algorithms. Then, set the new heuristic in the CSPSolver using the method setConflictSetVariableHeuristic().
- jconstraints.heuristics.backjump.RandomConflictSetHeutistic: Class that inherits from ConflictSetVariableHeuristic in order to choose randomly a variable from the conflict set to be backjumped. It can be used either in the graph-based backjump algorithm or in the conflict-based backjump algorithms.
- jconstraints.heuristics.localsearch.ConflictedVariableHeuristic: Default heuristic to choose a variable that is in conflict with another one. Used in the local search algorithm. If one want to use another heuristic, extends this class and override the method getConflictedVariable(), than set the heuristic in the CSPSolver using the method setConflictVariableHeuristic().
- jconstraints.heuristics.localsearch.InitialStateHeuristic: Heuristic to generate a random initial state to be used in the local search and tabu search algorithms. If one has a different heuristic, just extends this class and override the method setInitialState(). Than, set this new heuristic in the CSPSolver using the method setInitialStateHeuristic().
- jconstraints.heuristics.localsearch.MinConflictValueHeuristic: Heuristic to choose the next value to be assigned to a variable in the local search algorithm. The default behavior is to choose the value that minimizes the number of unsatisfied contraints. If one wants to use another behavior, just override the method getMinConflictValue()
and set the new heuristic in the CSPSolver using the method setMinConflictValueHeuristic().
- jconstraints.heuristics.tabu.SolutionCreationHeuristic: Heuristic to create a new solution to the Tabu Search in each iteration. The default behavior is to select the variable randomly and select a value from it's domain that minimizes the number of unsatisfied constraints. If one wants to use another behavior, just override the method getNewSolution()
and set the new heuristic in the CSPSolver using the method setSolutionCreationHeuristic().
- jconstraints.heuristics.tabu.VariableSelectionHeuristic: Heuristic to select a variable to the Tabu Search in each iteration. The default behavior is to select the variable randomly and select a value from it's domain that minimizes the number of unsatisfied constraints. If one wants to use another behavior, just override the method getSelectedVariable()
and set the new heuristic in the CSPSolver using the method setVariableSelectionHeuristic().
Tabu Search
The Tabu Search is a meta-heuristic composed of a variety of features to enhance constraints problems solving. It maintains a list of variables/solutions forbidden to be chosen for a number of iterations. It uses a greedy local search that can be overriden by developer's heuristics.
The Tabu Search can be configured in a variety of ways:
One can set the tabu list size. The default value if 7 (for variables as elements).
One can choose if the tabu list will store variables or entire solutions (represented by a hash code).
One can choose if it will be used a fixed size tabu list or a dynamic size tabu list allowing some elements to be chosen in the specific iteration.
For solutions as elements, one can provide a specific hash code generator to represent the solutions.
One can provide his own greedy local search to be used in the Tabu meta-heuristic.
The number of iterations that an element stays in the tabu list is equals to the tabu list size. To set the tabu list size use the method setTabuSize() of the CSPSolver instance. To choose between variables tabu list or solutions tabu list, use the methods setUseVariableTabu() / setUseSolutionTabu() of the CSPSolver instance. To choose if the tabu list will have fixed of dynamic size, use the method setUseVaryingTabuSize() of the CSPSolver instance.
Use combinations of the above features to achieve a more enhanced performance.
The developer can also implement his own hash code generator to represent each solution in the tabu list. To do so, inherit from class HashCodeGenerator and overrides the method getHashCode(). Then, use the method setHasCodeGenerator() in the CSPSolver class.
Finally, to implement the greedy local search in the Tabu meta-heuristic, one can inherit from two default heuristics already available for the Tabu Search. The first one is the VariableSelectionHeuristic used when variables are chosen to be the elements of the tabu list. Inherit from this class and override the method getSelectedVariable(). Then, set the new heuristic in the CSPSolver using the method setVariableSelectionHeuristic(). The second one is the SolutionCreationHeuristic used when solutions (the ArrayList of Variables passed to the CSPSolver) are chosen to be the tabu list elements. Inherit from this class and override the method getNewSolution(). Then, set the new heuristic to the CSPSolver using the method setSolutionCreationHeuristic().
One important note is that, the NULL value has an special meaning to the Tabu Search. If the NULL value is the return value of any of those two heuristics, the meta-heuristic will understand that a new initial state has to be created. Therefore, the whole search will be restarted. So, if one wants to restart the search for any reasons, return the NULL value.
Available Algorithms
Below a list of all the algorithms available in JConstraints:
| Algorithm | Description |
|---|---|
| CSPAlgorithm.BACKTRACKING | Basic Backtracking. |
| CSPAlgorithm.BACKTRACKING_WITH_AC2 | Backtracking with arc consistency 2 pre-processing. |
| CSPAlgorithm.BACKTRACKING_WITH_AC3 | Backtracking with arc consistency 3 pre-processing. |
| CSPAlgorithm.FORWARD_CHECK | Backtracking with forward checking. |
| CSPAlgorithm.FORWARD_CHECK_WITH_AC2 | Forward check with arc consistency 2. |
| CSPAlgorithm.FORWARD_CHECK_WITH_AC3 | Forward check with arc consistency 3. |
| CSPAlgorithm.BACKJUMPING | Graph-based Backjumping. |
| CSPAlgorithm.CONFLICT_DIRECTED_BACKJUMPING | Conflict-directed Backjumping. |
| CSPAlgorithm.GASCHNIG_BACKJUMPING | Gaschnig's Backjumping. |
| CSPAlgorithm.BACKJUMPING_WITH_FCHECK | Conflict-based Backjumping using forward check. |
| CSPAlgorithm.LOCAL_SEARCH | Local Search. |
| CSPAlgorithm.TABU_SEARCH | Tabu Search meta-heuristic. |
Project Members:
- Julio Heitor Silva Nóbrega (admin)
