Network Relaxations for Combinatorial Bilevel Optimization Under Linear Interactions

References

• Ahmed S, Tawarmalani M, Sahinidis NV (2004) A finite branch-and-bound algorithm for two-stage stochastic integer programs. Math. Programming 100(2):355–377.Crossref, Google Scholar
• Alpert CJ, Kahng AB (1997) Splitting an ordering into a partition to minimize diameter. J. Classification 14(1):51–74.Crossref, Google Scholar
• Arroyo JM (2010) Bilevel programming applied to power system vulnerability analysis under multiple contingencies. IET Generation Transmission Distribution 4(2):178–190.Crossref, Google Scholar
• Audet C, Haddad J, Savard G (2007) Disjunctive cuts for continuous linear bilevel programming. Optim. Lett. 1:259–267.Crossref, Google Scholar
• Bard JF, Falk JE (1982) An explicit solution to the multi-level programming problem. Comput. Oper. Res. 9(1):77–100.Crossref, Google Scholar
• Bazgan C, Toubaline S, Tuza Z (2011) The most vital nodes with respect to independent set and vertex cover. Discrete Appl. Math. (1979) 159(17):1933–1946.Crossref, Google Scholar
• Bergman D, Cire AA (2018) Discrete nonlinear optimization by state-space decompositions. Management Sci. 64(10):4700–4720.Link, Google Scholar
• Bergman D, Cire AA, Van Hoeve WJ, Hooker J (2016) Decision Diagrams for Optimization, vol. 1. (Springer, New York).Crossref, Google Scholar
• Bracken J, McGill JT (1973) Mathematical programs with optimization problems in the constraints. Oper. Res. 21(1):37–44.Link, Google Scholar
• Brotcorne L, Hanafi S, Mansi R (2013) One-level reformulation of the bilevel knapsack problem using dynamic programming. Discrete Optim. 10(1):1–10.Crossref, Google Scholar
• Brucker P (1978) On the complexity of clustering problems. Henn R, Korte B, Oettli W, eds. Optimization and Operations Research, Lecture Notes in Economics and Mathematical Systems, vol. 157 (Springer, Berlin), 45–54.Google Scholar
• Bui QM, Carvalho M, Neto J (2025) Solving combinatorial pricing problems using embedded dynamic programming models. INFORMS J. Comput. 38(2):548–567.Link, 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 (2016) Bilevel knapsack with interdiction constraints. INFORMS J. Comput. 28(2):319–333.Link, Google Scholar
• Carvalho M (2023) Bilevel knapsack problems. Pardalos PM, Prokopyev OA, eds. Encyclopedia of Optimization (Springer, Cham, Switzerland), 1–7.Crossref, Google Scholar
• Castro MP, Cire AA, Beck JC (2022) Decision diagrams for discrete optimization: A survey of recent advances. INFORMS J. Comput. 34(4):2271–2295.Link, Google Scholar
• Chen X, Diakonikolas I, Paparas D, Sun X, Yannakakis M (2018) The complexity of optimal multidimensional pricing for a unit-demand buyer. Games Econom. Behav. 110:139–164.Crossref, Google Scholar
• Colson B, Marcotte P, Savard G (2007) An overview of bilevel optimization. Ann. Oper. Res. 153:235–256.Crossref, Google Scholar
• Costa MC, de Werra D, Picouleau C (2011) Minimum d-blockers and d-transversals in graphs. J. Combin. Optim. 22(4):857–872.Crossref, Google Scholar
• Davarnia D, Van Hoeve WJ (2021) Outer approximation for integer nonlinear programs via decision diagrams. Math. Programming 187:111–150.Crossref, Google Scholar
• Dempe S, Kalashnikov V, Pérez-Valdés GA, Kalashnykova N (2015) Bilevel Programming Problems: Theory, Algorithms and Applications to Energy Networks, Energy Systems (Springer, Berlin, Heidelberg), 978–973.Google Scholar
• DeNegre ST, Ralphs TK (2009) A branch-and-cut algorithm for integer bilevel linear programs. Chinneck JW, Kristjansson B, Saltzman MJ, eds. Operations Research and Cyber-Infrastructure (Springer, New York), 65–78.Crossref, Google Scholar
• Dutta J, Dempe S (2006) Bilevel programming with convex lower level problems. Dempe S, Kalashnikov V, eds. Optimization with Multivalued Mappings, Springer Optimization and Its Applications, vol. 2 (Springer, Boston), 51–71.Crossref, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2016) Intersection cuts for bilevel optimization. Louveaux Q, Skutella M, eds. Integer Programming and Combinatorial Optimization. IPCO 2016, Lecture Notes in Computer Science, vol. 9682 (Springer, Cham, Switzerland), 77–88.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
• Fortuny-Amat J, McCarl B (1981) A representation and economic interpretation of a two-level programming problem. J. Oper. Res. Soc. 32(9):783–792.Crossref, Google Scholar
• Ghatkar S, Arulselvan A, Morton A (2023) Solution techniques for bi-level knapsack problems. Comput. Oper. Res. 159:106343.Crossref, Google Scholar
• Hemmati M, Smith JC, Thai MT (2014) A cutting-plane algorithm for solving a weighted influence interdiction problem. Comput. Optim. Appl. 57(1):71–104.Crossref, Google Scholar
• Hooker JN (2013) Decision diagrams and dynamic programming. Gomes C, Sellmann M, eds. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2013, Lecture Notes in Computer Science, vol. 7874 (Springer, Berlin, Heidelberg), 94–110.Google Scholar
• Kınay ÖB, Gzara F, Alumur SA (2023) Charging station location and sizing for electric vehicles under congestion. Transportation Sci. 57(6):1433–1451.Abstract, Google Scholar
• Kleinert T, Labbé M, Ljubić I, Schmidt M (2021a) A survey on mixed-integer programming techniques in bilevel optimization. EURO J. Comput. Optim. 9:100007.Crossref, Google Scholar
• Kleinert T, Labbé M, Plein F, Schmidt M (2021b) Closing the gap in linear bilevel optimization: A new valid primal-dual inequality. Optim. Lett. 15(4):1027–1040.Crossref, Google Scholar
• Kong N, Schaefer AJ, Hunsaker B (2006) Two-stage integer programs with stochastic right-hand sides: A superadditive dual approach. Math. Programming 108(2):275–296.Crossref, Google Scholar
• Köppe M, Louveaux Q, Weismantel R (2008) Intermediate integer programming representations using value disjunctions. Discrete Optim. 5(2):293–313.Crossref, Google Scholar
• Köppe M, Queyranne M, Ryan CT (2010) Parametric integer programming algorithm for bilevel mixed integer programs. J. Optim. Theory Appl. 146(1):137–150.Crossref, Google Scholar
• Labbé M, Marcotte P, Savard G (1998) A bilevel model of taxation and its application to optimal highway pricing. Management Sci. 44(12-part-1):1608–1622.Link, 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
• Lozano L, Bergman D, Cire A (2024) Constrained shortest-path reformulations via decision diagrams for structured two-stage optimization problems. Preprint, submitted June 26, https://arxiv.org/abs/2206.12962.Google Scholar
• Luo ZQ, Pang JS, Ralph D (1996) Mathematical programs with equilibrium constraints: A sequential approach. Comput. Optim. Appl. 5(2):123–156.Google Scholar
• Moore JT, Bard JF (1990) The mixed integer linear bilevel programming problem. Oper. Res. 38(5):911–921.Link, Google Scholar
• Morton DP, Pan F, Saeger KJ (2007) Models for nuclear smuggling interdiction. IIE Trans. 39(1):3–14.Crossref, Google Scholar
• Nie J, Wang L, Ye JJ (2017) Bilevel polynomial programs and semidefinite relaxation methods. SIAM J. Optim. 27(3):1728–1757.Crossref, Google Scholar
• Outrata JV (1990) On the numerical solution of a class of Stackelberg problems. Zeitschrift Für Oper. Res. 34:255–277.Google Scholar
• Pajouh F, Boginski V, Pasiliao EL (2014) Minimum vertex blocker clique problem. Networks 64(1):48–64.Crossref, Google Scholar
• Qi M, Jiang R, Shen S (2022) Sequential competitive facility location: Exact and approximate algorithms. Oper. Res. 72(1):300–316.Link, Google Scholar
• Sherali HD, Smith JC (2001) Improving discrete model representations via symmetry considerations. Management Sci. 47(10):1396–1407.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
• Tavaslıoğlu O, Prokopyev OA, Schaefer AJ (2019) Solving stochastic and bilevel mixed-integer programs via a generalized value function. Oper. Res. 67(6):1659–1677.Link, Google Scholar
• Thürauf J, Kleinert T, Ljubić I, Ralphs T, Schmidt M (2024) Bobilib: Bilevel optimization (benchmark) instance library. Accessed September 15, 2025, https://optimization-online.org/?p=27063.Google Scholar
• Vásquez S, Lozano L, van Hoeve W-J (2025) A single-level reformulation of integer bilevel programs. Math. Programming, ePub ahead of print, December 16, https://doi.org/10.1007/s10107-025-02294-1.Google Scholar
• Zare MH, Özaltın OY, Prokopyev OA (2018) On a class of bilevel linear mixed-integer programs in adversarial settings. J. Global Optim. 71(1):91–113.Crossref, Google Scholar