JACK: Java Constraint Kit

Home

Documentation

Sources

Contributors

Documentation

JCHR

JASE

VisualCHR
1. Documentation and Download
2. Demo

JASE

For the search, an exploration is used to walk through a search tree which consists of nodes; the behaviour of the nodes is implemented by choices.

1. Search concepts and interfaces

Search tree: A search tree is an unbalanced binary tree. Each inner node of the tree represents one state of the constraint system. Each edge between two nodes represents the transformation of one state into another. Leaf nodes are either empty, and represent a failed constraint system state, or they contain a solution.

Exploration: An exploration (interface SExploration) implements how to walk through the tree; for example depth-first search.

Nodes: A node is implemented by the class SNode. An object of this class stores the constraint system state, and is used by the SExploration classes. It does not, however, know about any application details - i.e., what handler is used, which variables are enumerated, which constraints are to be evaluated.

Choices: A choice (point) is implemented by a class that implements the interface SChoice. It deals with selecting variables to enumerated, and evaluates constraints. If a new JCHR handler should be enabled for search, (only) this interface must be implemented by a new class.

back

2. How to run a search in the Finite Domain handler?

To run a search, the constraint system and variables must have been created in Java code, as described in Interface JCHR - Java. The following code will enumerate the variable X, Y and Z:

        ObjectContainer vars=new ObjectContainer();
        vars.add(X);
        vars.add(Y);
        vars.add(Z);

        SChoice collector=new SCollectorChoice(vars,cs.getVariableNames(vars));

        SChoice rootChoice=SFDChoice.enumeration(vars,
                       cs.getVariableNames(vars),0,collector,trace);

        SExploration exploration=new SDepthFirstExploration(cs,rootChoice);

        boolean success=SSearch.all(exploration);       

        System.out.println(((SCollectorChoice)collector).toBeautifulString());

This code can be used as a simple search template. For an explanation of the classes used, see Classes and interfaces for using search. Different search strategies (other than depth-first) can be used too, see Branch and bound and Limited discrepancy search.

back

3. Classes and interfaces for using search

These classes and interfaces are directly usable for a search:

SChoice

This is the interface which must be implemented by all choices. There are several predefined implementations of this in the JACK system, which are distinguished as root choices, continuation choices and special choices.

Root choices
Each root choice is fixed to one handler.
- SFDChoice: while not being an instance of SChoice itself, this class has two static methods for creating different root choices for the Finite Domains handler:
  public static SChoice enumeration(ObjectContainer vars, ObjectContainer varNames,int curVar,SChoice continuation, boolean trace)
  This method creates a choice for simple variable enumeration (variables and their values are picked from left to right). The parameters are:
  - vars: A container with all the variables (of type java.lang.Object, see Interface JCHR - Java) which are to be enumerated.
  - varNames: A container with names for the variables. It can easily be created by using ConstraintSystem.getVariableNames(), which takes an ObjectContainer with variables and returns an ObjectContainer with variable names. This is only meaningful for the toString() and other debugging or tracing methods and can be null if those methods are not used.
  - curVar: This is used internally by the choice classes and must be 0.
  - continuation: This is a continuation choice.
  - trace: If this flag is true, the constraint system is instructed to output tracing information while running the search.
  The next method creates a choice for splitting the variable domains with optionally a heuristic to select the variables in an order different than left-to-right:
  public static SChoice splitting(ObjectContainer vars, ObjectContainer varNames,int curVar,SChoice continuation, boolean trace,boolean pickLargest)
  The parameters are exactly the same as for the enumeration method; additionally, if pickLargest is true, then variables are selected so that in each node, the variable with the currently largest domain is splitted first.
- SBoolChoice: This is the choice for the Boolean handler; for each variable it first tries the value false, then the value true. It has the following constructor:
  SBoolChoice(ObjectContainer vars,ObjectContainer varNames,int curVar,SChoice continuation,boolean trace)
  The constructor parameters are exactly the same as for the enumeration method of the Finite Domain choice.
