Pivot, Cut, and Dive: A Heuristic for 0-1 Mixed Integer Programming

Mikhail Nediak (msnrutcor.rutgers.edu)
Jonathan Eckstein (jecksteirutcor.rutgers.edu)

Abstract: 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.

Keywords: integer programming, heuristic, parallel

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 3: Combinatorial Optimization (Meta Heuristics )

Citation: RUTCOR Research Report RRR 53-2001, Rutgers University, October 2001

Download: [Postscript]

Entry Submitted: 11/10/2001
Entry Accepted: 11/10/2001
Entry Last Modified: 11/10/2001

Modify/Update this entry