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