A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming

• 成果类型: Article
• 署名作者: Castro, Margarita P.; Cire, Andre A.; Beck, J. Christopher
• 署名单位: Pontificia Universidad Catolica de Chile; University of Toronto; University Toronto Scarborough; University of Toronto
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01699-y
• 发表日期: 2022
• 页码: 115-171
• 关键词: extended formulations; valid inequalities; cover inequalities; decision diagrams; Lower bounds; Bin packing; optimization; branch; facets; algorithm

摘要

Cut generation and lifting are key components for the performance of state-of-the-art mathematical programming solvers. This work proposes a new general cut-and-lift procedure that exploits the combinatorial structure of 0-1 problems via a binary decision diagram (BDD) encoding of their constraints. We present a general framework that can be applied to a wide range of binary optimization problems and show its applicability for second-order conic inequalities. We identify conditions for which our lifted inequalities are facet-defining and derive a new BDD-based cut generation linear program. Such a model serves as a basis for a max-flow combinatorial algorithm over the BDD that can be applied to derive valid cuts more efficiently. Our numerical results show encouraging performance when incorporated into a state-of-the-art mathematical programming solver, significantly reducing the root node gap, increasing the number of problems solved, and reducing the run-time by a factor of three on average.