Mixed 0-1 programming by lift-and-project in a branch-and-cut framework

被引：138

作者：

Balas, E ^{[1
]}

Ceria, S ^{[1
]}

Cornuejols, G ^{[1
]}

机构：

[1] COLUMBIA UNIV, GRAD SCH BUSINESS, NEW YORK, NY 10027 USA

来源：

MANAGEMENT SCIENCE | 1996年 / 42卷 / 09期

关键词：

integer programming; cutting planes; branch-and-bound; branch-and-cut;

D O I：

10.1287/mnsc.42.9.1229

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We investigate the computational issues that need to be addressed when incorporating general cutting planes for mixed 0-1 programs into a branch-and-cut framework. The cuts we use are of the lift-and-project variety. Some of the issues addressed have a theoretical answer, but others are of an experimental nature and are settled by comparing alternatives on a set of test problems. The resulting code is a robust solver for mixed 0-1 programs. We compare it with several existing codes. On a wide range of test problems it performs as well as, or better than, some of the best currently available mixed integer programming codes.

引用

页码：1229 / 1246

页数：18

共 19 条

[11]

Hoffman K. L., 1991, ORSA Journal on Computing, V3, P121, DOI 10.1287/ijoc.3.2.121

[12] SOLVING AIRLINE CREW SCHEDULING PROBLEMS BY BRANCH-AND-CUT [J].

HOFFMAN, KL ;

PADBERG, M .

MANAGEMENT SCIENCE, 1993, 39 (06) :657-682

[13]

JUNGER M, 1993, COMMUNICATION

[14] CONES OF MATRICES AND SET-FUNCTIONS AND 0-1 OPTIMIZATION [J].

Lovasz, L. ;

Schrijver, A. .

SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (02) :166-190

[15]

NOBILI P, 1993, COMMUNICATION

[16] A BRANCH-AND-CUT ALGORITHM FOR THE RESOLUTION OF LARGE-SCALE SYMMETRICAL TRAVELING SALESMAN PROBLEMS [J].

PADBERG, M ;

RINALDI, G .

SIAM REVIEW, 1991, 33 (01) :60-100

[17] A HIERARCHY OF RELAXATIONS BETWEEN THE CONTINUOUS AND CONVEX-HULL REPRESENTATIONS FOR ZERO-ONE PROGRAMMING-PROBLEMS [J].

SHERALI, HD ;

ADAMS, WP .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (03) :411-430

[18]

URSIC S, 1984, LECT NOTES COMPUT SC, V170, P80

[19] SOLVING MIXED INTEGER PROGRAMMING-PROBLEMS USING AUTOMATIC REFORMULATION [J].

VANROY, TJ ;

WOLSEY, LA .

OPERATIONS RESEARCH, 1987, 35 (01) :45-57

← 1 2 →