Split closure and intersection cuts

• 成果类型: Article
• 署名作者: Andersen, K; Cornuéjols, G; Li, YJ
• 署名单位: Carnegie Mellon University; Purdue University System; Purdue University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-004-0558-z
• 发表日期: 2005
• 页码: 457-493
• 关键词: integer programs

摘要

In the seventies, Balas introduced intersection cuts for a Mixed Integer Linear Program (MILP), and showed that these cuts can be obtained by a closed form formula from a basis of the standard linear programming relaxation. In the early nineties, Cook, Kannan and Schrijver introduced the split closure of a MILP, and showed that the split closure is a polyhedron. In this paper, we show that the split closure can be obtained using only intersection cuts. We give two different proofs of this result, one geometric and one algebraic. The result is then used to provide a new proof of the fact that the split closure of a MILP is a polyhedron. Finally, we extend the result to more general disjunctions.