6.1 Depth First Search

A solution satisfying all constraints can be found using a depth first search algorithm. This algorithm searches for a possible solution by organizing the search space as a search tree. In every node of this tree a value is assigned to a domain variable and a decision whether the node will be extended or the search will be cut in this node is made. The search is cut if the assignment to the selected domain variable does not fulfill all constraints. Since assignment of a value to a variable triggers the constraint propagation and possible adjustment of the domain variable representing the cost function, the decision can easily be made to continue or to cut the search at this node of the search tree.

Typical search method for a single solution, for a list of variables, is specified as follows.

   Search<T> label = new DepthFirstSearch<T>(); 
   SelectChoicePoint<T> select = new SimpleSelect<T>(var, 
                                               varSelect, 
                                               tieBreakerVarSelect 
                                               indomain); 
   boolean result = label.labeling(store, select);

where T is type of variables we are using for this search (usually IntVar or SetVar), var is a list of variables, varSelect is a comparator method for selecting variable and tieBreakerV arSelect is a tie breaking comparator method. The tie breaking method is used when the varSelect method cannot decide ordering of two variables. Finally, indomain method is used to select a value that will be assigned to a selected variable. Different variable selection and indomain methods are specified in appendix B. This search, for variables of type IntVar creates choice points xi = val and xival where xi is variable identified by variable selection comparators and val is the value determined by indomain method. For variables of type SetVar the choice is made between val xi or val∈∕xi.

The standard method can be further modified to create search for all solutions. This is achieved by adopting the standard solution listener as specified below.

   label.getSolutionListener().searchAll(true); 
   label.getSolutionListener().recordSolutions(true);

In the first line the flag that changes search to find all solutions is set. It is set in the default solution listener. In this example, we also set a flag that informs search to record all found solutions. If this flag is not set the search will only count solutions without storing them. The values for found solutions can be printed using label.getSolutionListener().printAllSolutions() method or the following piece of code.

   for (int i=1; i<=label.getSolutionListener().solutionsNo(); i++){ 
      System.out.print("Solution " + i + ": "); 
      for (int j=0; j<label.getSolution(i).length; j++) 
         System.out.print(label.getSolution(i)[j]); 
      System.out.println(); 
   }

Even if the solutions are not recorded, they are counted and number of found solutions can be retrieved using method label.getSolutionListener().solutionsNo().

The minimization in JaCoP is achieved by defining variable for cost and using branch-and-bound (B&B) search, as specified below.

   IntVar cost; 
   ... 
   boolean result = label.labeling(store, select, cost);

B&B search uses depth-first-search to find a solution. Each time a solution with cost costV aluei is found a constraint cost < costV aluei is imposed. Therefore the search finds solutions with lower cost until it eventually fails to find any solution that proves that the last found solution is optimal, i.e., there is no better solution.

Sometimes we want to interrupt search and report the best solution found in a given time. For this purpose, the search time-out functionality can be used. For example, 10s time-out can be set with the following statement.

   label.setTimeOut(10);

Moreover, one can define own time-out listener to perform specific actions.

6.1.1 Restart search

In some situation classical B&B algorithm is not best suited for optimization and so called restart search is used. This optimization search method finds a solution and then start search from the beginning but with additional constraint restricting the cost variable in the same way as B&B search. JaCoP does not support directly this kind of search but it can be easily implemented using the following code (use to maximize cost defined by variable cost).

   label.setSolutionListener(new CostListener<IntVar>()); 
   store.setLevel(store.level+1); 
   boolean Result = true, optimalResult = false; 
   while (Result) { 
      Result = label.labeling(store, select); 
      store.impose(new XgtC(cost, CostValue)); 
      optimalResult = optimalResult || Result; 
   } 
   store.removeLevel(store.level); 
   store.setLevel(store.level-1);

The search iteratively calls depth-first-search until no better solution is found. It also rises the store level before search and returns to “fresh” store to make it possible to operate on it later. This code requires access to value CostV alue that can be retrieved by providing a customized version of solution listener and its method executeAfterSolution. This method simply stores the value of the cost variable when a solution is found. See the code below for details.

   public class CostListener<T extends Var> extends 
                                         SimpleSolutionListener<T> { 
 
      public boolean executeAfterSolution(Search<T> search, 
                                      SelectChoicePoint<T> select) { 
         boolean returnCode = super.executeAfterSolution(search, 
                                                         select); 
 
         CostValue = cost.value(); 
         return returnCode; 
      } 
   }