title | date | weight | math | description |
---|---|---|---|---|
Search Strategies |
2020-01-07 16:06:55 +0100 |
33 |
true |
How to define search strategies?
|
The search space induced by variable domains is equal to
NOTE: There are many ways to explore the search space and this steps should not be overlooked. Search strategies or heuristics have a strong impact on resolution performances. Thus, it is strongly recommended to adapt the search space exploration to the problem treated.
If no search strategy is specified to the resolver, Choco 4 will rely on the default one (defined by a defaultSearch
in Search
).
In many cases, this strategy will not be sufficient to produce satisfying performances and it will be necessary to specify a dedicated strategy, using solver.setSearch(...)
.
The default search strategy splits variables according to their type and defines specific search strategies for each type that are sequentially applied:
-
integer variables and boolean variables :
intVarSearch(ivars)
(callsdomOverWDegSearch
) -
set variables:
setVarSearch(svars)
-
real variables
realVarSearch(rvars)
-
objective variable, if any: lower bound or upper bound, depending on the optimization direction
Note that lastConflict is also plugged-in.
You may specify a search strategy to the resolver by using solver.setSearch(...)
method as follows:
import static org.chocosolver.solver.search.strategy.Search.*;
// to use the default SetVar search on mySetVars
Solver s = model.getSolver();
s.setSearch(setVarSearch(mySetVars));
// to use activity based search on myIntVars
Solver s = model.getSolver();
s.setSearch(activityBasedSearch(myIntVars));
// to use activity based search on myIntVars
// then the default SetValSelectorFactoryVar search on mySetVars
Solver s = model.getSolver();
s.setSearch(activityBasedSearch(myIntVars), setVarSearch(mySetVars));
NOTE: Search strategies generally hold on some particular variable kinds only (e.g. integers, sets, etc.).
Let us consider we have two integer variables x
and y
and we want our strategy to select
the variable of smallest domain and assign it to its lower bound.
There are several ways to achieve this:
// 1) verbose approach using usual imports
import org.chocosolver.solver.search.strategy.Search;
import org.chocosolver.solver.search.strategy.assignments.DecisionOperatorFactory;
import org.chocosolver.solver.search.strategy.selectors.values.*;
import org.chocosolver.solver.search.strategy.selectors.variables.*;
Solver s = model.getSolver();
s.setSearch(Search.intVarSearch(
// selects the variable of smallest domain size
new FirstFail(model),
// selects the smallest domain value (lower bound)
new IntDomainMin(),
// apply equality (var = val)
DecisionOperatorFactory.makeIntEq(),
// variables to branch on
x, y
));
// 2) Shorter approach : Use a static import for Search
// and do not specify the operator (equality by default)
import static org.chocosolver.solver.search.strategy.Search.*;
import org.chocosolver.solver.search.strategy.selectors.values.*;
import org.chocosolver.solver.search.strategy.selectors.variables.*;
Solver s = model.getSolver();
s.setSearch(intVarSearch(
// selects the variable of smallest domain size
new FirstFail(model),
// selects the smallest domain value (lower bound)
new IntDomainMin(),
// variables to branch on
x, y
));
// 3) Shortest approach using built-in strategies imports
import static org.chocosolver.solver.search.strategy.Search.*;
Solver s = model.getSolver();
s.setSearch(minDomLBSearch(x, y));
Most available search strategies are listed in Search
.
This factory enables you to create search strategies using static methods.
Most search strategies rely on :
- variable selectors (see package
org.chocosolver.solver.search.strategy.selectors.values
) - value selectors (see package
org.chocosolver.solver.search.strategy.selectors.variables
) - operators (see
DecisionOperator
)
Search
is not exhaustive, look at the selectors package to see learn more search possibilities.
{{% alert title="Info" color="primary" %}} Note that some strategies are dynamic and might work more efficiently when combined with a [restart policy]({{< ref "Restarts.md" >}}). {{%/alert%}}