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

• 成果类型: Article
• 署名作者: Balas, E; Ceria, S; Cornuejols, G
• 署名单位: Columbia University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.42.9.1229
• 发表日期: 1996
• 页码: 1229-1246
• 关键词: integer programming; cutting planes; branch-and-bound; branch-and-cut

摘要

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.