论文标题
通过结树建模组合分离的约束
Modeling Combinatorial Disjunctive Constraints via Junction Trees
论文作者
论文摘要
我们介绍了通过独立的分支方案来构建组合析出约束（CDC）的小型理想的混合智能编程（MIP）公式。我们提出了一种新颖的成对IB代表类的CDC类，CDC允许交界树，并提供了组合程序，以构建这些约束的MIP公式。通用的特殊有序集（$ \ text {sos} k $）可以由CDC建模，我们还可以获得$ \ text {sos} k $的MIP公式。此外，我们提供了一种新颖的理想扩展配方，对任何组合脱节的约束都具有较少的辅助二进制变量，并且在平面障碍物中避免了辅助二进制变量。
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 formulations for those constraints. Generalized special ordered sets ($\text{SOS} k$) can be modeled by CDCs admitting junction trees and we also obtain MIP formulations of $\text{SOS} k$. Furthermore, we provide a novel ideal extended formulation of any combinatorial disjunctive constraints with fewer auxiliary binary variables with an application in planar obstacle avoidance.
