The final component of this example is the metaheuristic that implements the tabu search. We implement a very simple tabu search where the MyTabuI class maintains a circular list of the last 10 moves that have been performed. A possible move suggested by the neighborhood is disallowed if it is the reverse of a move that is on the tabu list. The only exception to this rule is if the move results in a solution with a cost that is lower than the best solution that has been found so far.

Five of the virtual functions from the IloMetaHeuristicI class are redefined in our implementation. See the IBM ILOG Solver Reference Manual and IBM ILOG Solver User's Manual for a detailed description of the purpose of each of these methods.

Two of the redefined methods (reset and start) are very simple: the former resets the _bestCost to IloInfinity and empties the tabu list while the latter simply records the cost of the current solution if it is lower than any solution encountered so far.

We look more deeply at each of the other methods.

First, the test method is called by the local search protocol to determine if a move suggested by the neighborhood should be disallowed. If so, the function returns IloFalse and otherwise (that is, if the move is acceptable), IloTrue is returned. Our implementation first checks to see if the solution has a cost lower than any solution seen so far and, if so, accepts the move. Otherwise the tabu list is checked to see if the delta solution is the reverse of a move that is on the tabu list. If so, the move is rejected. Otherwise the move is accepted.

IloBool MyTabuI::test(IloSolver solver, IloSolution delta) {
  if (solver.getMin(_costVar) < _bestCost)
    return IloTrue;

  for(IloInt i = 0; i < _nbTabuEles; ++i) {
    if ((_tabuList[i] != 0) && _tabuList[i]->isReverseMove(delta))
      return IloFalse;
  }

  return IloTrue;
}

Second, the notify method is called whenever the local search protocol accepts a new move. What we need to do therefore is to add the new move to our tabu list. To do this, we make use of the findSwapFromDelta method described above and then add the move to the circular tabu list.

void MyTabuI::notify(IloSolver solver, IloSolution delta) {
  SwapRC *move = SwapRC::findSwapFromDelta(solver, delta);
  assert(move != 0);

  _tabuList[_nextTabuEle] = move;
  
  _nextTabuEle++;
  _nextTabuEle %= _maxTabuSize;

  if (_nbTabuEles < _maxTabuSize)
    _nbTabuEles++;
}

The final metaheuristic function is complete. This function is called by the local search in the situation where all possible moves are either infeasible or rejected by the test method. If this method returns IloTrue, the local search is ended. In our case, we simply age the tabu list by replacing the oldest element in the list by the youngest. This will have the effect of allowing one more possible neighbor than was allowed in the previous state. If all the elements in the tabu list are equal to the youngest element, we return IloTrue.

IloBool MyTabuI::complete() {
  // Remove the element that has been in the list the longest
  // time. Insert the youngest element in its place.
  IloInt youngest = _nextTabuEle - 1;
  if (youngest < 0)
    youngest = _nbTabuEles - 1;

  if ((youngest < 0) || 
      (_tabuList[youngest] == _tabuList[_nextTabuEle]))
    return IloTrue;

  _tabuList[_nextTabuEle] = _tabuList[youngest];

  _nextTabuEle++;
  _nextTabuEle %= _maxTabuSize;

  return IloFalse;
}