<p>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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10107_2025_2288_Article_IEq1.gif" Format="GIF" Height="13" Rendition="HTML" Resolution="72" Type="Linedraw" Width="24" /> </InlineMediaObject> <EquationSource Format="TEX">$\epsilon -$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϵ</mi> <mo>-</mo> </mrow> </math></EquationSource> </InlineEquation>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 <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10107_2025_2288_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">$<5\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo><</mo> <mn>5</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation> optimality gap in 12 hours. This gap is <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10107_2025_2288_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="49" /> </InlineMediaObject> <EquationSource Format="TEX">$>17\%$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>></mo> <mn>17</mn> <mo>%</mo> </mrow> </math></EquationSource> </InlineEquation> with a commercial solver.</p>

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

期刊论文
出版模式：

开放获取
发表日期：

2025年10月14日

查看全文

Fengqiao Luo,
Shibshankar Dey,
Sanjay Mehrotra

摘要

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 -$ $ϵ -$ 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\%$ $< 5 %$ optimality gap in 12 hours. This gap is $>17\%$ $> 17 %$ with a commercial solver.