Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristic

Abstract

Tabu search techniques have been applied to a wide class of optimization problems. Tabu search is a meta procedure that requires a subroutine to find local optima. In most examples of tabu search the subroutine used is problem specific. However, in order to apply tabu search successfully to general 0-1 integer programs, the subroutine must be general. The pivot and complement heuristic is a procedure that frequently finds feasible solutions for general 0-1 integer programs. In this paper we implement several elements of strategies proposed by tabu search method that result in general heuristics for 0-1 integer programs that could be included in an integer programming code. These heuristics employ the ZOOM/XMP implementation of the pivot and complement heuristic as a subroutine. Computational results indicate that these heuristics provide good bounds for many problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.