A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation

Bard, J.F.: Practical Bilevel Optimization: Algorithms and Applications. Kluwer Academic Publishers (1998)

Computational Infrastructure for Operations Research. https://www.coin-or.org (2018)

Salmeron, J., Wood, K., Baldick, R.: Analysis of electric grid security under terrorist threat. IEEE Trans. Power Syst. 19(2), 905–912 (2004)

Bienstock, D., Verma, A.: The NK problem in power grids: new models, formulations, and numerical experiments. SIAM J. Optim. 20(5), 2352–2380 (2010)

Zhang, Y., Snyder, L., Ralphs, T., Xue, Z.: The competitive facility location problem under disruption risks. Transp. Res. Part E Logist. Transp. Rev. 93, 453–473 (2016). https://doi.org/10.1016/j.tre.2016.07.002

Gao, J., You, F.: Design and optimization of shale gas energy systems: overview, research challenges, and future directions. Comput. Chem. Eng. 106, 699–718 (2017)

Loridan, P., Morgan, J.: Weak via strong stackelberg problem: new results. J. Glob. Optim. 8(3), 263–287 (1996)

Vicente, L., Savard, G., Júdice, J.: Discrete linear bilevel programming problem. J. Optim. Theory Appl. 89(3), 597–614 (1996)

Israeli, E.: System interdiction and defense. Ph.D. thesis, Naval Postgraduate School (1999)

DeNegre, S.: Interdiction and Discrete Bilevel Linear Programming. Ph.D. Lehigh University (2011). http://coral.ie.lehigh.edu/~ted/files/papers/ScottDeNegreDissertation11.pdf

Jeroslow, R.: The polynomial hierarchy and a simple model for competitive analysis. Math. Program. 32, 146–164 (1985)

Moore, J.T., Bard, J.F.: The mixed integer linear bilevel programming problem. Oper. Res. 38(5), 911–921 (1990)

Von Stackelberg, H.: Marktform und Gleichgewicht. Julius Springer, Berlin (1934)

Bracken, J., McGill, J.T.: Mathematical programs with optimization problems in the constraints. Oper. Res. 21(1), 37–44 (1973)

Wollmer, R.: Removing arcs from a network. Oper. Res. 12(6), 934–940 (1964)

Bard, J.F., Moore, J.T.: An algorithm for the discrete bilevel programming problem. Nav. Res. Logist. 39(3), 419–435 (1992)

Wen, U.P., Huang, A.: A simple tabu search method to solve the mixed-integer linear bilevel programming problem. Eur. J. Oper. Res. 88, 563–571 (1996)

Faísca, N.P., Dua, V., Rustem, B., Saraiva, P.M., Pistikopoulos, E.N.: Parametric global optimisation for bilevel programming. J. Glob. Optim. 38, 609–623 (2007)

DeNegre, S., Ralphs, T.: A branch-and-cut algorithm for bilevel integer programming. In: Proceedings of the Eleventh INFORMS Computing Society Meeting, pp. 65–78 (2009). https://doi.org/10.1007/978-0-387-88843-9_4. http://coral.ie.lehigh.edu/~ted/files/papers/BILEVEL08.pdf

Xu, P., Wang, L.: An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Comput. Oper. Res. 41, 309–318 (2014)

Zeng, B., An, Y.: Solving bilevel mixed integer program by reformulations and decomposition. Tech. rep., University of South Florida (2014). http://www.optimization-online.org/DB_FILE/2014/07/4455.pdf

Caramia, M., Mari, R.: Enhanced exact algorithms for discrete bilevel linear problems. Optim. Lett. 9(7), 1447–1468 (2015)

Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: Bilevel knapsack with interdiction constraints. INFORMS J. Comput. 28(2), 319–333 (2016)

Hemmati, M., Smith, J.C.: A mixed-integer bilevel programming approach for a competitive prioritized set covering problem. Discrete Optim. 20, 105–134 (2016)

Wang, L., Xu, P.: The watermelon algorithm for the bilevel integer linear programming problem. SIAM J. Optim. 27(3), 1403–1430 (2017)

Lozano, L., Smith, J.C.: A value-function-based exact approach for the bilevel mixed-integer programming problem. Oper. Res. 65(3), 768–786 (2017)

Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M.: On the use of intersection cuts for bilevel optimization. Math. Program. 172, 77–103 (2018)

Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M.: A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper. Res. 65(6), 1615–1637 (2017)

Mitsos, A.: Global solution of nonlinear mixed integer bilevel programs. J. Glob. Optim. 47, 557–582 (2010)

Kleniati, P.M., Adjiman, C.S.: Branch-and-sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part I: theoretical development. J. Glob. Optim. 60, 425–458 (2014)

Kleniati, P.M., Adjiman, C.S.: Branch-and-sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part II: convergence analysis and numerical results. J. Glob. Optim. 60, 459–481 (2014)

