Disjunctive cuts in Mixed-Integer Conic Optimization

• 成果类型: Article
• 署名作者: Lodi, Andrea; Tanneau, Mathieu; Vielma, Juan-Pablo
• 署名单位: Universite de Montreal; Polytechnique Montreal; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01844-1
• 发表日期: 2023
• 页码: 671-719
• 关键词: lift-and-project; cutting plane algorithm; extended formulations; approximation; inequalities

摘要

This paper studies disjunctive cutting planes in Mixed-Integer Conic Programming. Building on conic duality, we formulate a cut-generating conic program for separating disjunctive cuts, and investigate the impact of the normalization condition on its resolution. In particular, we show that a careful selection of normalization guarantees its solvability and conic strong duality. Then, we highlight the shortcomings of separating conic-infeasible points in an outer-approximation context, and propose conic extensions to the classical lifting and monoidal strengthening procedures. Finally, we assess the computational behavior of various normalization conditions in terms of gap closed, computing time and cut sparsity. In the process, we show that our approach is competitive with the internal lift-and-project cuts of a state-of-the-art solver.