We shall define a neighborhood specifically tailored to sorting. The idea of this neighborhood is to swap elements of the array which are adjacent, as in the classic "Bubble Sort" algorithm. We shall also include some other features which demonstrate how more complex behavior can be achieved.

Features of the "Bubble Sort" neighborhood

Our "Bubble Sort" neighborhood has three main features:

Virtual functions of IloNHoodI

The virtual functions of IloNHoodI, with the exception of reset, are all called from the IloScanNHood goal (or via IloScanNHood by IloSingleMove) and are passed an instance of IloSolver. This instance of IloSolver is the one executing IloScanNHood.

To define a neighborhood, the following virtual functions are available:

virtual void start(IloSolver solver, IloSolution soln)

The IloNHoodI::start method is called to signify to the neighborhood that neighbors will be requested of it, the root of these neighbors being the solution soln.

For our "Bubble Sort" neighborhood, we need to store a reference to the solution so that we can generate neighbors with it as a reference.

virtual IloInt getSize(IloSolver solver) const = 0

The IloNHoodI::getSize method asks the neighborhood to return the number of neighbors of which it is comprised. The neighborhood should be prepared to define neighbors with indices from 0 to s-1 where s is the value returned.

Since our "Bubble Sort" neighborhood exchanges only two adjacent cells, its size will be n-1 where n is the size of the array to be sorted.

virtual IloSolution define(IloSolver solver, IloInt i) = 0

The IloNHoodI::define method is called to retrieve a particular neighbor of the neighborhood. The index i represents the index of the neighbor being requested, where neighbors are indexed from 0 upwards.

For our "Bubble Sort" neighborhood the definition of a neighbor mentions two adjacent variables of the permutation array, with values swapped from their values in the previous solution. As mentioned previously, we also add cost bounds to increase efficiency.

virtual void notify(IloSolver solver, IloInt i)

When a neighborhood move is about to be taken, the IloNHoodI::notify() method is called. This function supplies the index i to tell the neighborhood which neighbor is accepted.

For our "Bubble Sort" neighborhood, we can use the IloNHoodI::notify member function to identify the previous move made, and use it in the definition of subsequent moves such that a different part of the neighborhood is explored. It is also an ideal place to capture the cost of the current instantiation so that we can compute cost differences from it in subsequent moves.

virtual void notifyOther(IloSolver solver, IloSolution delta)

When a move is about to be taken, but this neighborhood did not generate it, IloNHoodI::notifyOther is called on the neighborhood. This call is generated from IloNHoodI::notify() method of the IloConcatenate neighborhood (same as operator +) for the neighborhoods that did not define the move being taken. delta is the solution delta of the move.

Here, as in notify, we can capture the cost of the current instantiation so that we can compute cost differences from it in subsequent moves. In the context of the example, where the "Bubble Sort" neighborhood is the only one, notifyOther is never called, as no other neighborhood could perform the move. However, defining notifyOther here is good design practice, so the neighborhood could be used in a different context later.

virtual void reset();

This method can be called by the user (indirectly through the handle class IloNHood) to reset any internal state of the neighborhood to that at its creation.

For the "Bubble Sort" neighborhood, two items of internal state need to be reset: the cost of the previous solution, and the index of the last neighbor accepted.

Defining the "Bubble Sort" neighborhood

The following function displays the permuted array and its cost. The values of perm are retrieved from the algorithm via solver.getValue.

void Display(IloSolver solver,
             IloIntVarArray perm,
             IloIntArray values,
             IloIntVar cost) {
  cout << solver.getIntVarArray(perm) << endl;
  cout << solver.getIntVar(cost) << endl;
  for (IloInt i = 0; i < values.getSize(); i++) {
    cout << values[solver.getValue(perm[i])] << " ";
  }
  cout << endl;
}