Search for solutions

After specification of the model consisting of variables and constraints, a search for a solution can be started. JaCoP offers a number of methods for doing this. It makes it possible to search for a single solution or to try to find a solution which minimizes/maximizes given cost function. This is achieved by using the depth-first-search together with constraint consistency enforcement.

The consistency check of all imposed constrains is achieved calling the following method from class Store.

boolean result = store.consistency();

When the procedure returns false then the store is in inconsistent state and no solution exists. The result true only indicates that inconsistency cannot be found. In other words, since the finite domain solver is not complete it does not automatically mean that the store is consistent.

To find a single solution the DepthFirstSearch method can be used. Since the search method is used both for finite domain variables and set variables it is recommended to specify the type of variables that are used in search. For finite domain variables, this type is usually . It is possible to not specify these information but it will generate compilation warnings if compilation option -Xlint:unchecked is used. A simple use of this method is shown below.

   IntVar[] vars;
   ...
   Search<IntVar> label = new DepthFirstSearch<IntVar>();
   SelectChoicePoint<IntVar> select =
            new InputOrderSelect<IntVar>(store,
                                   vars, new IndomainMin<IntVar>());
   boolean result = label.labeling(store, select);

Different classes can be used to implement SelectChoicePoint interface. They are summarized in Appendix B. The following example uses SimpleSelect that selects variables using the size of their domains, i.e., variable with the smallest domain is selected first.

   IntVar[] vars;
   ...
   Search<IntVar> label = new DepthFirstSearch<IntVar>();
   SelectChoicePoint<IntVar> select =
                new SimpleSelect<IntVar>(vars,
                                         new SmallestDomain<IntVar>(),
                                         new IndomainMin<IntVar>());
   boolean result = label.labeling(store, select);

In some situations it is better to group FDVs and assign the values to them one after the other. JaCoP supports this by another variable selection method called SimpleMatrixSelect. An example of its use is shown below. This choice point selection heuristic works on two-dimensional lists of FDVs.

   IntVar[][] varArray;
   ...
   Search<IntVar> label = new DepthFirstSearch<IntVar>();
   SelectChoicePoint<IntVar> select =
                 new SimpleMatrixSelect<IntVar>(
                                       varArray,
                                       new SmallestMax<IntVar>(),
                                       new IndomainMin<IntVar>());
   boolean result = label.labeling(store, select);

The optimization requires specification of a cost function. The cost function is defined by a FDV that, with the help of attached (imposed) constraints, gets correct cost value. A typical minimization for defined constraints and a cost FDV is specified below.

   IntVar[] vars;
   IntVar cost;
   ...
   Search<IntVar> label = new DepthFirstSearch<IntVar>();
   SelectChoicePoint<IntVar> select = new SimpleSelect<IntVar>(vars,
                                       new SmallestDomain<IntVar>(),
                                       new IndomainMin<IntVar>());
   boolean result = label.labeling(store, select, cost);

JaCoP offers number of different search heuristics based on depth-first-search. For example, credit search and limited discrepancy search. They are implemented using plug-in listeners that modify the standard depth-first-serch. For more details, see section 6.

2.4 Search for solutions