论文标题
p-split公式：大-M和凸壳之间的一类中间公式用于析取约束
P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraints
论文作者
论文摘要
我们开发了一类混合企业制剂，以在松弛强度方面涉及大型M和凸出船体配方中间的分离约束。主要思想是捕获Big-M和凸壳配方中最好的：一种计算轻松的配方，并具有紧密的放松。 “ p-split”公式基于提升的转换，该转换将凸面可分开的约束分成p分区，并形成线性化和分区析取的凸壳。 “ p-split”公式是针对每个分离中具有凸约限制的析取约束的，我们将案例的结果推广到析置内的非convex约束。我们分析了p分数制剂的连续放松，并表明，在某些假设下，该制剂形成从大型M当量开始并融合到凸壳的层次结构。我们在计算上比较了在344个测试实例上与Big-M和凸出船体配方进行比较。测试问题包括K-均值聚类，半监督聚类，P_BALL问题以及对训练有素的Relu神经网络的优化。计算结果显示了p分数制剂的有希望的潜力。对于许多测试问题，p分数公式的求解与凸出的船体公式相似的探索节点求解，同时，通过数量级来减少解决方案的时间，并且在时间和探索节点上都超过了大-M的表现。
We develop a class of mixed-integer formulations for disjunctive constraints intermediate to the big-M and convex hull formulations in terms of relaxation strength. The main idea is to capture the best of both the big-M and convex hull formulations: a computationally light formulation with a tight relaxation. The "P-split" formulations are based on a lifted transformation that splits convex additively separable constraints into P partitions and forms the convex hull of the linearized and partitioned disjunction. The "P-split" formulations are derived for disjunctive constraints with convex constraints within each disjunct, and we generalize the results for the case with nonconvex constraints within the disjuncts. We analyze the continuous relaxation of the P-split formulations and show that, under certain assumptions, the formulations form a hierarchy starting from a big-M equivalent and converging to the convex hull. We computationally compare the P-split formulations against big-M and convex hull formulations on 344 test instances. The test problems include K-means clustering, semi-supervised clustering, P_ball problems, and optimization over trained ReLU neural networks. The computational results show promising potential of the P-split formulations. For many of the test problems, P-split formulations are solved with a similar number of explored nodes as the convex hull formulation, while reducing the solution time by an order of magnitude and outperforming big-M both in time and number of explored nodes.
