Octane: A new heuristic for pure 0-1 programs

被引：34

作者：

Balas, E ^{[1
]}

Ceria, S

Dawande, M

Margot, F

Pataki, G

机构：

[1] Carnegie Mellon Univ, GSIA, Pittsburgh, PA 15213 USA

[2] Columbia Univ, Grad Sch Business, New York, NY 10027 USA

[3] Univ Texas, Richardson, TX 78083 USA

[4] Univ Kentucky, Lexington, KY USA

[5] Univ N Carolina, Dept Operat Res, Chapel Hill, NC 27599 USA

来源：

OPERATIONS RESEARCH | 2001年 / 49卷 / 02期

关键词：

D O I：

10.1287/opre.49.2.207.13535

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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 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.

引用

页码：207 / 225

页数：19

共 20 条

[1]

[Anonymous], 1997, Tabu Search

[2]

AVIS D, 1972, DISCRETE MATH, V2, P1

[3]

Avis D, 1991, P 7 ANN S COMPUTATIO, P98

[4] INTERSECTION CUT FROM DUAL OF UNIT HYPERCUBE [J].