Modeling combinatorial disjunctive constraints via junction trees

• 成果类型: Article
• 署名作者: Lyu, Bochuan; Hicks, Illya V.; Huchette, Joey
• 署名单位: Rice University; Alphabet Inc.; Google Incorporated
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01955-3
• 发表日期: 2024
• 页码: 385-413
• 关键词: base-2 expansions; integer; optimization; complexity; graphs; formulations; algorithm

摘要

We introduce techniques to build small ideal mixed-integer programming (MIP) formulations of combinatorial disjunctive constraints (CDCs) via the independent branching scheme. We present a novel pairwise IB-representable class of CDCs, CDCs admitting junction trees, and provide a combinatorial procedure to build MIP formu-lations for those constraints. Generalized special ordered sets (SOS k) can be modeled by CDCs admitting junction trees and we also obtain MIP formulations of SOS k. Furthermore, we provide a novel ideal extended formulation of any combinatorial dis-junctive constraints with fewer auxiliary binary variables with an application in planar obstacle avoidance.