Class Search
 java.lang.Object

 org.chocosolver.solver.search.strategy.Search

public class Search extends Object


Constructor Summary
Constructors Constructor Description Search()

Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static AbstractStrategy<IntVar>
activityBasedSearch(IntVar... vars)
Create an Activity based search strategy.static AbstractStrategy<IntVar>
bestBound(AbstractStrategy<IntVar> formerSearch)
Search heuristic combined with a constraint performing strong consistency on the next decision variable and branching on the value with the best objective bound (for optimization) and branches on the lower bound for SAT problems.static <V extends Variable>
AbstractStrategy<V>conflictOrderingSearch(AbstractStrategy<V> formerSearch)
Use the conflict ordering search as a pluggin to improve a former search heuristic Should be set after specifying a search strategy.static AbstractStrategy
defaultSearch(Model model)
Creates a default search strategy for the given model.static AbstractStrategy<IntVar>
domOverWDegSearch(IntVar... vars)
Assignment strategy which selects a variable according toDomOverWDeg
and assign it to its lower boundstatic AbstractStrategy
greedySearch(AbstractStrategy search)
Make the input search strategy greedy, that is, decisions can be applied but not refuted.static AbstractStrategy
ibexSolving(Model model)
Create a strategy which lets Ibex terminates the solving process for the CSP, once all integer variables have been instantiated.static IntStrategy
inputOrderLBSearch(IntVar... vars)
Assigns the first noninstantiated variable to its lower bound.static IntStrategy
inputOrderUBSearch(IntVar... vars)
Assigns the first noninstantiated variable to its upper bound.static IntStrategy
intVarSearch(VariableSelector<IntVar> varSelector, IntValueSelector valSelector, DecisionOperator<IntVar> decisionOperator, IntVar... vars)
Builds your own search strategy based on binary decisions.static IntStrategy
intVarSearch(VariableSelector<IntVar> varSelector, IntValueSelector valSelector, IntVar... vars)
Builds your own assignment strategy based on binary decisions.static AbstractStrategy<IntVar>
intVarSearch(IntVar... vars)
Builds a default search heuristics of integer variables Variable selection relies ondomOverWDegSearch(IntVar...)
Value selection relies on InDomainBest for optimization and InDomainMin for satisfactionstatic <V extends Variable>
AbstractStrategy<V>lastConflict(AbstractStrategy<V> formerSearch)
Use the last conflict heuristic as a pluggin to improve a former search heuristic Should be set after specifying a search strategy.static <V extends Variable>
AbstractStrategy<V>lastConflict(AbstractStrategy<V> formerSearch, int k)
Use the last conflict heuristic as a pluggin to improve a former search heuristic Should be set after specifying a search strategy.static IntStrategy
minDomLBSearch(IntVar... vars)
Assigns the noninstantiated variable of smallest domain size to its lower bound.static IntStrategy
minDomUBSearch(IntVar... vars)
Assigns the noninstantiated variable of smallest domain size to its upper bound.static AbstractStrategy<IntVar>
objectiveStrategy(IntVar objective, OptimizationPolicy optPolicy)
Defines a branching strategy over the objective variable Note that it is only activated after a first solution.static IntStrategy
randomSearch(IntVar[] vars, long seed)
Randomly selects a variable and assigns it to a value randomly taken in  the domain in case the variable has an enumerated domain  {LB,UB} (one of the two bounds) in case the domain is boundedstatic RealStrategy
realVarSearch(double epsilon, RealVar... reals)
strategy to branch on real variables by choosing sequentially the next variable domain to split in two, wrt the middle value.static RealStrategy
realVarSearch(VariableSelector<RealVar> varS, RealValueSelector valS, boolean leftFirst, RealVar... rvars)
Generic strategy to branch on real variables, based on domain splitting.static RealStrategy
realVarSearch(VariableSelector<RealVar> varS, RealValueSelector valS, double epsilon, boolean leftFirst, RealVar... rvars)
Generic strategy to branch on real variables, based on domain splitting.static RealStrategy
realVarSearch(RealVar... reals)
strategy to branch on real variables by choosing sequentially the next variable domain to split in two, wrt the middle value.static AbstractStrategy
sequencer(AbstractStrategy... searches)
Apply sequentialy enumeration strategies.static SetStrategy
setVarSearch(VariableSelector<SetVar> varS, SetValueSelector valS, boolean enforceFirst, SetVar... sets)
Generic strategy to branch on set variablesstatic SetStrategy
setVarSearch(SetVar... sets)
strategy to branch on sets by choosing the first unfixed variable and forcing its first unfixed value



