It is possible to write your own local search metaheuristic using Solver by subclassing the IloMetaHeuristicI class. This section shows you how to do this. The basic behavior of the metaheuristic class is to filter out proposed moves according to the metaheuristic rule. For instance, a greedy metaheuristic filters out all moves which do not improve the cost.

Here, you will find the description of a limited tabu search metaheuristic. Tabu search is a technique that typically makes the best move at each step in the search process, even if that move degrades the search cost. However, in order to avoid the problem of the search being caught in a cycle of making a non-improving move, then the opposite improving one, a tabu status is given to the last few moves. Thus, once a move is made some other moves (typically those which would result in a previously visited point) are made illegal (tabu). This is to avoid the cycling problem mentioned. The illegality of a tabu move persists for a number of moves after it is first made tabu, this length of time being termed the tenure.

In the limited tabu search metaheuristic described here, the tenure is fixed at 1. The tabu metaheuristic is meant to be used in a local search where the value of only a single variable is changed at each move. Then, at each move, the variable that changed its value during the last move is forbidden from changing its value at this iteration. This prevents cycles of length 2, where the search moves continually between two neighboring states. To prevent longer cycles, longer tabu lists can be used, such as in the class IloTabuSearch provided with Solver.

To add a little extra complexity, the metaheuristic described also includes a rule which says that the solution must not stray too far (in terms of cost) from the best solution found so far. The maximum gap between the current and best solution is specified to the metaheuristic.