Search Strategies

The search space induced by variable domains is equal to $S=|d_1|\times|d_2|\times\cdots\times|d_n|$ where $d_i$ is the domain of the $i^{th}$ variable. Most of the time (not to say always), constraint propagation is not sufficient to build a solution, that is, to remove all values but one from variable domains. Thus, the search space needs to be explored using one or more search strategies. A search strategy defines how to explore the search space by computing decisions. A decision involves a variables, a value and an operator, e.g. $x = 5$, and triggers new constraint propagation. Decisions are computed and applied until all the variables are instantiated, that is, a solution has been found, or a failure has been detected (backtrack occurs). Choco 4.10.2 builds a binary search tree: each decision can be refuted (if $x = 5$ leads to no solution, then $x \neq 5$ is applied). The classical search is based on Depth First Search.

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.

Default search strategy

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:

1. integer variables and boolean variables : intVarSearch(ivars) (calls domOverWDegSearch)

2. set variables: setVarSearch(svars)

3. real variables realVarSearch(rvars)

4. objective variable, if any: lower bound or upper bound, depending on the optimization direction

Note that lastConflict is also plugged-in.

Specifying a search strategy

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

Example

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));

List of available search strategy

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.