Towards Large-Scale Probabilistic Set Covering Problems: An Efficient Benders Decomposition Approach

References

• Achterberg T (2007) Constraint integer programming. Unpublished PhD thesis, Technical University of Berlin, Germany.Google Scholar
• Ahmed S, Papageorgiou DJ (2013) Probabilistic set covering with correlations. Oper. Res. 61(2):438–452.Link, Google Scholar
• Ahmed S, Shapiro A (2008) Solving chance-constrained stochastic programs via sampling and integer programming. Chen ZL, Raghavan S, eds. Tutorials in Operations Research: State-of-the-Art Decision-Making Tools in the Information-Intensive Age (INFORMS, Catonsville), 261–269. Link, Google Scholar
• Atamtürk A, Nemhauser GL, Savelsbergh MW (2000) Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121(1):40–55.Crossref, Google Scholar
• Azizi N, García S, Irawan CA (2022) Discrete location problems with uncertainty. Salhi S, Boylan J, eds. The Palgrave Handbook of Operations Research (Palgrave Macmillan, Cham, Switzerland), 43–71.Crossref, Google Scholar
• Beasley JE (1990) OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Belotti P, Kirches C, Leyffer S, Linderoth J, Luedtke J, Mahajan A (2013) Mixed-integer nonlinear optimization. Acta Numerica 22:1–131.Crossref, 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.Crossref, Google Scholar
• Beraldi P, Ruszczyński A (2002) The probabilistic set-covering problem. Oper. Res. 50(6):956–967.Link, Google Scholar
• Bodur M, Luedtke JR (2017) Mixed-integer rounding enhanced Benders decomposition for multiclass service-system staffing and scheduling with arrival rate uncertainty. Management Sci. 63(7):2073–2091.Link, Google Scholar
• Bonami P, Kilinç M, Linderoth J (2012) Algorithms and software for convex mixed integer nonlinear programs. Lee J, Leyffer S, eds. Mixed Integer Nonlinear Programming (Springer, New York), 1–39.Crossref, Google Scholar
• Brito SS, Santos HG (2021) Preprocessing and cutting planes with conflict graphs. Comput. Oper. Res. 128:105176.Crossref, Google Scholar
• Burke EK, Mareček J, Parkes AJ, Rudová H (2012) A branch-and-cut procedure for the udine course timetabling problem. Ann. Oper. Res. 194(1):71–87.Crossref, Google Scholar
• Chen WK, Chen YL, Dai YH, Lv W (2024) Towards large-scale probabilistic set covering problem: An efficient Benders decomposition approach. 2024 INFORMS Optim. Soc. Conf. https://sites.google.com/view/ios2024refereed?usp=sharing.Google Scholar
• Chicoisne R, Espinoza D, Goycoolea M, Moreno E, Rubio E (2012) A new algorithm for the open-pit mine production scheduling problem. Oper. Res. 60(3):517–528.Link, Google Scholar
• Cordeau JF, Furini F, Ljubić I (2019) Benders decomposition for very large scale partial set covering and maximal covering location problems. Eur. J. Oper. Res. 275(3):882–896.Crossref, Google Scholar
• Deng Y, Ahmed S, Shen S (2018) Parallel scenario decomposition of risk-averse 0-1 stochastic programs. INFORMS J. Comput. 30(1):90–105.Link, Google Scholar
• Espinoza D, Goycoolea M, Moreno E (2015) The precedence constrained knapsack problem: Separating maximally violated inequalities. Discrete Appl. Math. 194:65–80.Crossref, Google Scholar
• Feng Z, Okamura H, Dohi T, Yun WY (2024) Reliability computing methods of probabilistic location set covering problem considering wireless network applications. IEEE Trans. Reliability 73(1):290–303.Crossref, Google Scholar
• Fischetti M, Monaci M (2012) Cutting plane versus compact formulations for uncertain (integer) linear programs. Math. Programming Comput. 4:239–273.Crossref, Google Scholar
• Fischetti M, Ljubić I, Sinnl M (2016) Benders decomposition without separability: A computational study for capacitated facility location problems. Eur. J. Oper. Res. 253(3):557–569.Crossref, Google Scholar
• Gendron B, Scutellà MG, Garroppo RG, Nencioni G, Tavanti L (2016) A branch-and-Benders-cut method for nonlinear power design in green wireless local area networks. Eur. J. Oper. Res. 255(1):151–162.Crossref, Google Scholar
• Geoffrion AM (1972) Generalized Benders decomposition. J. Optim. Theory Appl. 10(4):237–260.Crossref, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1993) Geometric Algorithms and Combinatorial Optimization (Springer, Berlin).Crossref, Google Scholar
• Gu Z, Nemhauser GL, Savelsbergh MWP (1998) Lifted cover inequalities for 0-1 integer programs: Computation. INFORMS J. Comput. 10(4):427–437.Link, Google Scholar
• Günlük O, Pochet Y (2001) Mixing mixed-integer inequalities. Math. Programming 90(3):429–457.Crossref, Google Scholar
• Hwang HS (2004) A stochastic set-covering location model for both ameliorating and deteriorating items. Comput. Indust. Engrg. 46(2):313–319.Crossref, Google Scholar
• Jiang N, Xie W (2025) The terminator: An integration of inner and outer approximations for solving Wasserstein distributionally robust chance constrained programs via variable fixing. INFORMS J. Comput. 37(2):381–412.Link, Google Scholar
• Johnson DS, Niemi KA (1983) On knapsacks, partitions, and a new dynamic programming technique for trees. Math. Oper. Res. 8(1):1–14.Link, Google Scholar
• Küçükyavuz S, Jiang R (2022) Chance-constrained optimization under limited distributional information: A review of reformulations based on sampling and distributional robustness. EURO J. Comput. Optim. 10:100030.Crossref, Google Scholar
• Küçükyavuz S, Sen S (2017) An introduction to two-stage stochastic mixed-integer programming. Batta R, Peng J, eds. Tutorials in Operations Research: Leading Developments from INFORMS Communities (INFORMS, Catonsville), 1–27.Link, Google Scholar
• Lejeune M (2008) Preprocessing techniques and column generation algorithms for stochastically efficient demand. J. Oper. Res. Soc. 59(9):1239–1252.Crossref, Google Scholar
• Lejeune M, Noyan N (2010) Mathematical programming approaches for generating p-efficient points. Eur. J. Oper. Res. 207(2):590–600.Crossref, Google Scholar
• Liu X, Küçükyavuz S, Luedtke J (2016) Decomposition algorithms for two-stage chance-constrained programs. Math. Programming 157(1):219–243.Crossref, Google Scholar
• Luedtke J (2014) A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math. Programming 146:219–244.Crossref, Google Scholar
• Luedtke J, Ahmed S (2008) A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2):674–699.Crossref, Google Scholar
• Luedtke J, Ahmed S, Nemhauser GL (2010) An integer programming approach for linear programs with probabilistic constraints. Math. Programming 122:247–272.Crossref, Google Scholar
• Lutter P, Degel D, Büsing C, Koster AMCA, Werners B (2017) Improved handling of uncertainty and robustness in set covering problems. Eur. J. Oper. Res. 263(1):35–49.Crossref, Google Scholar
• Lv W, Chen WK, Chen YL, Dai YH (2026) Toward large-scale probabilistic set-covering problems: An efficient Benders decomposition approach. https://doi.org/10.1287/ijoc.2025.1307.cd, https://github.com/INFORMSJoC/2025.1307.Google Scholar
• Nemirovski A, Shapiro A (2006) Scenario approximations of chance constraints. Calafiore G, Dabbene F, eds. Probabilistic and Randomized Methods for Design under Uncertainty (Springer, London), 3–47.Crossref, Google Scholar
• Norkin VI (2018) Optimization models of anti-terrorist protection. Cybernetics Systems Anal. 54(6):918–929.Crossref, Google Scholar
• Pagnoncelli BK, Ahmed S, Shapiro A (2009) Sample average approximation method for chance constrained programming: Theory and applications. J. Optim. Theory Appl. 142(2):399–416.Crossref, Google Scholar
• Prékopa A (1990) Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution. Math. Methods Oper. Res. 34(6):441–461.Crossref, Google Scholar
• Prékopa A (2003) Probabilistic programming. Ruszczyński A, Shapiro A, eds. Stochastic Programming: Handbooks in Operations Research and Management Science, vol. 10 (Elsevier, Amsterdam), 267–351.Crossref, Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801–817.Crossref, Google Scholar
• Rebennack S, Reinelt G, Pardalos PM (2012) A tutorial on branch and cut algorithms for the maximum stable set problem. Internat. Trans. Oper. Res. 19(1–2):161–199.Crossref, Google Scholar
• Richard JPP (2011) Lifting techniques for mixed integer programming. Cochran JJ, Cox LA Jr, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Inc., Hoboken, NJ).Crossref, Google Scholar
• Saxena A, Goyal V, Lejeune MA (2010) MIP reformulations of the probabilistic set covering problem. Math. Programming 121(1):1–31.Crossref, Google Scholar
• Shen H, Jiang R (2023) Chance-constrained set covering with Wasserstein ambiguity. Math. Programming 198(1):621–674.Crossref, 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.Crossref, 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
• Toregas C, Swain R, ReVelle CS, Bergman L (1971) The location of emergency service facilities. Oper. Res. 19(6):1363–1373.Link, 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. 33(4):1661–1677.Abstract, Google Scholar
• Wolsey LA (1976) Facets and strong valid inequalities for integer programs. Oper. Res. 24(2):367–372.Link, Google Scholar
• Wu HH, Küçükyavuz S (2019) Probabilistic partial set covering with an oracle for chance constraints. SIAM J. Optim. 29(1):690–718.Crossref, Google Scholar
• Wu HH, Küçükyavuz S (2020) An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions. Oper. Res. Lett. 48(3):356–361.Crossref, Google Scholar
• Wu P, Wu X, Chen G (2016) Rest with eyes open: Stochastic target coverage in wireless sensor networks with data fusion. Internat. J. Sensor Networks 20(1):16–25.Crossref, Google Scholar