Binary extended formulations of polyhedral mixed-integer sets

• 成果类型: Article; Proceedings Paper
• 署名作者: Dash, Sanjeeb; Gunluk, Oktay; Hildebrand, Robert
• 署名单位: International Business Machines (IBM); IBM USA; Virginia Polytechnic Institute & State University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1294-0
• 发表日期: 2018
• 页码: 207-236
• 关键词: programming-problems; linear-programs

摘要

We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call unimodular extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature. Finally, we study the behavior of branch-and-bound on such extended formulations and show that branching on the new binary variables leads to significantly smaller enumeration trees in some cases.