V-polyhedral disjunctive cuts

• 成果类型: Article; Early Access
• 署名作者: Balas, Egon; Kazachkov, Aleksandr M.
• 署名单位: Carnegie Mellon University; State University System of Florida; University of Florida
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02227-y
• 发表日期: 2025
• 关键词: lift-and-project; gomory cuts; local cuts; integer; branch; DECOMPOSITION; algorithm

摘要

We introduce V-polyhedral disjunctive cuts (VPCs) to generate valid inequalities from general disjunctions for a mixed-integer linear program. While optimization solvers critically rely on cuts, they only deploy limited families derivable from weak disjunctions, as the typical cut-generating linear program needs a costly higher-dimensional representation. The VPC framework mitigates this through a polar perspective to more efficiently use deeper, multiterm disjunctions, which partition the feasible region into more subproblems that offer tighter relaxations and better cuts. Given a disjunction, we build a linear program with constraints defined by points and rays from the disjunctive terms that must not be cut. We prove that a polynomially-sized point-ray collection suffices to guarantee cut validity while ensuring strong cuts exist. This enables us to evaluate large disjunctions, which we obtain from the leaf nodes of partial branch-and-bound trees. We generate multiple cuts by adaptively selecting objectives for one fixed strong disjunction. This contrasts to the traditional paradigm that pursues one cut from each of several weak disjunctions and relies on recursive applications to attain strong bound improvements, possibly causing numerical instability and tailing off of cut effectiveness. In computational experiments in the open-source COIN-OR framework, a round of VPCs substantially improves the gap closed compared to existing cuts and in some cases decreases solving time with branch and bound.