TY - JOUR
T1 - A decomposition method for distributionally-robust two-stage stochastic mixed-integer conic programs
AU - Luo, Fengqiao
AU - Mehrotra, Sanjay
N1 - Funding Information:
This research was supported by the Office of Naval Research grant N00014-18-1-2097-P00001.
Publisher Copyright:
© 2021, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.
PY - 2021
Y1 - 2021
N2 - We develop a decomposition algorithm for distributionally-robust two-stage stochastic mixed-integer convex conic programs, and its important special case of distributionally-robust two-stage stochastic mixed-integer second order conic programs. This generalizes the algorithm proposed by Sen and Sherali [Mathematical Programming 106(2): 203–223, 2006]. We show that the proposed algorithm is finitely convergent if the second-stage problems are solved to optimality at incumbent first stage solutions, and solution to an optimization problem to identify worst-case probability distribution is available. The second stage problems can be solved using a branch and cut algorithm, or a parametric cuts based algorithm presented in this paper. The decomposition algorithm is illustrated with an example. Computational results on a stochastic programming generalization of a facility location problem show significant solution time improvements from the proposed approach. Solutions for many models that are intractable for an extensive form formulation become possible. Computational results also show that for the same amount of computational effort the optimality gaps for distributionally robust instances and their stochastic programming counterpart are similar.
AB - We develop a decomposition algorithm for distributionally-robust two-stage stochastic mixed-integer convex conic programs, and its important special case of distributionally-robust two-stage stochastic mixed-integer second order conic programs. This generalizes the algorithm proposed by Sen and Sherali [Mathematical Programming 106(2): 203–223, 2006]. We show that the proposed algorithm is finitely convergent if the second-stage problems are solved to optimality at incumbent first stage solutions, and solution to an optimization problem to identify worst-case probability distribution is available. The second stage problems can be solved using a branch and cut algorithm, or a parametric cuts based algorithm presented in this paper. The decomposition algorithm is illustrated with an example. Computational results on a stochastic programming generalization of a facility location problem show significant solution time improvements from the proposed approach. Solutions for many models that are intractable for an extensive form formulation become possible. Computational results also show that for the same amount of computational effort the optimality gaps for distributionally robust instances and their stochastic programming counterpart are similar.
KW - Disjunctive programming
KW - Distributionally robust optimization
KW - Stochastic facility location
KW - Two-stage stochastic mixed-integer conic programming
KW - Two-stage stochastic mixed-integer second-order-cone programming
UR - http://www.scopus.com/inward/record.url?scp=85107479868&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85107479868&partnerID=8YFLogxK
U2 - 10.1007/s10107-021-01641-2
DO - 10.1007/s10107-021-01641-2
M3 - Article
AN - SCOPUS:85107479868
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
ER -