Technical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization

References

• Ambrosius M, Grimm V, Kleinert T, Liers F, Schmidt M, Zöttl G (2018) Endogenous price zones and investment incentives in electricity markets: An application of multilevel optimization with graph partitioning. Technical report. Accessed November 3, 2019, http://www.optimization-online.org/DB_HTML/2018/10/6868.html.Google Scholar
• Audet C, Hansen P, Jaumard B, Savard G (1997) Links between linear bilevel and mixed 0–1 programming problems. J. Optim. Theory Appl. 93(2):273–300.Crossref, Google Scholar
• Bard JF (2013) Practical Bilevel Optimization: Algorithms and Applications, vol. 30 (Springer Science & Business Media, New York).Google Scholar
• Bard JF (1991) Some properties of the bilevel programming problem. J. Optim. Theory Appl. 68(2):371–378.Crossref, Google Scholar
• Bard JF, Moore JT (1990) A branch and bound algorithm for the bilevel programming problem. SIAM J. Sci. Statist. Comput. 11(2):281–292.Crossref, Google Scholar
• Bialas WF, Karwan MH (1984) Two-level linear programming. Management Sci. 30(8):1004–1020.Link, Google Scholar
• Bracken J, McGill JT (1973) Mathematical programs with optimization problems in the constraints. Oper. Res. 21(1):37–44.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
• Casorrán C, Fortz B, Labbé M, Ordóñez F (2019) A study of general and security Stackelberg game formulations. Eur. J. Oper. Res. 278(3):855–868.Google Scholar
• Daxhelet O, Smeers Y (2007) The EU regulation on cross-border trade of electricity: A two-stage equilibrium model. Eur. J. Oper. Res. 181(3):1396–1412.Crossref, Google Scholar
• Dempe S (2018) Bilevel optimization: Theory, algorithms, and applications. Technical report, http://www.optimization-online.org/DB_HTML/2018/08/6773.html.Google Scholar
• Dempe S (2002) Foundations of Bilevel Programming (Springer, New York).Google Scholar
• Dempe S, Kalashnikov V, Pérez-Valdés GA, Kalashnykova N (2015) Bilevel Programming Problems (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• DeNegre S (2011) Interdiction and discrete bilevel linear programming. PhD thesis, Lehigh University, Bethlehem, PA.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.Google Scholar
• Fukuda K, Liebling TM, Margot F (1997) Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. Comput. Geometry 8(1):1–12.Crossref, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York).Google Scholar
• Grimm V, Schewe L, Schmidt M, Zöttl G (2018) A multilevel model of the European entry-exit gas market. Math. Methods Oper. Res. 89(2):223–255.Google Scholar
• Grimm V, Grübel J, Schewe L, Schmidt M, Zöttl G (2019a) Nonconvex equilibrium models for gas market analysis: Failure of standard techniques and alternative modeling approaches. Eur. J. Oper. Res. 273(3):1097–1108.Crossref, Google Scholar
• Grimm V, Kleinert T, Liers F, Schmidt M, Zöttl G (2019b) Optimal price zones of electricity markets: A mixed-integer multilevel model and global solution approaches. Optim. Methods Software 34(2):406–436.Crossref, Google Scholar
• Grimm V, Martin A, Schmidt M, Weibelzahl M, Zöttl G (2016) Transmission and generation investment in electricity markets: The effects of market splitting and network fee regimes. Eur. J. Oper. Res. 254(2):493–509.Crossref, Google Scholar
• Hansen P, Jaumard B, Savard G (1992) New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Statist. Comput. 13(5):1194–1217.Crossref, Google Scholar
• Hu X, Ralph D (2007) Using EPECs to model bilevel games in restructured electricity markets with locational prices. Oper. Res. 55(5):809–827.Link, Google Scholar
• Karp RM (1975) On the computational complexity of combinatorial problems. Networks 5(1):45–68.Crossref, Google Scholar
• Kleinert T, Schmidt M (2019) Global optimization of multilevel electricity market models including network design and graph partitioning. Discrete Optim. 33:43–69.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
• Labbé M, Violin A (2013) Bilevel programming and price setting problems. 4OR 11(1):1–30.Crossref, Google Scholar
• Nocedal J, Wright SJ (2006) Numerical Optimization, 2nd ed., Springer Series in Operations Research and Financial Engineering (Springer, New York).Google Scholar
• Paruchuri P, Pearce JP, Marecki J, Tambe M, Ordonez F, Kraus S (2008) Playing games for security: An efficient exact algorithm for solving Bayesian Stackelberg games. Proc. 7th Internat. Joint Conf. Autonomous Agents Multiagent Systems, vol. 2 (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 895–902.Google Scholar
• Pineda S, Morales JM (2019) Solving linear bilevel problems using big-Ms: Not all that glitters is gold. IEEE Trans. Power Systems 34(3):2469–2471.Crossref, Google Scholar
• Rusmevichientong P, Van Roy B, Glynn PW (2006) A nonparametric approach to multiproduct pricing. Oper. Res. 54(1):82–98.Link, Google Scholar
• Vicente L, Savard G, Júdice J (1994) Descent approaches for quadratic bilevel programming. J. Optim. Theory Appl. 81(2):379–399.Crossref, Google Scholar
• Wen U-P, Hsu S-T (1991) Linear bi-level programming problems—A review. J. Oper. Res. Soc. 42(2):125–133.Google Scholar
• Williams A (1970) Boundedness relations for linear constraint sets. Linear Algebra Appl. 3(2):129–141.Crossref, Google Scholar