Here is the synopsis of the class BubbleI, which is subclassed from IloNHoodI:

class BubbleI : public IloNHoodI {
private:
  IloSolution    _soln;
  IloIntVarArray _perm;
  IloIntArray    _values;
  IloIntVar      _cost;
  IloInt         _costVal;
  IloInt         _startPoint;
public:
  BubbleI(IloEnv env,
          IloIntVarArray perm,
          IloIntArray values,
          IloIntVar cost,
          const char *name = 0);
  void start(IloSolver solver, IloSolution soln);
  IloSolution define(IloSolver solver, IloInt i);
  IloInt getSize(IloSolver solver) const;
  void notify(IloSolver solver, IloInt i);
  void notifyOther(IloSolver solver, IloSolution delta);
  void reset();
};

The class BubbleI--local variables

The BubbleI class is subclassed from IloNHoodI and implements our "Bubble Sort" neighborhood. The local variables have the following functions:

_soln

This is the solution passed in the last call to start().

_perm

This is the permutation array which holds the decision variables of the local search process. These are the variables which will be mentioned in the neighbors generated.

_values

This is the original array of values to sort.

_cost

This is the cost variable of the sorting problem. We pass this here so that we can specify cost bounds in generated deltas. This is better than taking the objective variable from _soln as the local search could be optimizing something different from just the cost of the sorting problem. For example, it could be optimizing a problem where cost is only a part.

_costVal

This is the value of the cost variable the last time the solution was saved. A sentinel value of IloIntMax means that no move has been made as yet. No cost bounds will be imposed in the first iteration of the search. This is not usually a significant performance problem.

_startPoint

This is the index in the _perm array that the neighbor indexed zero corresponds to. Definition starts from that point.

The class BubbleI--constructor

The constructor sets up the base class and initializes its data members. Note that _costVal is set to IloIntMax and _startPoint to zero. These are the variables which represent the state of the neighborhood.

BubbleI::BubbleI(IloEnv env,
                 IloIntVarArray perm,
                 IloIntArray values,
                 IloIntVar cost,
                 const char *name)
: IloNHoodI(env, name),
  _soln(),
  _perm(perm),
  _values(values),
  _cost(cost),
  _costVal(IloIntMax),
  _startPoint(0) { }

The class BubbleI--member functions

The reset member function resets the variables that represent the state of the neighborhood, _costVal and _startPoint, to their original values.

void BubbleI::reset() {
  _costVal = IloIntMax;
  _startPoint = 0;
}

The start member function simply keeps a reference to the current solution.

void BubbleI::start(IloSolver, IloSolution soln) {
  _soln = soln;
}

The define member function returns a delta which swaps the values of two adjacent variables from the _perm array. The index is first offset by _startPoint.

IloSolution BubbleI::define(IloSolver solver, IloInt i) {
  i = (i + _startPoint) % (_perm.getSize() - 1);

Now the move is created by adding the variables which will change, together with their new values, to a delta. One point should be borne in mind when you return a delta from define. IloScanNHood automatically destroys this delta when it has no more use for it--you do not have to handle the memory management yourself. This also means that you should not keep any references to deltas returned from define, as these are not guaranteed to be valid thereafter. It is also legal to return an empty handle from define if you do not wish a neighbor to be defined for this index.

After the delta is created, the two adjacent variables are added. Their values are set to those in _soln (the old values), but swapped over.

  IloSolution delta(solver.getEnv());
  delta.add(_perm[i]);
  delta.add(_perm[i + 1]);
  IloInt oldLeft = _soln.getValue(_perm[i]);
  IloInt oldRight = _soln.getValue(_perm[i + 1]);
  delta.setValue(_perm[i], oldRight);
  delta.setValue(_perm[i + 1], oldLeft);

Finally, if _costVal does not hold its sentinel value, we compute the new cost of the move. Simply, the cost increases by one if the move puts the values in the wrong order when they were in the correct order before, and decreases by one in the other situation.

  if (_costVal != IloIntMax) {
    IloInt diff = (_values[oldLeft] < _values[oldRight])
                - (_values[oldLeft] > _values[oldRight]);
    delta.add(_cost);
    delta.setValue(_cost, _costVal + diff);
  }

  return delta;
}

