6.4 Limited discrepancy search

Limited discrepancy search (LDS) uses the partial search method proposed in [7]. It basically allows only a number of different decisions along a search path, called discrepancies. If the number of discrepancies is exhausted backtracking is initiated. The number of discrepancies is specified as a parameter for LDS.

An example of LDS with one discrepancy is as follows.

   Search<IntVar> label = new DepthFirstSearch<IntVar>(); 
   SelectChoicePoint<IntVar> select = new SimpleSelect<IntVar>(var, 
                                      new SmallestDomain<IntVar>(), 
                                      new IndomainMiddle<IntVar>()); 
   LDS<IntVar> lds = new LDS<IntVar>(2); 
   label.getExitChildListener().setChildrenListeners(lds); 
 
   boolean result = label.labeling(store, select);