Embedding Formulations and Complexity for Unions of Polyhedra
提出嵌入公式与复杂度作为混合整数规划新范式，系统构造最优尺寸的析取约束公式，对特殊有序集类型2和二元分段线性函数给出最优公式，计算优势显著。
It is well known that selecting a good mixed-integer programming (MIP) formulation is crucial for effectively obtaining a solution with state-of-the art solvers. Although best practices and guidelines for constructing good formulations abound, there is rarely a single systematic construction approach that leads to the best possible formulation. Here, we introduce embedding formulations and complexity as a new MIP formulation paradigm for systematically constructing formulations for disjunctive constraints that are optimal with respect to size. More specifically, they yield the smallest possible ideal formulation (i.e., one whose LP relaxation has integral extreme points) among all formulations that only use 0-1 auxiliary variables. We use the paradigm to characterize optimal formulations for special ordered sets of type 2 and certain piecewise linear functions of two variables. We also show that the resultant formulations can provide a significant computational advantage over all known formulations for piecewise linear functions. This paper was accepted by Yinyu Ye, optimization.