论文标题
与0-1二阶圆锥编程应用程序的组合切割程序
A Combinatorial Cut-and-Lift Procedure with an Application to 0-1 Second-Order Conic Programming
论文作者
论文摘要
剪切生成和提起是最先进的数学编程求解器执行的关键组成部分。这项工作提出了一种新的通用切割程序，该程序通过二进制决策图（BDD）编码其约束来利用0-1问题的组合结构。我们提出了一个通用框架，该框架可以应用于广泛的二进制优化问题，并显示其对二阶锥形不平等的适用性。我们确定提出不平等的条件是定义的，并得出了新的基于BDD的切割生成线性程序。这样的模型是BDD上最大流量组合算法的基础，可将其应用于得出有效削减的效率更高。我们的数值结果表明，当将其纳入最先进的数学编程求解器中时，令人鼓舞的性能，大大减少了根节点间隙，增加了解决的问题的数量，并将运行时间平均减少了三倍。
Cut generation and lifting are key components for the performance of state-of-the-art mathematical programming solvers. This work proposes a new general cut-and-lift procedure that exploits the combinatorial structure of 0-1 problems via a binary decision diagram (BDD) encoding of their constraints. We present a general framework that can be applied to a wide range of binary optimization problems and show its applicability for second-order conic inequalities. We identify conditions for which our lifted inequalities are facet-defining and derive a new BDD-based cut generation linear program. Such a model serves as a basis for a max-flow combinatorial algorithm over the BDD that can be applied to derive valid cuts more efficiently. Our numerical results show encouraging performance when incorporated into a state-of-the-art mathematical programming solver, significantly reducing the root node gap, increasing the number of problems solved, and reducing the run-time by a factor of three on average.
