Tabu Search Modern Heuristic Techniques for Combinatorial Problems

Tabu Search I 51
in TS methods, but was achieved in this instance due to cleverly designed data structures to exploit the neighborhood definition. Multiple tabu lists have now become common in many TS applications.

Jaumard, Hansen, and Poggi di Aragao (1991) investigate the problem of determining the consistency of probabilities that specify whether given collections of clauses are true, with extensions to include probability intervals, conditional probabilities, and perturbations to achieve satisfiability. By integrating a tabu search approach with an exact 0-1 nonlinear programming procedure for generating columns of a master linear program, they readily solved problems with up to 140 variables and 300 clauses, approximately tripling both the number of variables and the

number of clauses that could be handled by existing alternative approaches. This work: is extended in the study of Hansen, Jaumard, and Poggi di Aragao (1992) to address problems arising in expert systems, as in systems for medical diagnosis. Tabu search again is embedded in a column generation scheme to determine optimal changes to sets of rules that incorporate probabilities. The combinatorial complexity of this problem comes from the fact that the number of columns grows astronomically as a function of the number of logical sentences used to define rules. This extended study is able to generate optimal solutions for rule systems containing up to 200 sentences, significantly advancing the size of such problems that previously could be addressed.

The multiconstraint zero-one knapsack problem is studied by Dammeyer and V08 (1993) using a TS method that incorporates tabu restrictions based on the logical structure of the attribute sequence generated. The method is compared against an improved version of a simulated annealing method from the literature specifically designed for these problems, using a testbed of 57 problems with known optimal solutions. The TS and SA methods take comparable time on these problems, but the TS method finds optimal solutions for nearly 50% more problems than simulated annealing (44 problems versus 31). On the remaining problems, deviations from optimality with the TS method were less than 2% in all cases, and less than 1% for all problems except one. Dammeyer and V 08 also note that the SA method is very sensitive to the choice of control parameters, which greatly influenced the solution quality. By contrast, they found the TS parameters to be very robust. Similar differences in outcomes are established in the study of quadratic semi-assignment problems by Domschke, Forst, and V08 (1992).

When publishing tabular data, the United States Bureau of the Census must sometimes round fractional data to integer values or round integer data to multiples of a pre-specified base. Data integrity can be maintained by rounding tabular data subject to additivity constraints while minimizing the overall perturbation of the data. Kelly, Golden, and Assad (1993) describe a tabu search procedure with strategic oscillation for solving this NP-hard problem. A lower bound is obtained by solving a network flow programming model and the corresponding solution is used as the starting point for the procedure. Strategic oscillation plays a major role in this TS implementation. The oscillation in this case is around the feasibility boundary. A penalty function is used fIrst to lead the search from the lower bound solution towards the feasible region, by linearly incrementing the penalty for an aggregated measure of constraint violation. Once the procedure reaches feasibility for the flfSt time, the penalty oscillates within a specified period. The
52 I GLOVERandLAGUNA
theoretical lower bound value obtained by network optimization (which may not be attainable by any feasible solution) is used to gauge the quality of solutions found. Experiments with 270 simulated problems yield an average deviation from this lower bound of 1.32%. In addition, for

248 three-dimensional tables provided by the United States Bureau of the Census, the deviation from the lower bound was only 0.391 %.

5.
Connections with Other Procedures and Conclusions
Relationships between tabu search and other procedures like simulated annealing and genetic algorithms provide a basis for understanding similarities and contrasts in their philosophies, and for creating potentially useful hybrid combinations of these approaches. We

offer some speculation on preferable directions in this regard, and also suggest how elements of tabu search can add a useful dimension to neural network approaches.