×

zbMATH — the first resource for mathematics

A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. (English) Zbl 1458.90488
Summary: In this paper, we describe a comprehensive algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) using a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range of bilevel optimization problems. The framework has been fully implemented in the open-source solver MibS. The paper describes the algorithmic options offered by MibS and presents computational results evaluating the effectiveness of the various options for the solution of a number of classes of bilevel optimization problems from the literature.

MSC:
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bard, J.F.: Practical Bilevel Optimization: Algorithms and Applications. Kluwer Academic Publishers (1998) · Zbl 0943.90078
[2] Computational Infrastructure for Operations Research. https://www.coin-or.org (2018)
[3] Salmeron, J.; Wood, K.; Baldick, R., Analysis of electric grid security under terrorist threat, IEEE Trans. Power Syst., 19, 2, 905-912 (2004)
[4] Bienstock, D.; Verma, A., The NK problem in power grids: new models, formulations, and numerical experiments, SIAM J. Optim., 20, 5, 2352-2380 (2010) · Zbl 1211.90140
[5] 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)
[6] 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)
[7] Loridan, P.; Morgan, J., Weak via strong stackelberg problem: new results, J. Glob. Optim., 8, 3, 263-287 (1996) · Zbl 0861.90151
[8] Vicente, L.; Savard, G.; Júdice, J., Discrete linear bilevel programming problem, J. Optim. Theory Appl., 89, 3, 597-614 (1996) · Zbl 0851.90084
[9] Israeli, E.: System interdiction and defense. Ph.D. thesis, Naval Postgraduate School (1999)
[10] DeNegre, S.: Interdiction and Discrete Bilevel Linear Programming. Ph.D. Lehigh University (2011). http://coral.ie.lehigh.edu/ ted/files/papers/ScottDeNegreDissertation11.pdf
[11] Jeroslow, R., The polynomial hierarchy and a simple model for competitive analysis, Math. Program., 32, 146-164 (1985) · Zbl 0588.90053
[12] Moore, JT; Bard, JF, The mixed integer linear bilevel programming problem, Oper. Res., 38, 5, 911-921 (1990) · Zbl 0723.90090
[13] Von Stackelberg, H.: Marktform und Gleichgewicht. Julius Springer, Berlin (1934)
[14] Bracken, J.; McGill, JT, Mathematical programs with optimization problems in the constraints, Oper. Res., 21, 1, 37-44 (1973) · Zbl 0263.90029
[15] Wollmer, R., Removing arcs from a network, Oper. Res., 12, 6, 934-940 (1964) · Zbl 0204.20102
[16] Bard, JF; Moore, JT, An algorithm for the discrete bilevel programming problem, Nav. Res. Logist., 39, 3, 419-435 (1992) · Zbl 0751.90111
[17] Wen, UP; Huang, A., A simple tabu search method to solve the mixed-integer linear bilevel programming problem, Eur. J. Oper. Res., 88, 563-571 (1996) · Zbl 0908.90194
[18] Faísca, NP; Dua, V.; Rustem, B.; Saraiva, PM; Pistikopoulos, EN, Parametric global optimisation for bilevel programming, J. Glob. Optim., 38, 609-623 (2007) · Zbl 1145.91016
[19] 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). doi:10.1007/978-0-387-88843-9_4. http://coral.ie.lehigh.edu/ ted/files/papers/BILEVEL08.pdf
[20] 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) · Zbl 1348.90496
[21] 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
[22] Caramia, M.; Mari, R., Enhanced exact algorithms for discrete bilevel linear problems, Optim. Lett., 9, 7, 1447-1468 (2015) · Zbl 1332.90170
[23] Caprara, A.; Carvalho, M.; Lodi, A.; Woeginger, GJ, Bilevel knapsack with interdiction constraints, INFORMS J. Comput., 28, 2, 319-333 (2016) · Zbl 1343.90075
[24] Hemmati, M.; Smith, JC, A mixed-integer bilevel programming approach for a competitive prioritized set covering problem, Discrete Optim., 20, 105-134 (2016) · Zbl 1387.90135
[25] Wang, L.; Xu, P., The watermelon algorithm for the bilevel integer linear programming problem, SIAM J. Optim., 27, 3, 1403-1430 (2017) · Zbl 1373.90078
[26] Lozano, L.; Smith, JC, A value-function-based exact approach for the bilevel mixed-integer programming problem, Oper. Res., 65, 3, 768-786 (2017) · Zbl 1387.90161
[27] Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M.: On the use of intersection cuts for bilevel optimization. Math. Program. 172, 77-103 (2018) · Zbl 1406.90082
[28] 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) · Zbl 1386.90085
[29] Mitsos, A., Global solution of nonlinear mixed integer bilevel programs, J. Glob. Optim., 47, 557-582 (2010) · Zbl 1202.90217
[30] Kleniati, PM; Adjiman, CS, Branch-and-sandwich: a deterministic global optimization algorithm for optimistic bilevel programming problems. Part I: theoretical development, J. Glob. Optim., 60, 425-458 (2014) · Zbl 1310.90093
[31] Kleniati, PM; Adjiman, CS, 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) · Zbl 1310.90092
[32] 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) · Zbl 0618.90082
[33] Padberg, M.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale traveling salesman problems, SIAM Rev., 33, 60-100 (1991) · Zbl 0734.90060
[34] Land, AH; Doig, AG, An automatic method for solving discrete programming problems, Econometrica, 28, 497-520 (1960) · Zbl 0101.37004
[35] Achterberg, T.: Constraint integer programming. Ph.D. thesis. doi:10.14279/depositonce-1634 (2007) · Zbl 1430.90427
[36] Achterberg, T.; Koch, T.; Martin, A., Branching rules revisited, Oper. Res. Lett., 33, 1, 42-54 (2005) · Zbl 1076.90037
[37] Marchand, H.; Martin, A.; Weismantel, R.; Wolsey, L., Cutting planes in integer and mixed integer programming, Discrete Appl. Math., 123, 1, 397-446 (2002) · Zbl 1130.90370
[38] Wolter, K.: Implementation of Cutting Plane Separators for Mixed Integer Programs. Master’s thesis, Technische Universität Berlin (2006)
[39] Balas, E.; Jeroslow, R., Canonical cuts on the unit hypercube, SIAM J. Appl. Math., 23, 1, 61-69 (1972) · Zbl 0237.52004
[40] Balas, E., Intersection cuts-a new type of cutting planes for integer programming, Oper. Res., 19, 1, 19-39 (1971) · Zbl 0219.90035
[41] Ehrgott, M.; Wiecek, MM; Ehrgott, M.; Figueira, J.; Greco, S., Multiobjective programming, Multiple Criteria Decision Analysis: State of the Art Surveys, 667-722 (2005), Berlin: Springer, Berlin · Zbl 1072.90031
[42] Geoffrion, AM, Proper efficiency and the theory of vector maximization, J. Math. Anal. Appl., 22, 618-630 (1968) · Zbl 0181.22806
[43] DeNegre, S., Ralphs, T., Tahernejad, S.: version 1.1.2 (2017). doi:10.5281/zenodo.1439384. https://github.com/coin-or/MibS
[44] 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) · Zbl 1243.90010
[45] Ralphs, T.; Ladányi, L.; Saltzman, M., A library hierarchy for implementing scalable parallel search algorithms, J. Supercomput., 28, 215-234 (2004) · Zbl 1062.90039
[46] Xu, Y., Ralphs, T.: ALPS version 1.5.6 (2019). 10.5281/zenodo.245971. https://github.com/coin-or/CHiPPS-ALPS
[47] 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). doi:10.1007/0-387-23529-9_21
[48] Xu, Y., Ralphs, T.: BiCEPs version 0.94.4 (2017). doi:10.5281/zenodo.245652. https://github.com/coin-or/CHiPPS-BiCePS
[49] Xu, Y., Ralphs, T.: BLIS version 0.94.5 (2017). 10.5281/zenodo.246079. https://github.com/coin-or/CHiPPS-BLIS
[50] Forrest, J.J.: Clp version 1. 16 (2017). https://github.com/coin-or/Clp
[51] Ralphs, T., Güzelsoy, M., Mahajan, A.: SYMPHONY version 5.6.16 (2017). doi:10.5281/zenodo.248734
[52] 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). doi:10.1007/0-387-23529-9_5. http://coral.ie.lehigh.edu/ ted/files/papers/SYMPHONY04.pdf
[53] Cgl version 0.59 (2017). https://github.com/coin-or/Cgl
[54] Osi version 0.107 (2017). https://github.com/coin-or/Osi
[55] 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
[56] 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 · Zbl 1160.90600
[57] Ibm ILOG CPLEX Optimizer. https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/ (2017)
[58] Forrest, J.J.: Cbc version 2.9 (2017). https://projects.coin-or.org/Cbc
[59] Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.: An updated mixed integer programming library: Miplib 3.0. Tech. rep. (1998)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.