We present a heuristic method for general 0-1 mixed integer programming, intended for eventual incorporation into parallel branch-and-bound methods for solving such problems exactly. The core of the heuristic is a rounding method based on simplex pivots, employing only gradient information, for a strictly concave, differentiable merit function measuring integer feasibility. When local minima of this merit function are not integer-feasible, several additional layers of the heuristic come into play. These successive layers include explicit probing of adjacent vertices, modification of the merit function, adjoining of ``convexity'' cuts to the formulation, and a diving procedure that attempts to fix multiple variables simultaneously. We present ``stand-alone'' computational results, running the heuristic by itself without an accompanying branch-and-bound optimization, on a variety of problems from the MIPLIB collection.
Citation
RUTCOR Research Report RRR 53-2001, Rutgers University, October 2001
Article
View Pivot, Cut, and Dive: A Heuristic for 0-1 Mixed Integer Programming