Continuation choices
These choices process the solutions found during the search.
- SCollectorChoice: This continuation simply collects all solutions. They can later be processed, or printed.
  This is the constructor:
  SCollectorChoice(ObjectContainer vars,ObjectContainer varNames)
  After the search has been run, the following methods can be used:
  - getSolutions(): This returns an ObjectContainer which in turn contains one instance of ObjectContainer per solution. These containers contain the variable bindings for all the variables in the same order as given in the constructor.
  - toBeautifulString(): This returns a string with a beautiful representation of the results. It optionally takes a boolean parameter, which, if true, gives a more dense representation.
- SPrintChoice: This prints all solution as soon as they are found. It has the same constructor as SCollectorChoice and no further methods interesting to the user.
- SChoiceOperator: This is an abstract base class for continuations similar to SCollectorChoice and SPrintChoice. A class which derives from this base class needs to implement one single method:
  abstract void run(ConstraintSystem system)
  This method will be called whenever a solution is encountered during the search and can access the constraint system like explained in Interface JCHR - Java.
Special choices
At this moment, there is one special choice:
- STraceChoice: This class adds a debugging layer to another choice. It has one constructor:
  public STraceChoice(OutputStream stream,SChoice choice)
  The stream can be System.out, for example. The instance of STraceChoice will have exactly the same behaviour of the root choice passed into it, but it will also output information about the ongoing search while it runs (e.g., it shows nodes as they are created, along with the constraint system state and variable bindings).

SDepthFirstExploration

This class implements depth-first exploration. It has no methods for the end user. The constructor is this:

public SDepthFirstExploration(ConstraintSystem system,SChoice choice)

SSearch

This class has several static methods for actually running the search:

public static boolean first(SExploration exp)
This method looks for the first solution and stops.
public static boolean all(SExploration exp)
This method looks for all solutions.
public static boolean best(SExploration exp,SBestSearchCollector coll, ConstraintSystem system)
See Branch and bound.

back

4. Branch and bound

There are special classes in the JACK system which do branch-and-bound search. Instead of just walking through the whole search tree, this algorithm modifies the constraint system after a solution is found, and restarts the search. The modification is to insert a new constraint which assures that any further solution is better than the last solution.

The standard search template must be modified to use branch and bound:

A special continuation choice must be used:

SBestSearchCollector continuation=new MyCollector(...);

The class MyCollector must implement the following method:

public void addBetterConstraint(ConstraintSystem system)

This method must insert a new constraint into the constraint system, which takes the currently "best" solution into account and guarantees that any further solution will be better.

