Reduce-and-split cuts: Improving the performance of mixed-integer gomory cuts

• 成果类型: Article
• 署名作者: Andersen, K; Cornuéjols, G; Li, YJ
• 署名单位: Universite Catholique Louvain; Carnegie Mellon University; Aix-Marseille Universite; Purdue University System; Purdue University
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.1050.0382
• 发表日期: 2005
• 页码: 1720-1732
• 关键词: integer programming; Mixed-Integer Programming; cutting plane; split cut; mixed-integer Gomory cut; reduce-and-split cut

摘要

Mixed-integer Gomory cuts have become an integral part of state-of-the-art software for solving mixed-integer linear programming problems. Therefore, improvements in the performance of these cutting planes can be of great practical value. In this paper, we present a simple and fast heuristic for improving the coefficients on the continuous variables in the mixed-integer Gomory cuts. This is motivated by the fact that in a mixed-integer Gomory cut, the coefficient of an integer variable lies between 0 and 1, whereas for a continuous variable, there is no upper bound. The heuristic tries to reduce the coefficients of the continuous variables. We call the resulting cuts reduce-and-split cuts. We found that on several test problems, reduce-and-split cuts can substantially enhance the performance of a branch-and-bound algorithm.