A Bilevel Optimization Approach for a Class of Combinatorial Problems with Disruptions and Probing

References

• Adamczyk M, Sviridenko M, Ward J (2016) Submodular stochastic probing on matroids. Math. Oper. Res. 41(3):1022–1038.Link, Google Scholar
• Alizadeh SM, Marcotte P, Savard G (2013) Two-stage stochastic bilevel programming over a transportation network. Transportation Res. Part B Methodological 58:92–105.Crossref, Google Scholar
• Artstein Z (1994) Probing for information in two-stage stochastic programming and the associated consistency. Asymptotic Statist.: Proc. 5th Prague Sympos. (Springer, Berlin), 21–33.Google Scholar
• Artstein Z (1999) Gains and costs of information in stochastic programming. Ann. Oper. Res. 85(0):129–152.Crossref, Google Scholar
• Artstein Z, Wets RJ (1993) Sensors and information in optimization under stochastic uncertainty. Math. Oper. Res. 18(3):523–547.Link, Google Scholar
• Beck Y, Ljubić I, Schmidt M (2023) A survey on bilevel optimization under uncertainty. Eur. J. Oper. Res. 311(2):401–426.Crossref, Google Scholar
• Cappanera P, Scaparra MP (2011) Optimal allocation of protective resources in shortest-path networks. Transportation Sci. 45(1):64–80.Link, Google Scholar
• Caprara A, Carvalho M, Lodi A, Woeginger GJ (2013) A complexity and approximability study of the bilevel knapsack problem. Proc. 16th Internat. Conf. Integer Programming Combinatorial Optim., vol. 16 (Springer, Berlin), 98–109.Google Scholar
• Cormican KJ, Morton DP, Wood RK (1998) Stochastic network interdiction. Oper. Res. 46(2):184–197.Link, Google Scholar
• Dempe S (2002) Foundations of Bilevel Programming (Kluwer Academic Publishers, Boston).Google Scholar
• DeNegre S, Ralphs TK (2009) A branch-and-cut algorithm for bilevel integer programming. Proc. 11th INFORMS Comput. Soc. Meeting (INFORMS, Catonsville, MD), 65–78.Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2017) A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper. Res. 65(6):1615–1637.Link, Google Scholar
• Goel V, Grossmann IE (2004) A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Comput. Chemical Engrg. 28(8):1409–1429.Crossref, Google Scholar
• Goel A, Guha S, Munagala K (2010) How to probe for an extreme value. ACM Trans. Algorithms 7(1):1–20.Crossref, Google Scholar
• Guha S, Munagala K (2012) Adaptive uncertainty resolution in Bayesian combinatorial optimization problems. ACM Trans. Algorithms 8(1):1–23.Crossref, Google Scholar
• Gümüş ZH, Floudas CA (2005) Global optimization of mixed-integer bilevel programming problems. Comput. Management Sci. 2:181–212.Crossref, Google Scholar
• Gupta A, Nagarajan V (2013) A stochastic probing problem with applications. Proc. 16th Internat. Conf. Integer Programming Combinatorial Optim., vol. 16 (Springer, Berlin), 205–216.Google Scholar
• Gupta A, Nagarajan V, Singla S (2016) Algorithms and adaptivity gaps for stochastic probing. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1731–1747.Google Scholar
• Hellemo L, Barton PI, Tomasgard A (2018) Decision-dependent probabilities in stochastic programs with recourse. Comput. Management Sci. 15:369–395.Crossref, Google Scholar
• Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97–111.Crossref, Google Scholar
• Janjarassuk U, Linderoth J (2008) Reformulation and sampling to solve a stochastic network interdiction problem. Networks 52(3):120–132.Crossref, Google Scholar
• Jonsbråten TW, Wets RJ, Woodruff DL (1998) A class of stochastic programs with decision dependent random elements. Ann. Oper. Res. 82(0):83–106.Crossref, Google Scholar
• Kleinert T, Labbé M, Ljubić I, Schmidt M (2021) A survey on mixed-integer programming techniques in bilevel optimization. EURO J. Comput. Optim. 9:100007.Crossref, Google Scholar
• Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Lozano L, Borrero JS (2024) A bilevel optimization approach for a class of combinatorial problems with disruptions and probing. http://dx.doi.org/10.1287/ijoc.2024.0629.cd, https://github.com/INFORMSJoC/2024.0629.Google Scholar
• Lozano L, Smith JC (2017a) A backward sampling framework for interdiction problems with fortification. INFORMS J. Comput. 29(1):123–139.Link, Google Scholar
• Lozano L, Smith JC (2017b) A value-function-based exact approach for the bilevel mixed-integer programming problem. Oper. Res. 65(3):768–786.Link, Google Scholar
• McCormick GP (1976) Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems. Math. Programming 10(1):147–175.Crossref, Google Scholar
• Mitsos A (2010) Global solution of nonlinear mixed-integer bilevel programs. J. Global Optim. 47(4):557–582.Crossref, Google Scholar
• Özaltın OY, Prokopyev OA, Schaefer AJ (2018) Optimal design of the seasonal influenza vaccine with manufacturing autonomy. INFORMS J. Comput. 30(2):371–387.Link, Google Scholar
• Tahernejad S, Ralphs TK, DeNegre ST (2020) A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Math. Programming Comput. 12(4):529–568.Crossref, Google Scholar
• Verweij B, Ahmed S, Kleywegt AJ, Nemhauser G, Shapiro A (2003) The sample average approximation method applied to stochastic routing problems: A computational study. Comput. Optim. Appl. 24:289–333.Crossref, Google Scholar