Octane: A new heuristic for pure 0-1 programs

We propose a new heuristic for pure 0-1 programs, which finds feasible inte ger points by enumerating extended facets of the octahedron, the outer pola r of the unit hypercube. We give efficient algorithms to carry out the enum eration, and rye 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 MILPLIB and other sources.