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

• 成果类型: Article; Early Access
• 署名作者: Luo, Fengqiao; Dey, Shibshankar; Mehrotra, Sanjay
• 署名单位: Northwestern University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02288-z
• 发表日期: 2025
• 关键词: valid inequalities; gomory cuts; integer; approximation

摘要

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 is an element of-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% optimality gap in 12 hours. This gap is >17% with a commercial solver.