We can modify our map coloring problem to use solution deltas, as opposed to modifying the solution directly. We address only the local search part of the code that appears after the creation of the solution object and the generation of the initial solution.

From any current solution, we know that there are 6 possible changes that can be made, one corresponding to each country. To represent this, we create an array of solutions to act as solution deltas:

    IloSolutionArray deltas(env, 6);

The deltas are then created:

    for (IloInt i = 0; i < 6; i++) {
      deltas[i] = IloSolution(env);
      deltas[i].add(AllVars[i]);
      deltas[i].setValue(AllVars[i], 1 - soln.getValue(AllVars[i]));
    }

The variable deltas[i] represents a change of color for country i. Each delta contains a variable whose saved value is a different color from that stored in the current solution.

We define the goal to attempt a move in stages. In the first stage, a goal explores the possible changes that can be applied to the solution (that is, explores the neighborhood):

    IloNeighborIdentifier nid(env);
    IloGoal scan = IloScanDeltas(env, soln, deltas, nid);

IloScanDeltas takes a solution and an array of solution deltas, and applies each delta to the solution in turn. For each delta to be examined, each one that can be applied legally results in a leaf node of IloScanDeltas. The variable nid is a neighbor identifier. This class is used by IloScanDeltas to communicate information back to the user about the solution delta representing the current variable instantiation. Both the index of the delta and the delta itself can be accessed from the solver using solver.getAtIndex(nid) and solver.getAtDelta(nid).

Next, one neighbor is chosen from those available. A search selector is used which selects the first legal neighbor found:

    IloGoal selectNeighbor = IloSelectSearch(env, scan, IloFirstSolution(env));

Finally, we construct the goal that moves to the chosen neighbor, as follows:

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

The first term of the composed goal states that the objective value must be increased from its current value. The second term examines all deltas and selects a single change to be made, if a legal one exists. At this point, the decision variables AllVars are instantiated with the new solution. The third element stores the new solution. Now the local search optimization loop is performed. The loop terminates when no moves can be taken. This happens when IloScanDeltas fails because none of the available deltas can legally be applied.

    IloIIM iim(solver);
    while (solver.solve(move)) {
      solver.out() << "Move made:    Objective value = "
                   << soln.getObjectiveValue() << endl;
      IloInt atIndex = iim.getAtIndex(nid);
      IloIntVar var = AllVars[atIndex];
      deltas[atIndex].setValue(var, 1 - deltas[atIndex].getValue(var));
    }

Whenever the constrained variables of the problem are instantiated by IloScanDeltas, IloScanDeltas assures that the neighbor identifier nid contains information on the delta itself. We get the index of this delta using solver.getAtIndex(nid). We then flip the value of the variable stored in deltas[atIndex], which maintains it in the opposite sense from what is stored in the current solution. This ensures that future moves can change the value of the relevant variable once more.

When the optimization loop is over, the solution found is presented:

    solver.solve(IloRestoreSolution(env, soln));

Functionally, this search is identical to the previous version which directly manipulates the solution. However, the use of IloScanDeltas is preferred to testing each delta in turn via IloRestoreSolution as it is much more efficient when large numbers of deltas are being tested.