A cutting-plane and benders’ decomposition algorithm for two-stage distributionally robust convex programs
提出一种有限步收敛的割平面算法求解一般混合整数凸规划，并扩展至两阶段分布鲁棒随机凸规划，结合分支并集方案提升实用性，测试中12小时内最优性差距小于5%。
Abstract We present a finitely convergent cutting-plane algorithm for solving a general mixed-integer convex program given an oracle for solving a general convex program. This method is extended to solve a family of two-stage mixed-integer convex programs using cutting planes, with applications to solving distributionally-robust two-stage stochastic mixed-integer convex programs. Analysis is also given for the case where convex programming oracle provides an $$\epsilon -$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ϵ</mml:mi> <mml:mo>-</mml:mo> </mml:mrow> </mml:math> optimal solution. We combine the cut generation with a branch-and-union scheme to develop a more practical algorithm. Computational results on generated test problems show the practicality of our algorithm. Specifically, results show that in the tested problems our algorithm achieves $$<5\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo><</mml:mo> <mml:mn>5</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> optimality gap in 12 hours. This gap is $$>17\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>></mml:mo> <mml:mn>17</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> with a commercial solver.