minicp.cp

Class BranchingScheme

java.lang.Object

minicp.cp.BranchingScheme

public final class BranchingScheme
extends Object

Factory for search procedures.

A typical custom search on an array of variable q is illustrated next

 
 DFSearch search = Factory.makeDfs(cp, () -> {
   int idx = -1; // index of the first variable that is not bound
   for (int k = 0; k < q.length; k++)
      if(q[k].size() > 1) {
        idx=k;
        break;
      }
   if(idx == -1)
      return new Procedure[0];
   else {
      IntVar qi = q[idx];
      int v = qi.min();
      Procedure left = () -> Factory.equal(qi, v);
      Procedure right = () -> Factory.notEqual(qi, v);
      return branch(left,right);
   }
 });
 
 

See Also:

Factory.makeDfs(Solver, Supplier)

Field Summary

Fields

Modifier and Type	Field and Description
static Procedure[]	EMPTY Constant that should be returned to notify the solver that there are no branches to create any more and that the current state should be considered as a solution.

Method Summary

Modifier and Type	Method and Description
static Supplier<Procedure[]>	and(Supplier<Procedure[]>... choices) Sequential Search combinator that linearly considers a list of branching generator.
static Procedure[]	branch(Procedure... branches)
static Supplier<Procedure[]>	firstFail(IntVar... x) First-Fail strategy.
static Supplier<Procedure[]>	limitedDiscrepancy(Supplier<Procedure[]> branching, int maxDiscrepancy) Limited Discrepancy Search combinator that limits the number of right decisions
static <T,N extends Comparable<N>> T	selectMin(T[] x, Predicate<T> p, Function<T,N> f) Minimum selector.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

EMPTY

public static final Procedure[] EMPTY

Constant that should be returned to notify the solver that there are no branches to create any more and that the current state should be considered as a solution.

See Also:

Factory.makeDfs(Solver, Supplier)

Method Detail

branch

public static Procedure[] branch(Procedure... branches)

Parameters:

branches - the ordered closures for the child branches ordered from left to right in the depth first search.

Returns:

an array with those branches

See Also:

DFSearch

selectMin

public static <T,N extends Comparable<N>> T selectMin(T[] x,
                                                      Predicate<T> p,
                                                      Function<T,N> f)

Minimum selector.

Example of usage.

 
 IntVar xs = selectMin(x,xi -> xi.size() > 1,xi -> xi.size());
 
 

Type Parameters:

T - the type of the elements in x, for instance IntVar

N - the type on which the minimum is computed, for instance Integer

Parameters:

x - the array on which the minimum value is searched

p - the predicate that filters the element eligible for selection

f - the evaluation function that returns a comparable when applied on an element of x

Returns:

the minimum element in x that satisfies the predicate p or null if no element satisfies the predicate.

firstFail

public static Supplier<Procedure[]> firstFail(IntVar... x)

First-Fail strategy. It selects the first variable with a domain larger than one. Then it creates two branches. The left branch assigning the variable to its minimum value. The right branch removing this minimum value from the domain.

Parameters:

x - the variable on which the first fail strategy is applied.

Returns:

a first-fail branching strategy

See Also:

Factory.makeDfs(Solver, Supplier)

and

public static Supplier<Procedure[]> and(Supplier<Procedure[]>... choices)

Sequential Search combinator that linearly considers a list of branching generator. One branching of this list is executed when all the previous ones are exhausted (they return an empty array).

Parameters:

choices - the branching schemes considered sequentially in the sequential by path in the search tree

Returns:

a branching scheme implementing the sequential search

See Also:

Sequencer

limitedDiscrepancy

public static Supplier<Procedure[]> limitedDiscrepancy(Supplier<Procedure[]> branching,
                                                       int maxDiscrepancy)

Limited Discrepancy Search combinator that limits the number of right decisions

Parameters:

branching - a branching scheme

maxDiscrepancy - a discrepancy limit (non negative number)

Returns:

a branching scheme that cuts off any path accumulating a discrepancy beyond the limit maxDiscrepancy

See Also:

LimitedDiscrepancyBranching