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 non-instantiated variable to its lower bound.static IntStrategy
inputOrderUBSearch(IntVar... vars)
Assigns the first non-instantiated 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 non-instantiated variable of smallest domain size to its lower bound.static IntStrategy
minDomUBSearch(IntVar... vars)
Assigns the non-instantiated 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)
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)
-
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."Activity-Based Search for Black-Box 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 non-instantiated 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 non-instantiated variable to its upper bound.- Parameters:
vars
- list of variables- Returns:
- assignment strategy
-
minDomLBSearch
public static IntStrategy minDomLBSearch(IntVar... vars)
Assigns the non-instantiated 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 non-instantiated 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.
-
-