Backtracking

Backtracking occurs when there is a failure in a goal and goal execution resumes at the most recent choice point with untried subgoals.

Within CP Optimizer search, the implicit generation of combinations of values for decision variables uses constructive search strategies. A constructive strategy attempts to build a solution by choosing a non-fixed decision variable and a value for this variable. The chosen variable is then fixed to the chosen value and constraint propagation is triggered. This operation is called branching, and the fixing is also called a “branch”. Constraint propagation then reduces the domains of variables and, consequently, the currently possible combinations. After propagation terminates, another non-fixed variable, if one exists, is chosen, and the process repeats until all decision variables are fixed. However, if a fixing fails because it cannot lead to a solution, the constructive strategy backtracks and chooses another value for the variable.

The fixing of a decision variable must be seen as a guess: if it leads to inconsistencies, it should be undone, and another value should be tried. CP Optimizer implements these guesses and “undos” by using choice points. Choice points are implemented at the search level in CP Optimizer by the function IlcOr. A choice point defines a goal in terms of a choice between subgoals.

CP Optimizer executes a choice point between two or more subgoals like this:

• The state of CP Optimizer (including the state of all variables and constraints and the state of the goal stack) is saved, so that it can be restored if needed. This is called setting the choice point.

• The first subgoal is pushed onto the top of the goal stack.

• The other subgoals are saved as untried subgoals for the choice point.

• Then the first subgoal is popped from the goal stack and executed. If this subgoal fails, the state of CP Optimizer is restored, and the first untried choice is pushed onto the goal stack. This activity is called backtracking, and it continues until a subgoal is found that succeeds.

• If all subgoals fail, the choice point itself fails.

When the function IloCP::fail is called, goal execution resumes at the most recent choice point with untried subgoals. It is possible to make goal execution resume at an earlier choice point if you associate labels with choice points. Then the function IloCP::fail can be called with a label. In such a case, goal execution resumes at the most recent choice point having the same label.