MILP Acceleration: A Survey from Perspectives of Simplex Initialization and Learning-Based Branch and Bound

doi:10.1007/s40305-023-00493-1

Abstract

Abstract: Mixed integer linear programming (MILP) is an NP-hard problem, which can be solved by the branch and bound algorithm by dividing the original problem into several subproblems andforming a search tree. For each subproblem, linear programming(LP) relaxation can be solved to find the boundformaking thefollowing decisions. Recently, with the increasing dimension of MILPs in different applications, how to accelerate the solution process becomes a huge challenge. In this survey, we summarize techniques and trends to speed up MILP solving from two perspectives. First, we present different approaches in simplex initialization, which can help to accelerate the solution of LP relaxation for each subproblem. Second, we introduce the learning-based technologies in branch and bound algorithms to improve decision making in tree search. We also propose several potential directions and extensions to further enhance the efficiency of solving different MILP problems.

Key words: MILP acceleration, Simplex initialization, Linear programming, Mixed integer linear programming, Machine learning

CLC Number:

90C11

Meng-Yu Huang, Ling-Ying Huang, Yu-Xing Zhong, Hui-Wen Yang, Xiao-Meng Chen, Wei Huo, Jia-Zheng Wang, Fan Zhang, Bo Bai, Ling Shi. MILP Acceleration: A Survey from Perspectives of Simplex Initialization and Learning-Based Branch and Bound[J]. Journal of the Operations Research Society of China, 2025, 13(1): 1-55.

TrendMD

References

