×

A computational status update for exact rational mixed integer programming. (English) Zbl 1482.90125

Singh, Mohit (ed.) et al., Integer programming and combinatorial optimization. 22nd international conference, IPCO 2021, Atlanta, GA, USA, May 19–21, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12707, 163-177 (2021).
Summary: The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by W. Cook et al. [Math. Program. Comput. 5, No. 3, 305–344 (2013; Zbl 1305.90310)]. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal floating-point heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 6.6x over the original framework and 2.8 times as many instances solved within a time limit of two hours.
For the entire collection see [Zbl 1476.90004].

MSC:

90C11 Mixed integer programming

Citations:

Zbl 1305.90310
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Achterberg, T.: Constraint integer programming. Ph.D. thesis, Technische Universität Berlin (2007) · Zbl 1430.90427
[2] Achterberg, T.; Bixby, RE; Gu, Z.; Rothberg, E.; Weninger, D., Presolve reductions in mixed integer programming, INFORMS J. Comput., 32, 2, 473-506 (2020) · Zbl 07290858
[3] Achterberg, T.; Koch, T.; Martin, A., Branching rules revisited, Oper. Res. Lett., 33, 1, 42-54 (2005) · Zbl 1076.90037
[4] Achterberg, T.; Wunderling, R.; Jünger, M.; Reinelt, G., Mixed integer programming: analyzing 12 years of progress, Facets of Combinatorial Optimization, 449-481 (2013), Heidelberg: Springer, Heidelberg · Zbl 1317.90206
[5] Applegate, D., Bixby, R., Chvatal, V., Cook, W.: Concorde TSP Solver (2006)
[6] Applegate, D.; Cook, W.; Dash, S.; Espinoza, DG, Exact solutions to linear programming problems, Oper. Res. Lett., 35, 6, 693-699 (2007) · Zbl 1177.90282
[7] Assarf, B., Computing convex hulls and counting integer points with polymake, Math. Program. Comput., 9, 1, 1-38 (2017) · Zbl 1370.90009
[8] Bagnara, R.; Hill, PM; Zaffanella, E., The Parma Polyhedra Library: toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems, Sci. Comput. Program., 72, 1-2, 3-21 (2008)
[9] Berthold, T., Measuring the impact of primal heuristics, Oper. Res. Lett., 41, 6, 611-614 (2013) · Zbl 1287.90037
[10] Biere, A., Heule, M., van Maaren, H., Walsh, T.: Handbook of Satisfiability: Volume 185 Frontiers in Artificial Intelligence and Applications. IOS Press, Amsterdam (2009)
[11] Bofill, M.; Manyà, F.; Vidal, A.; Villaret, M., New complexity results for Łukasiewicz logic, Soft. Comput., 23, 2187-2197 (2019) · Zbl 1418.03114
[12] Burton, B.A., Ozlen, M.: Computing the crosscap number of a knot using integer programming and normal surfaces. ACM Trans. Math. Softw. 39(1) (2012). doi:10.1145/2382585.2382589 · Zbl 1295.57006
[13] Cheung, KKH; Gleixner, A.; Steffy, DE; Eisenbrand, F.; Koenemann, J., Verifying integer programming results, Integer Programming and Combinatorial Optimization, 148-160 (2017), Cham: Springer, Cham · Zbl 1418.90176
[14] Cheung, K., Gleixner, A., Steffy, D.: VIPR. Verifying Integer Programming Results. https://github.com/ambros-gleixner/VIPR. Accessed 11 Nov 2020 · Zbl 1418.90176
[15] Cook, W.; Dash, S.; Fukasawa, R.; Goycoolea, M., Numerically safe gomory mixed-integer cuts, INFORMS J. Comput., 21, 641-649 (2009) · Zbl 1243.90135
[16] Cook, W.; Koch, T.; Steffy, DE; Wolter, K., A hybrid branch-and-bound approach for exact rational mixed-integer programming, Math. Program. Comput., 5, 3, 305-344 (2013) · Zbl 1305.90310
[17] Eifler, L., Gleixner, A.: Exact SCIP - a development version. https://github.com/leoneifler/exact-SCIP. Accessed 11 Nov 2020
[18] Eifler, L., Gleixner, A., Pulaj, J.: A safe computational framework for integer programming applied to Chvátal’s conjecture (2020)
[19] Espinoza, D.G.: On linear programming, integer programming and cutting planes. Ph.D. thesis, Georgia Institute of Technology (2006)
[20] Faure, G.; Nieuwenhuis, R.; Oliveras, A.; Rodríguez-Carbonell, E.; Kleine Büning, H.; Zhao, X., SAT modulo the theory of linear arithmetic: exact, inexact and commercial solvers, Theory and Applications of Satisfiability Testing - SAT 2008, 77-90 (2008), Heidelberg: Springer, Heidelberg · Zbl 1138.68537
[21] Gamrath, G., et al.: The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin (2020)
[22] Gleixner, A., et al.: MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. Math. Program. Comput. 1-48 (2021). doi:10.1007/s12532-020-00194-3 · Zbl 1476.90191
[23] Gleixner, A.; Steffy, DE, Linear programming using limited-precision oracles, Math. Program., 183, 525-554 (2020) · Zbl 1450.90006
[24] Gleixner, A.; Steffy, DE; Wolter, K., Iterative refinement for linear programming, INFORMS J. Comput., 28, 3, 449-464 (2016) · Zbl 1348.90460
[25] Gottwald, L.: PaPILO - Parallel Presolve for Integer and Linear Optimization. https://github.com/lgottwald/PaPILO. Accessed 9 Sep 2020
[26] Granlund, T., Team, G.D.: GNU MP 6.0 Multiple Precision Arithmetic Library. Samurai Media Limited, London, GBR (2015)
[27] Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia (2002). doi:10.1137/1.9780898718027 · Zbl 1011.65010
[28] Kenter, F.; Skipper, D.; Kim, D.; Uma, RN; Zelikovsky, A., Integer-programming bounds on pebbling numbers of Cartesian-product graphs, Combinatorial Optimization and Applications, 681-695 (2018), Cham: Springer, Cham · Zbl 07116414
[29] Lancia, G.; Pippia, E.; Rinaldi, F.; Kononov, A.; Khachay, M.; Kalyagin, VA; Pardalos, P., Using integer programming to search for counterexamples: a case study, Mathematical Optimization Theory and Operations Research, 69-84 (2020), Cham: Springer, Cham · Zbl 1476.05101
[30] de Moura, L.; Bjørner, N.; Ramakrishnan, CR; Rehof, J., Z3: an efficient SMT solver, Tools and Algorithms for the Construction and Analysis of Systems, 337-340 (2008), Heidelberg: Springer, Heidelberg
[31] Neumaier, A.; Shcherbina, O., Safe bounds in linear and mixed-integer programming, Math. Program., 99, 283-296 (2002) · Zbl 1098.90043
[32] Pulaj, J., Cutting planes for families implying Frankl’s conjecture, Math. Comput., 89, 322, 829-857 (2020) · Zbl 1429.05199
[33] Steffy, DE; Wolter, K., Valid linear programming bounds for exact mixed-integer programming, INFORMS J. Comput., 25, 2, 271-284 (2013)
[34] Wetzler, N.; Heule, MJH; Hunt, WA; Sinz, C.; Egly, U., DRAT-trim: efficient checking and trimming using expressive clausal proofs, Theory and Applications of Satisfiability Testing - SAT 2014, 422-429 (2014), Cham: Springer, Cham · Zbl 1423.68475
[35] Wilken, K.; Liu, J.; Heffernan, M., Optimal instruction scheduling using integer programming, SIGPLAN Not., 35, 5, 121-133 (2000)
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.