Optimization Online


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

Mikhail Nediak (msn***at***rutcor.rutgers.edu)
Jonathan Eckstein (jeckstei***at***rutcor.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society