Method Detail

lastConflict
public static <V extends Variable> AbstractStrategy<V> lastConflict(AbstractStrategy<V> formerSearch)
Use the last conflict heuristic as a pluggin to improve a former search heuristic Should be set after specifying a search strategy. Returns:
 last conflict strategy

bestBound
public static AbstractStrategy<IntVar> bestBound(AbstractStrategy<IntVar> formerSearch)
Search heuristic combined with a constraint performing strong consistency on the next decision variable and branching on the value with the best objective bound (for optimization) and branches on the lower bound for SAT problems. BEWARE: ONLY FOR INTEGERS (lets the former search work for other variable types) Parameters:
formerSearch
 default search to branch on variables (defines the variable selector and the value selector when this does not hold) Returns:
 best bound strategy

lastConflict
public static <V extends Variable> AbstractStrategy<V> lastConflict(AbstractStrategy<V> formerSearch, int k)
Use the last conflict heuristic as a pluggin to improve a former search heuristic Should be set after specifying a search strategy. Parameters:
k
 the maximum number of conflicts to store Returns:
 last conflict strategy

conflictOrderingSearch
public static <V extends Variable> AbstractStrategy<V> conflictOrderingSearch(AbstractStrategy<V> formerSearch)
Use the conflict ordering search as a pluggin to improve a former search heuristic Should be set after specifying a search strategy. Returns:
 last conflict strategy

greedySearch
public static AbstractStrategy greedySearch(AbstractStrategy search)
Make the input search strategy greedy, that is, decisions can be applied but not refuted. Parameters:
search
 a search heuristic building branching decisions Returns:
 a greedy form of search

sequencer
public static AbstractStrategy sequencer(AbstractStrategy... searches)
Apply sequentialy enumeration strategies. Strategies are considered in input order. When strategy i returns null (all variables are instantiated) the i+1 ones is activated. Parameters:
searches
 ordered set of enumeration strategies

setVarSearch
public static SetStrategy setVarSearch(VariableSelector<SetVar> varS, SetValueSelector valS, boolean enforceFirst, SetVar... sets)
Generic strategy to branch on set variables Parameters:
varS
 variable selection strategyvalS
 integer selection strategyenforceFirst
 branching order true = enforce first; false = remove firstsets
 SetVar array to branch on Returns:
 a strategy to instantiate sets

setVarSearch
public static SetStrategy setVarSearch(SetVar... sets)
strategy to branch on sets by choosing the first unfixed variable and forcing its first unfixed value Parameters:
sets
 variables to branch on Returns:
 a strategy to instantiate sets

realVarSearch
public static RealStrategy realVarSearch(VariableSelector<RealVar> varS, RealValueSelector valS, double epsilon, boolean leftFirst, RealVar... rvars)
Generic strategy to branch on real variables, based on domain splitting. A real decision is like: left branch: X ≤ v
 right branch: X ≥ v + e
 Parameters:
varS
 variable selection strategyvalS
 strategy to select where to split domainsepsilon
 gap for refutationrvars
 RealVar array to branch onleftFirst
 select left range first Returns:
 a strategy to instantiate reals

realVarSearch
public static RealStrategy realVarSearch(double epsilon, RealVar... reals)
strategy to branch on real variables by choosing sequentially the next variable domain to split in two, wrt the middle value. A real decision is like: left branch: X ≤ v
 right branch: X ≥ v + e
 Parameters:
epsilon
 gap for refutationreals
 variables to branch on Returns:
 a strategy to instantiate real variables

realVarSearch
public static RealStrategy realVarSearch(VariableSelector<RealVar> varS, RealValueSelector valS, boolean leftFirst, RealVar... rvars)
Generic strategy to branch on real variables, based on domain splitting. A real decision is like: left branch: X ≤ v
 right branch: X ≥ v + epsilon
 Parameters:
varS
 variable selection strategyvalS
 strategy to select where to split domainsleftFirst
 select left range firstrvars
 RealVar array to branch on Returns:
 a strategy to instantiate reals

realVarSearch
public static RealStrategy realVarSearch(RealVar... reals)
strategy to branch on real variables by choosing sequentially the next variable domain to split in two, wrt the middle value. A real decision is like: left branch: X ≤ v
 right branch: X ≥ v +
Double.MIN_VALUE
 Parameters:
reals
 variables to branch on Returns:
 a strategy to instantiate real variables