[1] CPLEX:http://www.ilog.com/products/cplex
[2] LINDO:http://www.lindo.com
[3] Achterberg, T.:SCIP:solving constraint integer programs. Math. Program. Comput. 1, 1-41(2009)
[4] Land, A.H., Doig, A.G.:An automatic method for solving discrete programming problems. In: Econometrica vol. 28, pp. 497-520(1960)
[5] Kantorovich, L.V.:The mathematical method of production planning and organization. Manag. Sci. 6(4), 363-422(1939)
[6] Dantzig, G.B.:Maximization of a linear function of variables subject to linear inequalities. Act. Anal. Prod. Alloc. 13, 339-347(1951)
[7] Karmarkar, N.:A new polynomial-time algorithm for linear programming. In:Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pp. 302-311(1984)
[8] Dantzig, G.B.:Linear Programming and Extensions, vol. 48. Princeton University Press, Princeton (1965)
[9] 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)
[10] Murshed, M.M., Sarward, B.M., Sattar, M.A., Kaykobad, M.:A New Polynomial Algorithm for Linear Programming Problem. NEC Research Institute (1993)
[11] Stojković, N.V., Stanimirović, P.S.:Two direct methods in linear programming. Eur. J. Oper. Res. 131(2), 417-439(2001)
[12] Junior, H.V., Lins, M.P.E.:An improved initial basis for the simplex algorithm. Comput. Oper. Res. 32(8), 1983-1993(2005)
[13] Hu, J.:A note on an improved initial basis for the simplex algorithm. Comput. Oper. Res. 34(11), 3397-3401(2007)
[14] Bergström, P.:Plot 2D/3D region. https://www.mathworks.com/matlabcentral/fileexchange/9261- plot-2d-3d-region. MATLAB Central File Exchange. Accessed 26 July 2021(2021)
[15] Pan, P.:A variant of the dual pivoting rule in linear programming. J. Inf. Optim. Sci. 15(3), 405-413(1994)
[16] Wolfe, P.:The composite simplex algorithm. SIAM Rev. 7(1), 42-54(1965)
[17] Guerrero-Garcia, P., Santos-Palomo, A.:Phase I cycling under the most-obtuse-angle pivot rule. Eur. J. Oper. Res. 167(1), 20-27(2005)
[18] Galabova, I., Hall, J.:The idiot crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems. Optim. Methods Softw. 35(3), 488- 501(2020)
[19] Luh, H., Tsaih, R.:An efficient search direction for linear programming problems. Comput. Oper. Res. 29(2), 195-203(2002)
[20] Chaderjian, B.J., Gao, T.:Comments on an efficient search direction for linear programming problems by H. Luh and R. Tsaih. Comput. Oper. Res. 30(8), 1255-1258(2003)
[21] Al-Najjar, C., Malakooti, B.:Hybrid-LP:finding advanced starting points for simplex, and pivoting LP methods. Comput. Oper. Res. 38(2), 427-434(2011)
[22] Maros, I.:Computational Techniques of the Simplex Method, vol. 61. Springer, Berlin (2012)
[23] Maros, I., Mitra, G.:Strategies for creating advanced bases for large-scale linear programming problems. INFORMS J. Comput. 10(2), 248-260(1998)
[24] Ploskas, N., Sahinidis, N.V., Samaras, N.:A triangulation and fill-reducing initialization procedure for the simplex algorithm. Math. Program. Comput. 66, 1-18(2020)
[25] Bixby, R.E.:Implementing the simplex method:the initial basis. ORSA J. Comput. 4(3), 267-284(1992)
[26] Vaidya, N., Kasturiwale, N.:Quick simplex algorithm for optimal solution to the linear programming problem along with theoretical proof of formulae. Int. J. Latest Trend Math. 4(2), 183-200(2014)
[27] Chvatal, V., Chvatal, V., et al.:Linear Programming. Macmillan, New York (1983)
[28] Bertsimas, D., Tsitsiklis, J.N.:Introduction to Linear Optimization, vol. 6. Athena Scientific, Belmont (1997)
[29] Nabli, H., Chahdoura, S.:Algebraic simplex initialization combined with the nonfeasible basis method. Eur. J. Oper. Res. 245(2), 384-391(2015)
[30] Nabli, H.:An overview on the simplex algorithm. Appl. Math. Comput. 210(2), 479-489(2009)
[31] Wunderling, R.:Paralleler und objektorientierter simplex. PhD thesis, Konrad-Zuse-Zentrum für Informationstechnik Berlin (1996)
[32] Pan, P.:Primal perturbation simplex algorithms for linear programming. J. Comput. Math. 66, 587- 596(2000)
[33] Gould, N.I., Reid, J.K.:New crash procedures for large systems of linear constraints. Math. Program. 45(1), 475-501(1989)
[34] Erisman, A., Grimes, R., Lewis, J., Poole, W., Jr.:A structurally stable modification of Hellerman- Rarick's P4 algorithm for reordering unsymmetric sparse matrices. SIAM J. Numer. Anal. 22(2), 369-385(1985)
[35] Zionts, S.:The Criss-Cross method for solving linear programming problems. Manag. Sci. 15(7), 426-445(1969)
[36] Pan, P.:Linear Programming Computation. Springer, Berlin (2014)
[37] Ge, D., Wang, C., Xiong, Z., Ye, Y.:From an interior point to a corner point:smart crossover. arXiv:2102.09420(2021)
[38] Pan, P.:Practical finite pivoting rules for the simplex method. Oper. Res. Spektr. 12(4), 219-225(1990)
[39] Pan, P.:Ratio-test-free pivoting rules for a dual phase-1 method. In:Proceeding of the Third Conference of Chinese SIAM, pp. 245-249. Tsinghua University Press, Beijing (1994)
[40] Pan, P.:The most-obtuse-angle row pivot rule for achieving dual feasibility:a computational study. Eur. J. Oper. Res. 101(1), 164-176(1997)
[41] Koberstein, A., Suhl, U.H.:Progress in the dual simplexmethod for large scale LP problems:practical dual phase 1 algorithms. Comput. Optim. Appl. 37(1), 49-65(2007)
[42] Pan, P.:A new perturbation simplex algorithm for linear programming. J. Comput. Math. 66, 233-242(1999)
[43] Maros, I.:A general phase-1 method in linear programming. Eur. J. Oper. Res. 23(1), 64-77(1986)
[44] Maros, I.:A piecewise linear dual phase-1 algorithm for the simplex method. Comput. Optim. Appl. 26(1), 63-81(2003)
[45] Wunderling, R.:Paralleler und objektorientierter simplex. PhD thesis, Technische Universität, Berlin (1996)
[46] Achterberg, T., Koch, T., Martin, A.:Branching rules revisited. Oper. Res. Lett. 33(1), 42-54(2005)
[47] Alvarez, A.M., Louveaux, Q., Wehenkel, L.:A supervised machine learning approach to variable branching in branch-and-bound. In:Ecml. Citeseer (2014)
[48] Alvarez, A.M., Louveaux, Q., Wehenkel, L.:A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1), 185-195(2017)
[49] Marcos Alvarez, A., Wehenkel, L., Louveaux, Q.:Online Learning for Strong Branching Approximation in Branch-and-Bound (2016)
[50] Geurts, P., Ernst, D., Wehenkel, L.:Extremely randomized trees. Mach. Learn. 63(1), 3-42(2006)
[51] Khalil, E., Le Bodic, P., Song, L., Nemhauser, G., Dilkina, B.:Learning to branch in mixed integer programming. In:Proceedings of the AAAI Conference on Artificial Intelligence, pp. 724-731, AAAI Press (2016)
[52] Falk, P.G.:Experiments in mixed integer linear programming in a manufacturing system. Omega 8(4), 473-484(1980)
[53] Balcan, M.-F., Dick, T., Sandholm, T., Vitercik, E.:Learning to branch. In:Proceedings of the 35th International Conference on Machine Learning, pp. 344-353. PMLR (2018)
[54] Gasse, M., Chételat, D., Ferroni, N., Charlin, L., Lodi, A.:Exact combinatorial optimization with graph convolutional neural networks. arXiv:1906.01629(2019)
[55] Gupta, P., Gasse, M., Khalil, E.B., Kumar, M.P., Lodi, A., Bengio, Y.:Hybrid models for learning to branch. arXiv:2006.15212(2020)
[56] Nair, V., Bartunov, S., Gimeno, F., von Glehn, I., Lichocki, P., Lobov, I., O'Donoghue, B., Sonnerat, N., Tjandraatmadja, C., Wang, P., et al.:Solving mixed integer programs using neural networks. arXiv:2012.13349(2020)
[57] Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.-K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., et al.:The scip optimization suite 7.0(2020) https://optimization-online.org/?p=16345
[58] Zarpellon, G., Jo, J., Lodi, A., Bengio, Y.:Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies (2020)
[59] Gleixner, A., Bastubbe, M., Eifler, L., Gally, T., Gamrath, G., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Lübbecke, M., Maher, S.J., Miltenberger, M., Müller, B., Pfetsch, M., Puchert, C., Rehfeldt, D., Schlösser, F., Schubert, C., Serrano, F., Shinano, Y., Viernickel, J.M., Walter, M., Wegscheider, F., Witt, J.T., Witzig, J.:The scip optimization suite 6.0. Technical Report 18-26, ZIB, Takustr. 7, 14195, Berlin (2018)
[60] Hansknecht, C., Joormann, I., Stiller, S.:Cuts, primal heuristics, and learning to branch for the time-dependent traveling salesman problem. arXiv:1805.01415(2018)
[61] Sun, H., Chen, W., Li, H., Song, L.:Improving learning to branch via reinforcement learning. In: Learning Meets Combinatorial Algorithms at NeurIPS2020(2020). https://openreview.net/forum?id=z4D7-PTxTb
[62] Achterberg, T., Berthold, T.:Hybrid branching. In:International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 309-311. Springer (2009)
[63] Etheve, M., Alès, Z., Bissuel, C., Juan, O., Kedad-Sidhoum, S.:Reinforcement learning for variable selection in a branch and bound algorithm. In:Hebrard, E., Musliu, N.(eds.) Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 176-185. Springer, Cham (2020)
[64] Di Liberto, G., Kadioglu, S., Leo, K., Malitsky, Y.:Dash:dynamic approach for switching heuristics. Eur. J. Oper. Res. 248(3), 943-953(2016)
[65] Kadioglu, S., Malitsky, Y., Sellmann, M.:Non-model-based search guidance for set partitioning problems. In:Proceedings of the AAAI Conference on Artificial Intelligence, vol. 26, pp. 493-498(2012)
[66] Lodi, A., Zarpellon, G.:On learning and branching:a survey. Top 25(2), 207-236(2017)
[67] Linderoth, J.T., Savelsbergh, M.W.:A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11(2), 173-187(1999)
[68] Sabharwal, A., Samulowitz, H., Reddy, C.:Guiding combinatorial optimization with uct. In:International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pp. 356-361. Springer (2012)
[69] Glover, F.:Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533-549(1986)
[70] Glover, F., Greenberg, H.J.:New approaches for heuristic search:a bilateral linkage with artificial intelligence. Eur. J. Oper. Res. 39(2), 119-130(1989)
[71] Ansótegui, C., Pon, J., Sellmann, M., Tierney, K.:Reactive dialectic search portfolios for maxsat. In:Proceedings of the AAAI Conference on Artificial Intelligence, vol. 31, pp. 765-772(2017)
[72] Ansótegui, C., Malitsky, Y., Samulowitz, H., Sellmann, M., Tierney, K.:Model-based genetic algorithms for algorithm configuration. In:Proceedings of the 24th International Conference on Artificial Intelligence, pp. 733-739(2015)
[73] Daumé, H., Langford, J., Marcu, D.:Search-based structured prediction. Mach. Learn. 75(3), 297- 325(2009)
[74] Chang, K.-W., Krishnamurthy, A., Agarwal, A., Daume, H., Langford, J.:Learning to search better than your teacher. In:International Conference on Machine Learning, pp. 2058-2066. PMLR (2015)
[75] He, H., Daume, H., III., Eisner, J.M.:Learning to search in branch and bound algorithms. Adv. Neural Inf. Process. Syst. 27, 3293-3301(2014)
[76] Yilmaz, K., Yorke-Smith, N.:A study of learning search approximation in mixed integer branch and bound:node selection in scip. AI 2(2), 150-178(2021)
[77] Hottung, A., Tanaka, S., Tierney, K.:Deep learning assisted heuristic tree search for the container pre-marshalling problem. Comput. Oper. Res. 113, 104781(2020)
[78] Karapetyan, D., Punnen, A.P., Parkes, A.J.:Markov chainmethods for the bipartite Boolean quadratic programming problem. Eur. J. Oper. Res. 260(2), 494-506(2017)
[79] Khalil, E.B., Dilkina, B., Nemhauser, G.L., Ahmed, S., Shao, Y.:Learning to run heuristics in tree search. In:Twenty-Sixth International Joint Conference on Artificial Intelligence, pp. 659-666(2017)
[80] Hendel, G.:Adaptive Large Neighborhood Search for Mixed Integer Programming. Math. Prog. Comp. 14, 185-221(2022)
[81] Hottung, A., Tierney, K.:Neural large neighborhood search for the capacitated vehicle routing problem. arXiv:1911.09539(2019)
[82] Addanki, R., Nair, V., Alizadeh, M.:Neural large neighborhood search. In:Learning Meets Combinatorial Algorithms NeurIPS Workshop (2020)
[83] Song, J., Lanka, R., Yue, Y., Dilkina, B.:A general large neighborhood search framework for solving integer programs. arXiv:2004.00422(2020)
[84] Xavier, Á.S., Qiu, F., Ahmed, S.:Learning to solve large-scale security-constrained unit commitment problems. INFORMS J. Comput. 6, 66(2020)
[85] Ding, J., Zhang, C., Shen, L., Li, S., Wang, B., Xu, Y., Song, L.:Accelerating primal solution findings for mixed integer programs based on solution prediction. In:Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 1452-1459(2020)
[86] Han, S., Mao, H., Dally, W.J.:Deep compression:compressing deep neural networks with pruning, trained quantization and Huffman coding. arXiv:1510.00149(2015)
[87] Shen, Y., Shi, Y., Zhang, J., Letaief, K.B.:Lorm:learning to optimize for resource management in wireless networks with few training samples. IEEE Trans. Wirel. Commun. 19(1), 665-679(2019)
[88] Lee, M., Yu, G., Li, G.Y.:Learning to branch:accelerating resource allocation in wireless networks. IEEE Trans. Veh. Technol. 69(1), 958-970(2019)
[89] Aglin, G., Nijssen, S., Schaus, P.:Learning optimal decision trees using caching branch-and-bound search. In:Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 3146-3153(2020)
[90] Binney, J., Sukhatme, G.S.:Branch and bound for informative path planning. In:2012 IEEE International Conference on Robotics and Automation, pp. 2147-2154. IEEE (2012)
[91] Dey, S.S., Molinaro, M.:Theoretical challenges towards cutting-plane selection. Math. Program. 170(1), 1-30(2018)
[92] Huang, Z., Wang, K., Liu, F., Zhen, H.-L., Zhang, W., Yuan, M., Hao, J., Yu, Y., Wang, J.:Learning to select cuts for efficient mixed-integer programming. Pattern Recognit. 123, 108353(2022)
[93] Babenko, B.:Multiple instance learning:algorithms and applications. View Article PubMed/NCBI Google Scholar, pp. 1-19(2008)
[94] Balcan, M.-F.F., Prasad, S., Sandholm, T., Vitercik, E.:Sample complexity of tree search configuration:cutting planes and beyond. Adv. Neural Inf. Process. Syst. 34, 4015-4027(2021)
[95] Paulus, M.B., Zarpellon, G., Krause, A., Charlin, L., Maddison, C.:Learning to cut by looking ahead: cutting plane selection via imitation learning. In:International Conference on Machine Learning, pp. 17584-17600. PMLR (2022)
[96] Tang, Y., Agrawal, S., Faenza, Y.:Reinforcement learning for integer programming:Learning to cut. In:Singh, A.H.D III (Eds.) Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 119, pp. 9367-9376. PMLR (2020)
[97] Turner, M., Koch, T., Serrano, F., Winkler, M.:Adaptive cut selection in mixed-integer linear programming. arXiv:2202.10962(2022)
[98] Anonymous:Learning cut selection for mixed-integer linear programming via hierarchical sequence model. In:Submitted to the Eleventh International Conference on Learning Representations (2023). https://openreview.net/forum?id=Zob4P9bRNcK
[99] Dey, S.S., Kazachkov, A.M., Lodi, A., Munoz, G.:Cutting plane generation through sparse principal component analysis (2021). http://www.optimization-online.org/DB_HTML/2021/02/8259.html
[100] Baltean-Lugojan, R., Bonami, P., Misener, R., Tramontani, A.:Selecting cutting planes for quadratic semidefinite outer-approximation via trained neural networks. Technical report, Technical Report, CPLEX Optimization, IBM (2018)
[101] Achterberg, T.:Constraint Integer Programming Verlag:Dr. Hut (2007)
[102] Wesselmann, F., Stuhl, U.:Implementing Cutting Plane Management and Selection Techniques (2012) https://optimization-online.org/?p=12261
[103] Dey, S.S., Molinaro, M.:Theoretical challenges towards cutting-plane selection. Math. Program. 170(1), 237-266(2018)
[104] Selsam, D., Lamm, M., Bünz, B., Liang, P., de Moura, L., Dill, D.L.:Learning a SAT solver from single-bit supervision. arXiv:1802.03685(2018)
[105] Ross, S., Gordon, G., Bagnell, D.:A reduction of imitation learning and structured prediction to no-regret online learning. In:Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 627-635. JMLR Workshop and Conference Proceedings (2011)