Octane: A New Heuristic for Pure 0–1 Programs

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.