Octane: A New Heuristic for Pure 0–1 Programs

Egon Balas, Sebastián Ceria, Milind Dawande, Francois Margot, Gábor Pataki

Operations Research · 2001 · Volume 49 · Issue 2

Abstract

We propose a new heuristic for pure 0–1 programs, which finds feasible integer points by enumerating extended facets of the octahedron, the outer polar of the unit hypercube. We give efficient algorithms to carry out the enumeration, and we explain how our heuristic can be embedded in a branch-and-cut framework. Finally, we present computational results on a set of pure 0–1 programs taken from MIPLIB and other sources.

Keywords

Integer programming: pure 0-1 programming, Heuristics: facet enumeration

Enable JavaScript for citation tools and additional paper interactions.