6.3 Credit search

Credit search combines credit based exhaustive search at the beginning of the tree with local search in the rest of the tree [1]. In JaCoP, the credit search is controlled by three parameters: number of credits, number of backtracks during local search and maximum depth of search. In Figure 6.1 there is an example of the credit search tree. The search has initially 8 credits. The number of possible backtracks is three. During search half of the credits is distributed to the selected choice. The rest of the credits is distributed using the same principle for the next choice point. The first part of the search is based on the credits and makes it possible to investigate many possible assignments to domain variables while the other part is supposed to lead to a solution and can use a number of backtracks specified for this search. Moreover, the maximal depth of the search cannot be exceeded. Since we control the search it is possible to partially explore the whole tree and avoid situations when the search is stuck at one part of the tree which is a common problem of B&B algorithm when a depth first search strategy is used.


Figure 6.1: Credit search example.

An example of the command which produces the search tree depicted in Fig. 6.1 is as follows.

   SelectChoicePoint<IntVar> select = new SimpleSelect<IntVar>(vars, 
                                       new SmallestDomain<IntVar>(), 
                                       new IndomainMin<IntVar>()); 
   int credits=8, backtracks=3, maxDepth=1000; 
   CreditCalculator<IntVar> credit = new CreditCalculator<IntVar>( 
   Search<IntVar> search = new DepthFirstSearch<IntVar>(); 
   boolean result = search.labeling(store, select);