For example, this class would maximize the first variable of a list of variables:

    class MaxCollector extends SBestSearchCollector
    {
	private Object theVariable;

	MaxCollector(ObjectContainer variables,ObjectContainer variableNames)
	{
	    super(variables,variableNames);
	    theVariable=variables.get(0);
	}

	public void addBetterConstraint(ConstraintSystem cs)
	{
	    ObjectContainer bestSolution=getSolution();
	    Object value=bestSolution.get(0);
 	    cs.addGoalConstraint(new FDLTConstraint(value,theVariable);
	}
    }

A special method of SSearch must be used:

    boolean success=SSearch.best(exploration,continuation,cs);

To retrieve the final solution, the method public ObjectContainer getSolution() of the continuation must be used. It returns a list of variable bindings which corresponds to the list of variables passed in to the constructor of SBestSearchCollector.

The complete code template for using branch-and-bound looks like this:

        ObjectContainer vars=new ObjectContainer();
        vars.add(X);
        vars.add(Y);
        vars.add(Z);

	SBestSearchCollector coll=new MaxCollector(variables,variableNames);

        SChoice rootChoice=SFDChoice.enumeration(vars,
                       cs.getVariableNames(vars),0,collector,trace);
	
	SExploration exploration=new SDepthFirstExploration(cs,rootChoice);

	boolean success=SSearch.best(exploration,coll,cs);

 	System.out.println(((SBestSearchCollector)coll).toBeautifulString());

back

5. Limited discrepancy search

Limited discrepancy search (LDS) has been implemented in the standard JACK distribution, too. LDS is a variant of the depth-first search which changes the order in which the nodes are visited. It assumes that the heuristic used to chose the children of a node is very good, that is, that the first child will lead to the "wanted" solution more often than not.

If the heuristic would be perfect, the solution would immediately be found when walking along the left-most path of the search tree. This path is assigned a discrepancy count of 0. If, along another path in the search tree, there is exactly one node where the edge to the second instead of the first child is followed, we assign it a discrepancy count of 1 (and so on). Thus, the last path through the tree, which follows the second child in every node, has maximal discrepancy count.

LDS now enumerates all solutions ordered by their discrepancy count. It does this by limiting the allowed discrepancies - if, during the search, a node has a higher discrepancy than allowed, it (and its subtree) is removed. The search is first run with a small allowed discrepancy, and this is increased until a solution (or some maximum discrepancy) is reached (a more detailled description of LDS).

To use LDS, the class SDiscrepancyExploration must be used instead of SDepthFirstExploration, using this constructor:

public SDiscrepancyExploration(ConstraintSystem system,SChoice choice,int startingMaxDisc,int discLimit)

system: The constraint system.
choice: The root choice.
startingMaxDisc: This is the initially allowed discrepancy.
discLimit: This is the maximal allowed discrepancy.

A template for using LDS is:

        ObjectContainer vars=new ObjectContainer();
        vars.add(X);
        vars.add(Y);
        vars.add(Z);

        SChoice collector=new SCollectorChoice(vars,cs.getVariableNames(vars));

        SChoice rootChoice=SFDChoice.enumeration(vars,
                       cs.getVariableNames(vars),0,collector,trace);

        SExploration exploration=new
           SDiscrepancyExploration(cs,rootChoice,0,100);

        boolean success=SSearch.all(exploration);       

        System.out.println(((SCollectorChoice)collector).toBeautifulString());

back

6. Classes and interfaces for implementing new search algorithms

There are several ways to create new search algorithms. First of all, and in most cases, you will want to modify an existing algorithm slightly, or add functionality to one. Most ways to extend the "simple" depth first search are already available in the JASE toolkit (for example, LDS search which changes the SDepthFirstExploration, or Branch and Bound, which uses a custom continuation SChoice).

For details on the implementation, and an thorough explanation of the background of JASE, please refer to the diploma thesis of JASE.

6.1. Implementing a new `SChoice`

Since each different JCHR handler needs its own SChoice, this class is very interesting in most cases. See the enumeration choice of the Finite Domain handler for an example.

Things to do when implementing a new instance of SChoice:

Add implements SChoice to your class.
Provide some means to let each instance of the new class know on which variable it has to work (for example, by passing along a list of variables to the constructor, and having a field int curVar in each instance).
Also, a continuation should be stored. for latter use in choose.
Implement the method
```
public SChoice choose(ConstraintSystem system,boolean firstChoice)
```
It has the following responsibilities:
- Modify the constraint system (for example, by binding one variable to one value of its domain). This is equivalen to walking down the edge to either the left or right child of the node in the search tree (as specified by firstChoice). Example (red code)
- Run ConstraintSystem.callGoal. Example (blue code)
- Return an instance of SChoice which will be called by the JASE engine when the node along that edge is entered. This choice can either be of the same class as the current one, or can be the continuation. Example (green code)
The implementation of your SChoice should be as lean and fast as possible, since it is called most often in the search process. Take care not to create superfluous objects in it (for example, by "recycling" instances of your SChoice), since they just increase memory use and garbage collection time.

6.2. Implementing a new `SExploration`

If you want to create a new or modified way to walk through the search tree, you have to implement a new instance of SExploration. This interface has one important method,

public SNode performOneStep()

which does exactly what its name implies - perform one transition from the current node in the search tree to the next node (where the definition of "next" depends on the algorithm to be implemented).

In most cases, you can use the existing (trivial) depth first implementation and modify it.

6.3. Changing the way in which results are processed

Results of a search are processed by continuation SChoice's. If you need more functionality than just collecting the results or printing them out, then override the abstract class SChoiceOperator and implement its method

abstract void run(ConstraintSystem system)

An object of this class can be passed to any search, and the run method will be called whenever a solution is found. See the section on continuation choices for more information.

back

Last modified: Mon Sep 17 10:26:26 CEST 2001