A cutting-plane and benders’ decomposition algorithm for two-stage distributionally robust convex programs

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 $$&lt;5\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>&lt;</mml:mo> <mml:mn>5</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> optimality gap in 12 hours. This gap is $$&gt;17\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mn>17</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> with a commercial solver.