Using an array of deltas to specify the possible neighbors of a solution is one step from directly manipulating the solution and restoring it, but maintaining the set of deltas can be laborious. Solver provides methods for describing neighborhoods in a more structured way. Using these neighborhoods makes it easier to define the neighbors of a solution. There are various predefined neighborhoods in Solver, and you can also define your own.

Just as IloScanDeltas was used to apply each delta to a solution, a goal IloScanNHood is used to apply each neighboring solution to the current one. We can use this goal in a further refinement to our map coloring example.

Instead of creating an array of deltas to represent the neighbors of a solution, we use the class IloNHood, a special class for defining neighborhoods. The predefined neighborhood IloFlip produces changes to 0-1 variables, which is exactly the type of neighborhood we require for our map coloring problem. We use that neighborhood here:

    IloNHood nhood = IloFlip(env, AllVars);

The goal that explores the neighborhood and selects the neighbor to be taken is defined as:

    IloNeighborIdentifier nid(env);
    IloGoal scan = IloScanNHood(env, nhood, nid, soln);
    IloGoal selectNeighbor = IloSelectSearch(env, scan, IloFirstSolution(env));

We use IloFirstSolution as we are interested in any legal neighbor. The nid parameter passed to IloScanNHood will be used for storing both the neighborhood index (numbered from 0 upwards) and the delta corresponding to any instantiated neighbor. Note that while for IloScanDeltas the index has a very obvious meaning (the index of the delta in the array specified), for IloScanNHood the index only has meaning to the neighborhood itself. This notion will become clearer later.

Then, the goal which attempts a change is defined as follows:

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

The goal is composed for four terms. In the first term the lower bound on the cost is set. In the next, the neighborhood is scanned and a neighbor selected. The third term uses the predefined Solver goal IloNotify. This goal takes as parameters a neighborhood and a neighborhood identifier. It indicates to the neighborhood, through the neighborhood identifier, the index of the neighbor that is about to be taken. (Such notification is important for neighborhoods which may change their behavior on subsequent scans depending on which moves have been taken. Full details on this are given in the section "Writing your own neighborhood" later in this chapter.) Finally, the fourth term stores the solution.

Finally, we use the following optimization loop:

    while (solver.solve(move)) {
      solver.out() << "Move made:    Objective value = "
                   << soln.getObjectiveValue() << endl;
    }

The remainder of the code is the same as before. The result is code that is functionally equivalent to the code using IloScanDeltas, although its complexity is reduced. The efficiency of the code is also approximately the same.