Padberg, M., Rinaldi, G.: Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Oper. Res. Lett. 6(1), 1–7 (1987)

Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale traveling salesman problems. SIAM Rev. 33, 60–100 (1991)

Land, A.H., Doig, A.G.: An automatic method for solving discrete programming problems. Econometrica 28, 497–520 (1960)

Achterberg, T.: Constraint integer programming. Ph.D. thesis. https://doi.org/10.14279/depositonce-1634 (2007)

Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42–54 (2005)

Marchand, H., Martin, A., Weismantel, R., Wolsey, L.: Cutting planes in integer and mixed integer programming. Discrete Appl. Math. 123(1), 397–446 (2002)

Wolter, K.: Implementation of Cutting Plane Separators for Mixed Integer Programs. Master’s thesis, Technische Universität Berlin (2006)

Balas, E., Jeroslow, R.: Canonical cuts on the unit hypercube. SIAM J. Appl. Math. 23(1), 61–69 (1972)

Balas, E.: Intersection cuts-a new type of cutting planes for integer programming. Oper. Res. 19(1), 19–39 (1971)

Ehrgott, M., Wiecek, M.M.: Multiobjective programming. In: Ehrgott, M., Figueira, J., Greco, S. (eds.) Multiple Criteria Decision Analysis: State of the Art Surveys, pp. 667–722. Springer, Berlin (2005)

Geoffrion, A.M.: Proper efficiency and the theory of vector maximization. J. Math. Anal. Appl. 22, 618–630 (1968)

DeNegre, S., Ralphs, T., Tahernejad, S.: version 1.1.2 (2017). https://doi.org/10.5281/zenodo.1439384. https://github.com/coin-or/MibS

Xu, Y., Ralphs, T., Ladányi, L., Saltzman, M.: Computational experience with a software framework for parallel integer programming. INFORMS J. Comput. 21, 383–397 (2009). https://doi.org/10.1287/ijoc.1090.0347

Ralphs, T., Ladányi, L., Saltzman, M.: A library hierarchy for implementing scalable parallel search algorithms. J. Supercomput. 28, 215–234 (2004). https://doi.org/10.1023/B:SUPE.0000020179.55383.ad

Xu, Y., Ralphs, T.: ALPS version 1.5.6 (2019). https://doi.org/10.5281/zenodo.245971. https://github.com/coin-or/CHiPPS-ALPS

Xu, Y., Ralphs, T., Ladányi, L., Saltzman, M.: ALPS: a framework for implementing parallel tree search algorithms. In: The Proceedings of the Ninth INFORMS Computing Society Conference, vol. 29, pp. 319–334 (2005). https://doi.org/10.1007/0-387-23529-9_21

Xu, Y., Ralphs, T.: BiCEPs version 0.94.4 (2017). https://doi.org/10.5281/zenodo.245652. https://github.com/coin-or/CHiPPS-BiCePS

Xu, Y., Ralphs, T.: BLIS version 0.94.5 (2017). https://doi.org/10.5281/zenodo.246079. https://github.com/coin-or/CHiPPS-BLIS

Forrest, J.J.: Clp version 1. 16 (2017). https://github.com/coin-or/Clp

Ralphs, T., Güzelsoy, M., Mahajan, A.: SYMPHONY version 5.6.16 (2017). https://doi.org/10.5281/zenodo.248734

Ralphs, T., Güzelsoy, M.: The SYMPHONY callable library for mixed integer programming. In: Proceedings of the Ninth INFORMS Computing Society Conference, pp. 61–76 (2005). https://doi.org/10.1007/0-387-23529-9_5. http://coral.ie.lehigh.edu/~ted/files/papers/SYMPHONY04.pdf

Cgl version 0.59 (2017). https://github.com/coin-or/Cgl

Osi version 0.107 (2017). https://github.com/coin-or/Osi

Hassanzadeh, A., Ralphs, T.: A Generalized Benders’ Algorithm for Two-Stage Stochastic Program with Mixed Integer Recourse. Tech. rep., COR@L Laboratory Report 14T-005, Lehigh University (2014). http://coral.ie.lehigh.edu/~ted/files/papers/SMILPGenBenders14.pdf

Ralphs, T., Güzelsoy, M.: Duality and warm starting in integer programming. In: The Proceedings of the 2006 NSF Design, Service, and Manufacturing Grantees and Research Conference (2006). http://coral.ie.lehigh.edu/~ted/files/papers/DMII06.pdf

Ibm ILOG CPLEX Optimizer. https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/ (2017)

Forrest, J.J.: Cbc version 2.9 (2017). https://projects.coin-or.org/Cbc

Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.: An updated mixed integer programming library: Miplib 3.0. Tech. rep. (1998)