The size of the neighborhood is one less than the number of values to sort, as adjacent pairs are examined from pair {0, 1} up to pair {_perm.getSize()-2, _perm.getSize()-1}.

IloInt BubbleI::getSize(IloSolver) const {
  return _perm.getSize() - 1;
}

In notify() we store the new starting point of the neighborhood as the one after the neighbor being notified. We reduce this value modulo the size of the neighborhood. We also store the cost of the current sorting configuration.

void BubbleI::notify(IloSolver solver, IloInt i) {
  _startPoint = (i + 1 + _startPoint) % (_perm.getSize() - 1);
  _costVal = (IloInt)solver.getValue(_cost);
}

We store the cost of the current sorting configuration in notifyOther.

void BubbleI::notifyOther(IloSolver solver, IloSolution) {
  _costVal = (IloInt)solver.getValue(_cost);
}

The following function returns the "Bubble Sort" neighborhood. The new neighborhood is allocated on the same environment as is passed to it. This is important as the delete operator of IloNHoodI (called via IloNHood::end) frees the allocated memory from the env. If you allocate your subclass of IloNHoodI on a different heap, you must define a delete operator in your subclass.

IloNHood Bubble(IloEnv env,
                IloIntVarArray perm,
                IloIntArray values,
                IloIntVar cost,
                const char *name = 0) {
  return new (env) BubbleI(env, perm, values, cost, name);
}

Main program

To begin the program, we define an environment, a solver, a model, and a random number generator. The latter will be used to generate the values to sort.

int main()
{
  IloEnv env;
  try {
    IloSolver solver(env);
    IloModel m(env);
    IloRandom r(env, 54321);

We now generate twenty values to sort, displaying them after they have been generated.

    IloInt n = 20;
    IloIntArray values(env, n);
    IloInt i;
    for (i = 0; i < n; i++)
      values[i] = r.getInt(1000);
    cout << values << endl;

The permutation array is created, as well as an array to hold the 0-1 cost of each pair of variables in the perm array. An all-different constraint is added to the model to ensure that the values of perm really are a permutation (no repeated values). The total cost is formed from the sum of the 0-1 cost variables.

    IloIntVarArray perm(env, n, 0, n - 1);
    IloConstraint allDiff = IloAllDiff(env, perm);
    m.add(allDiff);
    IloIntVarArray costs(env, n * (n - 1) / 2, 0, 1);
    IloInt k = 0;
    for (i = 0; i < n - 1; i++) {
      for (IloInt j = i + 1; j < n; j++) {
        m.add(costs[k] == (values(perm[i]) > values(perm[j])));
        k++;
      }
    }
    IloIntVar cost(env, 0, n * (n - 1) / 2);
    m.add(cost == IloSum(costs));

The initial solution to the sorting problem is created along with the solution to be used during local search. We add all the variables in perm to the solution, and the objective. We extract the model and find a first solution using the IloGenerate goal. We then store the solution and display it. The all-different constraint is then removed from the model as it is no longer needed. The "Bubble Sort" neighborhood only swaps values and so cannot violate this constraint.

    solver.extract(m);
    IloGoal g = IloGenerate(env, perm);
    IloSolution soln(env);
    soln.add(perm);
    soln.add(IloMinimize(env, cost));
    solver.solve(g);
    soln.store(solver);
    cout << "---" << endl;
    Display(solver, perm, values, cost);
    m.remove(allDiff);

The neighborhood is created along with the goal which will perform a single move. Then a typical local search optimization loop is entered, continuing until no move can be made, or until the cost value is reduced to zero.

    IloNHood nhood = Bubble(env, perm, values, cost);
    IloGoal move = IloSingleMove(env, soln, nhood, IloImprove(env));
    while (soln.getObjectiveValue() != 0 && solver.solve(move))
    ;

The final solution is restored and displayed.

    solver.solve(IloRestoreSolution(env, soln));
    cout << "---" << endl;
    Display(solver, perm, values, cost);
  } catch (IloException e) {
    cout << "Caught: " << e << endl;
  }
  env.end();
  return 0;
}