Constructive search

Along with constraint propagation, constructive search strategies are used by CP Optimizer in the search for solutions to constraint programming problems.

After initial constraint propagation, the search space is reduced. CP Optimizer will use a constructive search strategy to guide the search for a solution in the remaining part of the search space. It may help to think of the strategy as one that traverses a search tree. The root of the tree is the starting point in the search for a solution; each branch descending from the root represents an alternative in the search. Each combination of values in the search space can be seen as a leaf node of the search tree.

The CP Optimizer engine executes a search strategy that guides the search for a solution. The optimizer “tries” a value for a variable to see if this will lead to a solution. To demonstrate how the optimizer uses search strategies to find a solution, consider a search strategy that specifies that the optimizer should select variable x and assign it the lowest value in the domain of x. For the first search move in this strategy, the optimizer assigns the value 10 to the variable x. This move, or search tree branch, is not permanent. If a solution is not found with x = 10, then the optimizer can undo this move and try a different value of x.