After finding an initial solution, we next enter a local improvement phase. For that phase, we decide what changes to make to the solution to produce a new (changed) one.

In this example, there are only two available colors numbered zero (meaning blue) and one (meaning white). Thus, we can think of a simple change that can be made: change the color of one of the countries (from 0 to 1 or 1 to 0). This means that from any coloring, we can move to 6 other colorings (given our 6 countries). There are 6 possible changes that can be made. We therefore use an index to indicate which country should change color now:

    IloInt curr = 0;

If we try to change the color of all 6 countries without success, we can stop the search. We are at what is termed a local minimum. This means that no change can improve the cost of the solution. It is important to recognize that a local minimum is often not the optimum.

We maintain a counter which marks off how many color changes have failed since the last success, and repeat until no move has worked for six tries:

    IloInt failed = 0;
    while (failed < 6) {

Inside the main loop, we change the value of AllVars[curr] in the solution from 0 to 1 (blue to white) or 1 to 0 (white to blue).

      soln.setValue(AllVars[curr], 1 - soln.getValue(AllVars[curr]));

Now we are in a position to test the new solution for legality and to see if the cost is reduced over that of the current solution. If both of these conditions are satisfied, we save the resulting solution. This process is called making a local move. We construct a goal to perform these actions:

      IloGoal move = IloAddConstraint(obj >= soln.getObjectiveValue() + 1)
                  && IloRestoreSolution(env, soln)
                  && IloStoreSolution(env, soln);

This goal is made up of three parts. First, we assert that the new objective must be at least one more than the cost of the current solution. This is because we are maximizing. Then, we restore the solution, which means that the values of the constrained variables added to soln are placed into the constrained variables of the model. (The variables in AllVars will be assigned their values stored in soln.) Note that the value of the objective is not restored when a solution is restored, only the values of variables are. Normally, the value of the objective will be completely determined by the variables on which it depends. However, if this is not the case, a variable representing the objective can be added to the solution, which will result in its value being restored with the solution. In the last line of the move goal, the solution is stored again. Although this does not change the values of the variables AllVars as stored in the solution, it does store the new value of the objective.

We execute the goal, changing the chosen country back to its previous color if the color change was not successful in increasing the objective or if the color change violated any problem constraints.

      if (solver.solve(move)) {
        solver.out() << "Move made:    Objective value = "
                     << soln.getObjectiveValue() << endl;
        failed = 0;
      }
      else {
        soln.setValue(AllVars[curr], 1 - soln.getValue(AllVars[curr]));
        failed++;
      }

We then move to the next country to start the next loop:

      curr = (curr + 1) % 6;
    }

After the local search loop terminates (when no country's color could be changed to increase the objective), the solution found can be presented via:

    solver.solve(IloRestoreSolution(env, soln));
    print(solver, "Belgium:     ", Belgium); 
    print(solver, "Denmark:     ", Denmark); 
    print(solver, "France:      ", France); 
    print(solver, "Germany:     ", Germany); 
    print(solver, "Netherlands: ", Netherlands); 
    print(solver, "Luxembourg:  ", Luxembourg); 

In this small example, the solution delivered by local search is the optimal solution. One move is made by the local search procedure: changing the color of Luxembourg.