Octane: A New Heuristic for Pure 0--1 Programs

Egon Balas, Sebastián Ceria (), Milind Dawande (), Francois Margot () and Gábor Pataki ()
Additional contact information
Sebastián Ceria: Graduate School of Business, Columbia University, New York 10027 and Axioma, New York
Milind Dawande: University of Texas at Dallas, PO Box 830688, Richardson, Texas 78083
Francois Margot: University of Kentucky, Lexington, Kentucky
Gábor Pataki: Department of Operations Research, University of North Carolina, Chapel Hill, North Carolina 27599

Operations Research, 2001, vol. 49, issue 2, 207-225

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 (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.2.207.13535 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:49:y:2001:i:2:p:207-225

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().