Module org.maxicp
Package org.maxicp.search

Class Searches

java.lang.Object
org.maxicp.search.Searches
public final class Searches extends Object
Factory for search procedures.
See Also:

  • Field Details

    • EMPTY

      public static final Runnable[] 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:

    • EMPTY_SYMB

      public static final SymbolicBranching[] EMPTY_SYMB

  • Method Details

    • branch

      public static Runnable[] branch(Runnable... 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:

    • branch

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

    • 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.

    • selectMin

      public static <T, N extends Comparable<N>> T selectMin(Iterable<T> items, Predicate<T> p, Function<T,N> f)
      Minimum selector.

      Example of usage. 

           
     int i = selectMin(
       IntStream.range(0, n).boxed().toList(),
       qi -> q[qi].size() > 1,
       qi -> q[qi].size()
     );
      Type Parameters:
      T -
      N -
      Parameters:
      items - the iterable 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 items
      Returns:
      the minimum element in items that satisfies the predicate p

    • selectMin

      public static <T, N extends Comparable<N>> T selectMin(T[] x, int n, Predicate<T> p, Function<T,N> f)
      Minimum selector.

      Example of usage. 

       
 IntVar xs = selectMin(x,n, 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
      n - the n first elements from x that must be considered
      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.

    • selectMin

      public static <N extends Comparable<N>> OptionalInt selectMin(int[] x, int n, Predicate<Integer> p, Function<Integer,N> f)
      Minimum selector.

      Example of usage. 

       
 OptionalInt i = selectMin(values,n, i -> x[i].isFixed() > 1, i -> x[i].size());
      Parameters:
      x - the array on which the minimum value is searched
      n - the n first elements from x that must be considered
      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.

    • heuristicBinary

      public static Supplier<Runnable[]> heuristicBinary(Supplier<IntExpression> variableSelector)
      Binary Branching with custom variable heuristic and natural value ordering.
      Parameters:
      variableSelector - returns the next variable to bind, null if all variables are fixed
      Returns:
      a static branching strategy, the minimum value of the variable domain is attempted on the left, and removed on the right

    • heuristicBinary

      public static Supplier<Runnable[]> heuristicBinary(Supplier<IntExpression> variableSelector, Function<IntExpression,Integer> valueSelector)
      Binary Branching with custom variable and value heuristics.
      Parameters:
      variableSelector - the variable heuristic, returns the variable on which the branching is applied null if all variables are fixed
      valueSelector - given the variable, returns the value assigned in the left branch, and removed fin the right branch

    • heuristicNary

      public static Supplier<Runnable[]> heuristicNary(Supplier<IntExpression> variableSelector)
      N-ary Branching with custom variable heuristic and natural value ordering.
      Parameters:
      variableSelector - returns the variable on which the n-ary branching is applied null if all variables are fixed
      Returns:
      an n-ary branching strategy with the variable heuristic and natural value ordering (increasing order).

    • heuristicNary

      public static Supplier<Runnable[]> heuristicNary(Supplier<IntExpression> variableSelector, Function<Integer,Integer> valueHeuristic)
      N-ary Branching with custom variable and value heuristics.
      Parameters:
      variableSelector - returns the variable on which the n-ary branching is applied
      valueHeuristic - the branches for each value are ordered according to the value of this function (in increasing order). This function is called once for each value in the variable domain to sort them according to the heuristic before creating the branches in the sorted order.
      Returns:
      an n-ary branching strategy

    • staticOrderNary

      public static Supplier<Runnable[]> staticOrderNary(IntExpression... xs)
      N-ary Branching with static variable ordering and natural value ordering.
      Parameters:
      xs - the variable array to fix
      Returns:
      an n-ary branching strategy with static variable ordering and natural value ordering (increasing order).

    • staticOrderBinary

      public static Supplier<Runnable[]> staticOrderBinary(IntExpression... xs)
      Binary Branching with static variable ordering and natural value ordering.
      Parameters:
      xs - the variable array to fix
      Returns:
      a binary static branching strategy, min value on the left, remove it on the right

    • staticOrderBinary

      public static Supplier<Runnable[]> staticOrderBinary(Function<IntExpression,Integer> valueSelector, IntExpression... xs)
      Binary Branching with static variable ordering and custom value heuristic.
      Parameters:
      valueSelector - the value heuristic, given a variable, returns the value to which it must be assigned on the left branch, and removed on the right branch
      xs - the variable array to fix,
      Returns:
      a binary static branching strategy on the variable, but the value is selected by the heuristic on the left, removed on the right branches

    • firstFailBinary

      public static Supplier<Runnable[]> firstFailBinary(IntExpression... x)
      First-Fail Binary search strategy. Selects the first not fixed variable with smallest domain. 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

    • firstFailNary

      public static Supplier<Runnable[]> firstFailNary(IntExpression... x)
      First-Fail N-Ary search strategy. It selects the first variable with a domain larger than one. Then it creates one branch for each value in increasing order.
      Parameters:
      x - the variable on which the first fail strategy is applied.
      Returns:
      a first-fail n-ary branching strategy

    • and

      public static Supplier<Runnable[]> and(Supplier<Runnable[]>... 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:

    • limitedDiscrepancy

      public static Supplier<Runnable[]> limitedDiscrepancy(Supplier<Runnable[]> 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:

    • minDomVariableSelector

      public static Supplier<IntExpression> minDomVariableSelector(IntExpression... xs)
      It selects the first not fixed variable with the smallest domain.
      Parameters:
      xs - the variable array to fix
      Returns:
      a supplier that returns the first not fixed variable with the smallest domain, null if all variables are fixed

    • staticOrderVariableSelector

      public static Supplier<IntExpression> staticOrderVariableSelector(IntExpression... xs)

    • lastConflict

      public static Supplier<Runnable[]> lastConflict(Supplier<IntExpression> variableSelector, Function<IntExpression,Integer> valueSelector)
      Last conflict heuristic Attempts to branch first on the last variable that caused an Inconsistency

      Lecoutre, C., Saïs, L., Tabary, S., Vidal, V. (2009). Reasoning from last conflict (s) in constraint programming. Artificial Intelligence, 173(18), 1592-1614.

      Parameters:
      variableSelector - returns the next variable to bind
      valueSelector - given a variable, returns the value to which it must be assigned on the left branch (and excluded on the right)

    • conflictOrderingSearch

      public static Supplier<Runnable[]> conflictOrderingSearch(Supplier<IntExpression> variableSelector, Function<IntExpression,Integer> valueSelector)
      Conflict Ordering Search

      Gay, S., Hartert, R., Lecoutre, C., Schaus, P. (2015). Conflict ordering search for scheduling problems. In International conference on principles and practice of constraint programming (pp. 140-148). Springer.

      Parameters:
      variableSelector - returns the next variable to bind (fall back heuristic)
      valueSelector - given a variable, returns the value to which it must be assigned on the left branch (and excluded on the right)

    • conflictOrderingSearch

      public static Supplier<Runnable[]> conflictOrderingSearch(IntExpression... xs)
      Conflict Ordering Search with default variable selector (first-fail min dom) and value selector (min value).

      Gay, S., Hartert, R., Lecoutre, C., Schaus, P. (2015). Conflict ordering search for scheduling problems. In International conference on principles and practice of constraint programming (pp. 140-148). Springer.

    • firstFailBinary

      public static Supplier<Runnable[]> firstFailBinary(SeqVar... seqVars)

    • nodeSelector

      public static OptionalInt nodeSelector(SeqVar[] seqVars, int[] nodes, BiFunction<SeqVar,Integer,Integer> nodeCost)
      Generic node selector for sequence variables.

      Example of usage. 

       
 OptionalInt node = nodeSelector(routes, nodes, (seqvar, node) -> seqvar.nInsert(node));
      Parameters:
      seqVars - sequences variables in the problem
      nodes - nodes over which the sequence variables are related
      nodeCost - heuristic cost used to select the node, summed over all sequences
      Returns:
      node with the minimum cost, summed over all sequence variables

    • nodeSelector

      public static OptionalInt nodeSelector(SeqVar[] seqVars, int[] nodes, BiFunction<SeqVar,Integer,Integer> nodeCost, BiFunction<Integer,Integer,Integer> nodeCostAggr)
      Generic node selector for sequence variables.

      Example of usage. 

       
 OptionalInt node = nodeSelector(routes, nodes, (seqvar, node) -> seqvar.nInsert(node), (c1, c2) -> c1 + c2);
      Parameters:
      seqVars - sequences variables in the problem
      nodes - nodes over which the sequence variables are related
      nodeCost - heuristic cost used to select the node, summed over all sequences
      nodeCostAggr - aggregator to combine the heuristic cost of two sequence variables
      Returns:
      node with the minimum cost, summed over all sequence variables

    • branchesInsertingNode

      public static Supplier<Function<Integer,Runnable[]>> branchesInsertingNode(SeqVar[] seqVars, TriFunction<Integer,Integer,Integer,Integer> detourCost)
      Generates all branches inserting a node, sorted by a given detour cost.

      Example of usage. 

       
 int[][] d = ... // distance matrix between nodes
 Function<Integer, Runnable[]> branchGenerator = branchesInsertingNode(seqvar, (pred, node, succ) -> d[pred][node] + d[node][succ] - d[pred][succ]).get();
 Runnable[] branches = branchGenerator.apply(node); // all branches inserting the given node
      Parameters:
      seqVars - sequence over which the node may be inserted
      detourCost - detour cost for inserting a node between a predecessor and a successor; lower values are tried first. Arguments are (pred, node succ), where pred is the node after which the insertion happen, node is the node to insert and succ the current node after pred
      Returns:

    • branchesInsertingNode

      public static Supplier<Function<Integer,Runnable[]>> branchesInsertingNode(SeqVar[] seqVars, int[][] distMatrix)

    • boundImpactValueSelector

      public static Function<IntExpression,Integer> boundImpactValueSelector(IntExpression objective)
      Bound-Impact value selector. Gives a value selector yielding the value leading to the smallest decrease on the objective

      This value selection strategy was introduced in: Fages, J. G., Prud’Homme, C. Making the first solution good! In 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE.

      Parameters:
      objective - objective whose impact must be measured
      Returns:
      value decreasing the less the objective lower bound. Null if no value is valid for the variable

    • setTimes

      public static Supplier<Runnable[]> setTimes(IntervalVar[] intervals, IntFunction tieBreaker)
      The SetTimes branching search is a branching scheme for scheduling problems with "regular" constraints between the tasks (e.g., precedence constraints). The branching scheme is based on the following principle: - Select the earliest start time among the non postponed tasks - Branch on the start time of the task (Le Pape, C., Couronne, P., Vergamini, D., and Gosselin, V. (1995). Time-versus-capacity compromises in project scheduling)
      Parameters:
      intervals - tasks that must be decided
      tieBreaker - how to select the best task to branch on when several have the same earliest start time
      Returns:
      set time branching

    • setTimes

      public static Supplier<Runnable[]> setTimes(IntervalVar[] intervals)

    • fds

      public static Supplier<Runnable[]> fds(CPIntervalVar[] intervals)

    • fds

      public static Supplier<Runnable[]> fds(IntervalVar[] intervals)

    • branchOnStartMin

      public static Runnable[] branchOnStartMin(IntervalVar var)

    • branchOnStatus

      public static Runnable[] branchOnStatus(CPIntervalVar var)

    • branchOnPresentStarts

      public static Supplier<Runnable[]> branchOnPresentStarts(IntervalVar... vars)

    • branchOnStatus

      public static Supplier<Runnable[]> branchOnStatus(CPIntervalVar... vars)

    • branchOnStatusThenStarts

      public static Supplier<Runnable[]> branchOnStatusThenStarts(CPIntervalVar... vars)