A New General-Purpose Algorithm for Mixed-Integer Bilevel Linear Programs

References

• Andersen K, Cornuéjols G, Li Y (2005) Split closure and intersection cuts. Math. Programming 102(3):457–493.Crossref, Google Scholar
• Andersen K, Louveaux Q, Wolsey L, Weismantel R (2007) Inequalities from two rows of a simplex tableau. Fischetti M, Williamson DP, eds. Proc. 12th Internat. Conf. Integer Programming Combinatiorial Optimization, IPCO, (Springer, Berlin), 1–15.Crossref, Google Scholar
• Audet C, Haddad J, Savard G (2007) Disjunctive cuts for continuous linear bilevel programming. Optim. Lett. 1(3):259–267.Crossref, Google Scholar
• Baggio A, Carvalho M, Lodi A, Tramontani A (2016) Multilevel approaches for the critical node problem. Working paper, École Polytechnique de Montréal, Montréal, Canada.Google Scholar
• Balas E (1971) Intersection cuts–A new type of cutting planes for integer programming. Oper. Res. 19(1):19–39.Link, Google Scholar
• Balas E (1972) Integer programming and convex analysis: Intersection cuts from outer polars. Math. Programming 2(1):330–382.Crossref, Google Scholar
• Basu A, Bonami P, Cornuéjols G, Margot F (2011a) Experiments with two-row cuts from degenerate tableaux. INFORMS J. Comput. 23(4):578–590.Link, Google Scholar
• Basu A, Bonami P, Cornuéjols G, Margot F (2011b) On the relative strength of split, triangle and quadrilateral cuts. Math. Programming 126(2):281–314.Crossref, Google Scholar
• Bhattacharjee B, Green WH, Barton PI (2005a) Interval methods for semi-infinite programs. Comput. Optim. Appl. 30(1):63–93.Crossref, Google Scholar
• Bhattacharjee B, Lemonidis P, Green WH Jr, Barton PI (2005b) Global solution of semi-infinite programs. Math. Programming 103(2):283–307.Crossref, Google Scholar
• Bixby RE, Ceria S, McZeal CM, Savelsbergh MWP (1998) An updated mixed integer programming library: MIPLIB 3.0. Optima 58:12–15.Google Scholar
• Bracken J, McGill J (1973) Mathematical programs with optimization problems in the constraints. Oper. Res. 21(1):37–44.Link, Google Scholar
• Brotcorne L, Labbé M, Marcotte P, Savard G (2008) Joint design and pricing on a network. Oper. Res. 56(5):1104–1115.Link, Google Scholar
• Brown G, Carlyle M, Salmerón J, Wood K (2006) Defending critical infrastructure. Interfaces 36(6):530–544.Link, Google Scholar
• Caramia M, Mari R (2015) Enhanced exact algorithms for discrete bilevel linear problems. Optim. Lett. 9(7):1447–1468.Crossref, Google Scholar
• Conforti M, Cornuéjols G, Zambelli G (2010) Equivalence between intersection cuts and the corner polyhedron. Oper. Res. Lett. 38(3):153–155.Crossref, Google Scholar
• Conforti M, Cornuejols G, Zambelli G (2014) Integer Programming (Springer International, Cham, Switzerland).Crossref, Google Scholar
• DeNegre S (2011) Interdiction and discrete bilevel linear programming. PhD thesis, Lehigh University, Bethlehem, PA.Google Scholar
• DeNegre S, Ralphs TK (2009) A branch-and-cut algorithm for integer bilevel linear programs. Operations Research and Cyber-Infrastructure (Springer New York), 65–78.Crossref, Google Scholar
• Dey SS, Lodi A, Tramontani A, Wolsey LA (2014) On the practical strength of two-row tableau cuts. INFORMS J. Comput. 26(2):222–237.Link, Google Scholar
• Dolan ED, Moré J (2002) Benchmarking optimization software with performance profiles. Math. Programming 91(2):201–213.Crossref, Google Scholar
• Faísca NP, Dua V, Rustem B, Saraiva PM, Pistikopoulos EN (2007) Parametric global optimisation for bilevel programming. J. Global Optim. 38(4):609–623.Crossref, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2016) Intersection cuts for bilevel optimization. Louveaux Q, Skutella M, eds. Proc. 18th Internat. Conf. Integer Programming Combinatorial Optimization, IPCO (Springer International, Cham, Switzerland), 77–88.Crossref, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2017a) Instances and solver software for mixed-integer bilevel linear problems. Accessed March 2017, https://msinnl.github.io/pages/bilevel.html.Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2017b) On the use of intersection cuts for bilevel optimization. Math. Programming. ePub ahead of print September 16, https://doi.org/10.1007/s10107-017-1189-5.Crossref, Google Scholar
• Floudas CA, Stein O (2007) The adaptive convexification algorithm: A feasible point method for semi-infinite programming. SIAM J. Optim. 18(4):1187–1208.Crossref, Google Scholar
• Garcia-Herreros P, Zhang L, Misra P, Arslan E, Mehta S, Grossmann IE (2016) Mixed-integer bilevel optimization for capacity planning with rational markets. Comput. Chemical Engrg. 86:33–47.Crossref, Google Scholar
• Gilbert F, Marcotte P, Savard G (2015) A numerical study of the logit network pricing problem. Transportation Sci. 49(3):706–719.Link, Google Scholar
• Glover F (1974) Polyhedral convexity cuts and negative edge extensions. Zeitschrift für Oper. Res. 18(5):181–186.Crossref, Google Scholar
• Glover F, Klingman D (1976) Improved convexity cuts for lattice point problems. J. Optim. Theory Appl. 19(2):283–291.Crossref, Google Scholar
• Gümüs ZH, Floudas CA (2005) Global optimization of mixed-integer bilevel programming problems. Comput. Management Sci. 2(3):181–212.Crossref, Google Scholar
• Jeroslow RG (1985) The polynomial hierarchy and a simple model for competitive analysis. Math. Programming 32(2):146–164.Crossref, Google Scholar
• Kleniati PM, Adjiman CS (2015) A generalization of the branch-and-sandwich algorithm: From continuous to mixed-integer nonlinear bilevel problems. Comput. Chemical Engrg. 72:373–386.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
• Kunisch K, Pock T (2013) A bilevel optimization approach for parameter learning in variational models. SIAM J. Imaging Sci. 6(2):938–983.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):1608–1622.Link, Google Scholar
• Loridan P, Morgan J (1996) Weak via strong Stackelberg problem: New results. J. Global Optim. 8(3):263–297.Crossref, Google Scholar
• Mitsos A (2010) Global solution of nonlinear mixed-integer bilevel programs. J. Global Optim. 47(4):557–582.Crossref, Google Scholar
• Mitsos A, Lemonidis P, Lee CK, Barton PI (2008) Relaxation-based bounds for semi-infinite programs. SIAM J. Optim. 19(1):77–113.Crossref, Google Scholar
• Moore J, Bard J (1990) The mixed integer linear bilevel programming problem. Oper. Res. 38(5):911–921.Link, Google Scholar
• Outrata J (1990) On the numerical solution of a class of Stackelberg problems. Zeitschrift für Operations Research 34(4):255–277.Google Scholar
• Ralphs TK (2015) MibS. Accessed February 2016, https://github.com/tkralphs/MibS.Google Scholar
• Ralphs TK, Adams E (2016) Bilevel instance library. Accessed February 2016, http://coral.ise.lehigh.edu/data-sets/bilevel-instances/.Google Scholar
• Scaparra MP, Church RL (2008) A bilevel mixed-integer program for critical infrastructure protection planning. Comput. Oper. Res. 35(6):1905–1923.Crossref, Google Scholar
• Tang Y, Richard JPP, Smith JC (2016a) Bilevel clique instances. Accessed May 2016, http://people.clemson.edu/~jcsmith/Test_Instances_files/BCPIns.zip.Google Scholar
• Tang Y, Richard JPP, Smith JC (2016b) Bilevel knapsack instances. Accessed May 2016, http://people.clemson.edu/~jcsmith/Test_Instances_files/BKPIns.zip.Google Scholar
• Tang Y, Richard JPP, Smith JC (2016c) A class of algorithms for mixed-integer bilevel min-max optimization. J. Global Optim. 66(2):225–262.Crossref, Google Scholar
• Tsoukalas A, Rustem B, Pistikopoulos EN (2009) A global optimization algorithm for generalized semi-infinite, continuous minimax with coupled constraints and bi-level problems. J. Global Optim. 44(2):235–250.Crossref, Google Scholar
• Wood RK (2010) Bilevel Network Interdiction Models: Formulations and Solutions (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Xu P (2012) Three essays on bilevel optimization algorithms and applications. PhD thesis, Iowa State University, Ames, IA.Crossref, Google Scholar
• Xu P, Wang L (2014a) BMILP Library. Accessed October 2015, http://lzwang.public.iastate.edu/bmilplib.html.Google Scholar
• Xu P, Wang L (2014b) An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Comput. Oper. Res. 41:309–318.Crossref, Google Scholar
• Zugno M, Morales JM, Pinson P, Madsen H (2013) A bilevel model for electricity retailers’ participation in a demand response market environment. Energy Econom. 36:182–197.Crossref, Google Scholar