Here is the synopsis of the class LimitedTabuI:

class LimitedTabuI: public IloMetaHeuristicI {
private:
  IloNumVar   _previousVar;
  IloNum      _previousValue;
  IloNum      _gap;
  IloNum      _bestCost;
  IloSolution _soln;
public:
  LimitedTabuI(IloEnv env, IloNum gap, const char *name = 0);
  IloBool complete();
  IloBool isFeasible(IloSolver, IloSolution delta) const;
  void notify(IloSolver solver, IloSolution delta);
  void reset();
  IloBool start(IloSolver solver, IloSolution soln);
};

The class LimitedTabuI--local variables

The LimitedTabuI class is subclassed from IloMetaHeuricticI and implements our "limited tabu search" metaheuristic. The local variables have the following functions:

_previousVar

This variable holds the variable which was changed on the last move and which cannot change at this move. If this variable is an empty handle, it indicates that either the metaheuristic has just been created or reset, or that no variable in the solution was changed the last time notify() was called.

_previousValue

This variable holds the value that previousVar changed to on the previous move. This is the value it must have for the current move as it cannot change at this iteration.

_gap

This is the maximum difference in cost between the current solution and the best solution found.

_bestCost

This is the cost of the best solution given to the metaheuristic through start().

_soln

This is the solution given to the metaheuristic the last time start() was called.

The class LimitedTabuI--constructor

This constructor creates the limited tabu search class.

LimitedTabuI::LimitedTabuI(IloEnv env, IloNum gap, const char *name) 
  : IloMetaHeuristicI(env, name), _previousVar(), _gap(gap), _soln() {
  assert(_gap >= 0);
}

The class LimitedTabuI--member functions

The complete member function decides if the metaheuristic should indicate that it would like to terminate the search. If no tabu restriction was present, we end. Otherwise, we remove the tabu restriction and continue.

IloBool LimitedTabuI::complete() {
  IloBool done = (_previousVar.getImpl() == 0);
  _previousVar = IloNumVar();
  return done;
}

The isFeasible member function decides the feasibility of the delta with respect to the tabu restriction. If a variable is tabu and the delta assigns this value to a different value from the current one, the delta can be rejected.

IloBool LimitedTabuI::isFeasible(IloSolver, IloSolution delta) const {
  if (_previousVar.getImpl()) {
    if (delta.contains(_previousVar))
      return delta.getValue(_previousVar) != _previousValue;
  }
  return IloTrue;
}

The notify member function finds the changed variable and its value, and stores them in previousVar and previousValue. If delta is not an empty handle, an optimization can be performed. The only variables we need to examine are those in the delta. In the absence of this information, we need to scan all variables in the solution to discover the changed variable.

void LimitedTabuI::notify(IloSolver solver, IloSolution delta) {
  // Update previousVar and previousValue
  _previousVar = IloNumVar();
  IloSolutionIterator<IloNumVar> it(_soln);
  if (delta.getImpl())
    it = IloSolutionIterator<IloNumVar>(delta);
  while (it.ok()) {
    IloNumVar v = *it;
    if (solver.getValue(v) != _soln.getValue(v)) {
      _previousVar = v;
      _previousValue = solver.getValue(v);
      break;
    }
    ++it;
  }
}

The reset member function resets to creation state.

void LimitedTabuI::reset() {
  _soln = IloSolution();
  _previousVar = IloNumVar();
}

The start member function ensures that the solution has an objective which is a simple variable (so that we can map from the IloNumVar to Solver variables). It stores the best cost, if it is better or if there is no cost stored. It also adds constraints to ensure the cost does not vary too far from the best cost, and that the value of previousVar does not change. (This last is done via a setValue rather than a constraint.)

IloBool LimitedTabuI::start(IloSolver solver, IloSolution solution) {
  if (solution.isObjectiveSet()) {
    IloNumVar obj = solution.getObjectiveVar();
    if (obj.getImpl()) {
      if (solution.getObjective().getSense() == IloObjective::Minimize) {
        if (_soln.getImpl() == 0 || solution.getObjectiveValue() < _bestCost) 
          _bestCost = solution.getObjectiveValue();
        if (obj.getType() == ILOINT)
          solver.add(solver.getIntVar(obj) <= _bestCost + _gap);
        else
          solver.add(solver.getFloatVar(obj) <= _bestCost + _gap);
      }
      else {
        if (_soln.getImpl() == 0 || solution.getObjectiveValue() > _bestCost) 
          _bestCost = solution.getObjectiveValue();
        if (obj.getType() == ILOINT)
          solver.add(solver.getIntVar(obj) >= _bestCost - _gap);
        else
          solver.add(solver.getFloatVar(obj) >= _bestCost - _gap);
      }
      if (_previousVar.getImpl())
        solver.setValue(_previousVar, _previousValue);
    }
    else {
      throw "LimitedTabuI::start - "
            "Solution objective must be a simple variable";
    }
  }
  else {
    throw "LimitedTabuI::start - Solution has no objective";
  }
  _soln = solution;
  return IloTrue;
}
 
 

The following function returns the limited tabu metaheuristic. The new metaheuristic is allocated on the same environment as is passed to it. This is important as the delete operator of IloMetaHeuristicI (called via IloMetaHeuristic::end) frees the allocated memory from the env. If you allocate your subclass of IloMetaHeuristicI on a different heap, you must define a delete operator in your subclass.

IloMetaHeuristic LimitedTabu(IloEnv env, IloNum gap, const char *name = 0) {
  return new (env) LimitedTabuI(env, gap, name);
}