Monoidal strengthening of simple V-polyhedral disjunctive cuts

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

摘要

Disjunctive cutting planes can tighten a relaxation of a mixed-integer linear program. Traditionally, such cuts are obtained by solving a higher-dimensional linear program, whose additional variables cause the procedure to be computationally prohibitive. Adopting a V-polyhedral perspective is a practical alternative that enables the separation of disjunctive cuts via a linear program with only as many variables as the original problem. The drawback is that the classical approach of monoidal strengthening cannot be directly employed without the values of the extra variables appearing in the extended formulation, which constitute a certificate of validity of the cut. We derive how to compute this certificate from a solution to the linear program generating V-polyhedral disjunctive cuts. We then present computational experiments with monoidal strengthening of cuts from disjunctions with as many as 64 terms. Some instances are dramatically impacted, with strengthening increasing the gap closed by the cuts from 0 to 100%. However, for larger disjunctions, monoidal strengthening appears to be less effective, for which we identify a potential cause. Lastly, the certificates of validity also enable us to verify which disjunctive cuts are equivalent to intersection cuts, which happens increasingly rarely for larger disjunctions.