intVarSearch
public static IntStrategy intVarSearch(VariableSelector<IntVar> varSelector, IntValueSelector valSelector, DecisionOperator<IntVar> decisionOperator, IntVar... vars)
Builds your own search strategy based on binary decisions. Parameters:
varSelector
 defines how to select a variable to branch on.valSelector
 defines how to select a value in the domain of the selected variabledecisionOperator
 defines how to modify the domain of the selected variable with the selected valuevars
 variables to branch on Returns:
 a custom search strategy

intVarSearch
public static IntStrategy intVarSearch(VariableSelector<IntVar> varSelector, IntValueSelector valSelector, IntVar... vars)
Builds your own assignment strategy based on binary decisions. Selects a variable X and a value V to make the decision X = V. Note that value assignments are the public static decision operators. Therefore, they are not mentioned in the search heuristic name. Parameters:
varSelector
 defines how to select a variable to branch on.valSelector
 defines how to select a value in the domain of the selected variablevars
 variables to branch on Returns:
 a custom search strategy

intVarSearch
public static AbstractStrategy<IntVar> intVarSearch(IntVar... vars)
Builds a default search heuristics of integer variables Variable selection relies ondomOverWDegSearch(IntVar...)
Value selection relies on InDomainBest for optimization and InDomainMin for satisfaction Parameters:
vars
 variables to branch on Returns:
 a default search strategy

domOverWDegSearch
public static AbstractStrategy<IntVar> domOverWDegSearch(IntVar... vars)
Assignment strategy which selects a variable according toDomOverWDeg
and assign it to its lower bound Parameters:
vars
 list of variables Returns:
 assignment strategy

activityBasedSearch
public static AbstractStrategy<IntVar> activityBasedSearch(IntVar... vars)
Create an Activity based search strategy."ActivityBased Search for BlackBox Constraint Propagramming Solver", Laurent Michel and Pascal Van Hentenryck, CPAIOR12.
Uses public static parameters (GAMMA=0.999d, DELTA=0.2d, ALPHA=8, RESTART=1.1d, FORCE_SAMPLING=1) Parameters:
vars
 collection of variables Returns:
 an Activity based search strategy.

randomSearch
public static IntStrategy randomSearch(IntVar[] vars, long seed)
Randomly selects a variable and assigns it to a value randomly taken in  the domain in case the variable has an enumerated domain  {LB,UB} (one of the two bounds) in case the domain is bounded Parameters:
vars
 list of variablesseed
 a seed for random Returns:
 assignment strategy

objectiveStrategy
public static AbstractStrategy<IntVar> objectiveStrategy(IntVar objective, OptimizationPolicy optPolicy)
Defines a branching strategy over the objective variable Note that it is only activated after a first solution. This should be completed with another strategy with a larger scope. Parameters:
objective
 objective variableoptPolicy
 policy to adopt for the optimization process Returns:
 a assignment strategy

inputOrderLBSearch
public static IntStrategy inputOrderLBSearch(IntVar... vars)
Assigns the first noninstantiated variable to its lower bound. Parameters:
vars
 list of variables Returns:
 int strategy based on value assignments

inputOrderUBSearch
public static IntStrategy inputOrderUBSearch(IntVar... vars)
Assigns the first noninstantiated variable to its upper bound. Parameters:
vars
 list of variables Returns:
 assignment strategy

minDomLBSearch
public static IntStrategy minDomLBSearch(IntVar... vars)
Assigns the noninstantiated variable of smallest domain size to its lower bound. Parameters:
vars
 list of variables Returns:
 assignment strategy

minDomUBSearch
public static IntStrategy minDomUBSearch(IntVar... vars)
Assigns the noninstantiated variable of smallest domain size to its upper bound. Parameters:
vars
 list of variables Returns:
 assignment strategy

defaultSearch
public static AbstractStrategy defaultSearch(Model model)
Creates a default search strategy for the given model. This heuristic is complete (handles IntVar, BoolVar, SetVar and RealVar) Parameters:
model
 a model requiring a default search strategy

ibexSolving
public static AbstractStrategy ibexSolving(Model model)
Create a strategy which lets Ibex terminates the solving process for the CSP, once all integer variables have been instantiated.
Note that if the system is not constrained enough, there can be an infinite number of solutions.
For example, solving the function
x,y in [0.0,1.0] with
x + y = 1.0
will return x,y in [0.0,1.0] and not a single solution.If one wants a unique solution, calling
realVarSearch(RealVar...)
should be considered. Parameters:
model
 declaring model Returns:
 a strategy that lets Ibex terminates the solving process.

