Sometimes, however, you not only want a solution to a problem but a solution that optimizes a given criterion. For that purpose, Solver offers predefined ways to get solutions that minimize or maximize an objective. The technique used by Solver is widely known as branch & bound.

In Solver, you search for an optimal solution in three steps:

In this section, you will model this same problem, map coloring with minimum colors, using the function IloMinimize and a search loop. You will learn more about how Solver uses objectives and how the member functions IloSolver::startNewSearch, IloSolver::restartSearch and IloSolver::next work when used with an objective to search for an optimal solution.

In this version, the objective is the maximum color used (since you number the colors). You define it by using IloMax on the array of colors. You want each modification of this maximum to be propagated to the other variables, and any modification of a color variable to be propagated to the maximum as well. More generally, it is essential to link the cost variable to the other variables in the problem by means of constraints, not mere tests.

Constraints differ from tests in an important way: once a constraint has been posted, effects of the constraint are propagated to reduce the domains of all variables affected by the constraint in ways that a mere test does not have. In this example, since you are using constraints rather than tests to link the objective to other variables, the choices made about the other variables are propagated to the cost variable with absolute accuracy, and the modification of the objective impinges on the other variables as soon as possible. These two ideas are critical so that as soon as possible the minimization process eliminates parts of the search tree that will not produce better solutions.

The function IloMinimize takes a constant or expression as its argument. This constant or expression becomes the objective to be minimized. This member function changes the behavior of IloSolver::next, like this:

In other words, each time next is called, the new solution will yield a better value for the objective. The last solution found is the optimal solution.

In this version, to find a solution using the least number of colors, you use IloMinimize and loop to find better and better solutions. As you do so, you print the cost you get for each solution.

This loop actually produces a series of solutions, ending with an optimal solution. The last call of next in that loop searches for a solution better than the optimal, and it consequently fails. Having failed, it backtracks, and unfortunately the optimal solution is lost.

What shall you do to retain that last optimal solution, that was inadvertently "lost" during backtracking? Easy: in the last part of the program, you search again for the best solution found so far. To do that, you first call IloSolver::restartSearch in order to restart the search, and then you search for exactly one solution. The member function restart keeps track of the best objective value found. In that way, you insure that you find the optimal solution again.

Here is how you model the objective for this version of the problem.

    IloNumVarArray AllVars(env, 6, Belgium, Denmark, France,
                           Germany, Netherlands, Luxembourg);
    model.add(IloMinimize(env, IloMax(AllVars)));

The output of the program looks like this:

OPTIMAL Solution
Belgium:     white
Denmark:     blue
France:      blue
Germany:     white
Netherlands: blue
Luxembourg:  red