A Solution Approach to Distributionally Robust Joint-Chance-Constrained Assignment Problems

References

• Abdi A, Fukasawa R (2016) On the mixing set with a knapsack constraint. Math. Programming 157(1):191–217.Google Scholar
• Bansal M, Huang K-L, Mehrotra S (2018) Decomposition algorithms for two-stage distributionally robust mixed binary programs. SIAM J. Optim. 28(3):2360–2383.Google Scholar
• Ben-Tal A, Den Hertog D, De Waegenaere A, Melenberg B, Rennen G (2013) Robust solutions of optimization problems affected by uncertain probabilities. Management Sci. 59(2):341–357.Link, Google Scholar
• Beraldi P, Bruni ME (2010) An exact approach for solving integer problems under probabilistic constraints with random technology matrix. Ann. Oper. Res. 177(1):127–137.Google Scholar
• Bertsimas D, Demir R (2002) An approximate dynamic programming approach to multidimensional knapsack problems. Management Sci. 48(4):550–565.Link, Google Scholar
• Calafiore GC, Campi MC (2006) The scenario approach to robust control design. IEEE Trans. Automated Control 51(5):742–753.Google Scholar
• Chen Z, Kuhn D, Wiesemann W (2018) Data-driven chance constrained programs over wasserstein balls. Preprint, submitted August 31, https://arxiv.org/abs/1809.00210.Google Scholar
• Chen W, Sim M, Sun J, Teo C-P (2010) From cvar to uncertainty set: Implications in joint chance-constrained optimization. Oper. Res. 58(2):470–485.Link, Google Scholar
• Cheng J, Delage E, Lisser A (2014) Distributionally robust stochastic knapsack problem. SIAM J. Optim. 24(3):1485–1506.Google Scholar
• Cohen MC, Keller PW, Mirrokni V, Zadimoghaddam M (2019) Overcommitment in cloud services: Bin packing with chance constraints. Management Sci. 65(7):3255–3271.Link, Google Scholar
• Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):595–612.Link, Google Scholar
• Deng Y, Shen S (2016) Decomposition algorithms for optimizing multi-server appointment scheduling with chance constraints. Math. Programming 157(1):245–276.Google Scholar
• Deng Y, Shen S, Denton B (2019) Chance-constrained surgery planning under conditions of limited and ambiguous data. INFORMS J. Comput. 31(3):559–575.Link, Google Scholar
• Esfahani PM, Kuhn D (2018) Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Math. Programming 171(1-2):115–166.Google Scholar
• Gu Z, Nemhauser GL, Savelsbergh MW (1998) Lifted cover inequalities for 0-1 integer programs: Computation. INFORMS J. Comput. 10(4):427–437.Link, Google Scholar
• Hanasusanto GA, Roitch V, Kuhn D, Wiesemann W (2017) Ambiguous joint chance constraints under mean and dispersion information. Oper. Res. 65(3):751–767.Link, Google Scholar
• Ji R, Lejeune MA (2020) Data-driven distributionally robust chance-constrained optimization with Wasserstein metric. J. Global Optim. 79(4):779–811.Google Scholar
• Jiang R, Guan Y (2016) Data-driven chance constrained stochastic program. Math. Programming 158(1-2):291–327.Google Scholar
• Jiang R, Guan Y (2018) Risk-averse two-stage stochastic program with distributional ambiguity. Oper. Res. 66(5):1390–1405.Link, Google Scholar
• Kaparis K, Letchford AN (2008) Local and global lifted cover inequalities for the 0–1 multidimensional knapsack problem. Eur. J. Oper. Res. 186(1):91–103.Google Scholar
• Klabjan D, Nemhauser GL, Tovey C (1998) The complexity of cover inequality separation. Oper. Res. Lett. 23(1-2):35–40.Google Scholar
• Küçükyavuz S (2012) On mixing sets arising in chance-constrained programming. Math. Programming 132(1-2):31–56.Google Scholar
• Liu X, Kilinç-Karzan F, Küçükyavuz S (2019) On intersection of two mixing sets with applications to joint chance-constrained programs. Math. Programming 175:29–68.Google Scholar
• Liu X, Küçükyavuz S, Luedtke J (2016) Decomposition algorithms for two-stage chance-constrained programs. Math. Programming 157(1):219–243.Google Scholar
• Luedtke J (2014) A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math. Programming 146(1-2):219–244.Google Scholar
• Luedtke J, Ahmed S (2008) A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2):674–699.Google Scholar
• Luedtke J, Ahmed S, Nemhauser GL (2010) An integer programming approach for linear programs with probabilistic constraints. Math. Programming 122(2):247–272.Google Scholar
• Luo F, Mehrotra S (2019) Decomposition algorithm for distributionally robust optimization using Wasserstein metric with an application to a class of regression models. Eur. J. Oper. Res. 278(1):20–35.Google Scholar
• Mehrotra S, Papp D (2014) A cutting surface algorithm for semi-infinite convex programming with an application to moment robust optimization. SIAM J. Optim. 24(4):1670–1697.Google Scholar
• Pagnoncelli B, Ahmed S, Shapiro A (2009) Sample average approximation method for chance constrained programming: Theory and applications. J. Optim. Theory Appl. 142(2):399–416.Google Scholar
• Peng C, Delage E, Li J (2020) Probabilistic envelope constrained multiperiod stochastic emergency medical services location model and decomposition scheme. Transportation Sci. 54(6):1471–1494.Link, Google Scholar
• Qiu F, Ahmed S, Dey SS, Wolsey LA (2014) Covering linear programming with violations. INFORMS J. Comput. 26(3):531–546.Link, Google Scholar
• Rahimian H, Mehrotra S 2019. Distributionally robust optimization: A review. Preprint, submitted XX, https://arxiv.org/abs/1908.05659.Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2009) Lectures on Stochastic Programming: Modeling and Theory (SIAM, Philadelphia).Google Scholar
• Song Y, Luedtke JR (2013) Branch-and-cut approaches for chance-constrained formulations of reliable network design problems. Math. Programming Comput. 5(4):397–432.Google Scholar
• Song Y, Luedtke JR, Küçükyavuz S (2014) Chance-constrained binary packing problems. INFORMS J. Comput. 26(4):735–747.Link, Google Scholar
• Tanner MW, Ntaimo L (2010) Iis branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation. Eur. J. Oper. Res. 207(1):290–296.Google Scholar
• van Ackooij W, Frangioni A, de Oliveira W (2016) Inexact stabilized benders’ decomposition approaches with application to chance-constrained problems with finite support. Comput. Optim. Appl. 65(3):637–669.Google Scholar
• Wang S, Li J, Mehrotra S (2021) Chance-constrained multiple bin packing problem with an application to operating room planning. INFORMS J. Comput., ePub ahead of print March 9, https://doi.org/10.1287/ijoc.2020.1010.Google Scholar
• Wang S, Li J, Peng C (2017) Distributionally robust chance-constrained program surgery planning with downstream resource. Proc. 2017 Internat. Conf. Service Systems Service Management (IEEE, New York), 1–6.Google Scholar
• Wiesemann W, Kuhn D, Sim M (2014) Distributionally robust convex optimization. Oper. Res. 62(6):1358–1376.Link, Google Scholar
• Wu H-H, Küçükyavuz S 2017. Chance-constrained combinatorial optimization with a probability oracle and its application to probabilistic partial set covering. Preprint, submitted XX, https://arxiv.org/abs/1708.02505.Google Scholar
• Xie W (2019) On distributionally robust chance constrained programs with Wasserstein distance. Math. Programming 186(1):115–155.Google Scholar
• Xie W, Ahmed S (2018) On quantile cuts and their closure for chance constrained optimization problems. Math. Programming 172(1-2):621–646.Google Scholar
• Zemel E (1989) Easily computable facets of the knapsack polytope. Math. Oper. Res. 14(4):760–764.Link, Google Scholar
• Zhang Z, Denton BT, Xie X (2020) Branch and price for chance-constrained bin packing. INFORMS J. Comput. 32(3):547–564.Link, Google Scholar
• Zhang Y, Jiang R, Shen S (2018) Ambiguous chance-constrained binary programs under mean-covariance information. SIAM J. Optim. 28(4):2922–2944.Google Scholar
• Zhao M, Huang K, Zeng B (2017) A polyhedral study on chance constrained program with random right-hand side. Math. Programming 166(1-2):19–64.Google Scholar
• Zymler S, Kuhn D, Rustem B (2013) Distributionally robust joint chance constraints with second-order moment information. Math. Programming 137(1-2):167–198.Google Scholar