×

zbMATH — the first resource for mathematics

A hybrid branch-and-bound approach for exact rational mixed-integer programming. (English) Zbl 1305.90310
Summary: We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver Qsopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the Miplib and Mittelmann libraries and for a new collection of numerically difficult instances.

MSC:
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.: ALU instances. http://miplib.zib.de/miplib2003/contrib/ALU
[2] Achterberg, T.: Constraint Integer Programming. Ph.D. thesis, Technische Universität Berlin (2007) · Zbl 1169.90414
[3] Achterberg, T.: SCIP: Solving constraint integer programs. Math. Program. Comput. 1(1), 1–41 (2009) · Zbl 1171.90476
[4] Achterberg, T., Koch, T., Martin, A.: The mixed integer programming library: MIPLIB (2003). http://miplib.zib.de
[5] Althaus, E., Dumitriu, D.: Fast and accurate bounds on linear programs. In: Vahrenhold, J. (ed.) SEA 2009. LNCS, vol. 5526, pp. 40–50. Springer, Berlin (2009)
[6] Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2006) · Zbl 1130.90036
[7] Applegate, D.L., Cook, W.J., Dash, S., Espinoza, D.G.: $$\(\backslash\)text{ QSopt }\(\backslash\)_\(\backslash\)text{ ex }.$$ QSopt _ ex . http://www.dii.uchile.cl/daespino/ESolver_doc/main.html
[8] Applegate, D.L., Cook, W.J., Dash, S., Espinoza, D.G.: Exact solutions to linear programming problems. Oper. Res. Lett. 35(6), 693–699 (2007) · Zbl 1177.90282
[9] AT &T Bell Laboratories, The University of Tennessee Knoxville, and Oak Ridge National Laboratory. Netlib Repository. http://www.netlib.org/netlib/lp
[10] Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.: An updated mixed integer programming library: MIPLIB 3.0. Optima 58, 12–15 (1998)
[11] Bley, A., Koch, T.: Optimierung des G-WiN. DFN-Mitteilungen 54, 13–15 (2000)
[12] Chai, J., Toh, K.: Computation of condition numbers for linear programming problems using Peña’s method. Optim. Methods Softw. 21(3), 419–443 (2006) · Zbl 1136.90540
[13] Cheung, D., Cucker, F.: A new condition number for linear programming. Math. Program. 91, 163–174 (2001) · Zbl 1072.90564
[14] Cheung, D., Cucker, F.: Solving linear programs with finite precision: I. Condition numbers and random programs. Math. Program. 99, 175–196 (2004) · Zbl 1082.90060
[15] Cheung, D., Cucker, F.: Solving linear programs with finite precision: II. Algorithms. J. Complex. 22(3), 305–335 (2006) · Zbl 1105.90042
[16] Cheung, D., Cucker, F., Peña, J.: Unifying condition numbers for linear programming. Math. Oper. Res. 28(4), 609–624 (2003) · Zbl 1082.90061
[17] Cook, W.J., Dash, S., Fukasawa, R., Goycoolea, M.: Numerically safe Gomory mixed-integer cuts. INFORMS J. Comput. 21(4), 641–649 (2009) · Zbl 1243.90135
[18] Czyzyk, J., Mesnier, M.P., Moré, J.J.: The Network-Enabled Optimization System (NEOS) server. IEEE J. Comput. Sci. Eng. 5(3), 68–75 (1998) · Zbl 05092192
[19] de Vries, S., Vohra, R.: Combinatorial auctions: a survey. INFORMS J. Comput. 15(3), 284–309 (2003) · Zbl 1238.91003
[20] Dhiflaoui, M., Funke, S., Kwappik, C., Mehlhorn, K., Seel, M., Schömer, E., Schulte, R., Weber, D.: Certifying and repairing solutions to large LPs, how good are LP-solvers? In: SODA 2003, pp. 255–256. ACM/SIAM, New York (2003) · Zbl 1176.90395
[21] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2001) · Zbl 1049.90004
[22] Espinoza, D.G.: On Linear Programming, Integer Programming and Cutting Planes. Ph.D. thesis, Georgia Institute of Technology (2006)
[23] Gay, D.M.: Electronic mail distribution of linear programming test problems. Math. Program. Soc. COAL Newsl. 13, 10–12 (1985)
[24] GMP. GNU multiple precision arithmetic library. http://gmplib.org
[25] Goldberg, D.: What every computer scientist should know about floating-point arithmetic. ACM Comput. Surv. (CSUR) 23(1), 5–48 (1991)
[26] IBM, ILOG. CPLEX. http://www.ilog.com/products/cplex
[27] Koch, T.: The final NETLIB-LP results. Oper. Res. Lett. 32(2), 138–142 (2004) · Zbl 1137.90613
[28] Koch, T.: Rapid Mathematical Programming. Ph.D. thesis, Technische Universität Berlin (2004)
[29] Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Math. Program. Comput. 3(2), 103–163 (2011) · Zbl 06110465
[30] Kwappik, C.: Exact Linear Programming. Universität des Saarlandes, Master thesis (1998)
[31] Lehigh University. COR@L mixed integer programming collection. http://coral.ie.lehigh.edu/data-sets/mixed-integer-instances
[32] Linderoth, J.T., Ralphs, T.K.: Noncommercial software for mixed-integer linear programming. In: Karlof, J. (ed.) Integer programming: theory and practice, pp. 253–303. CRC Press, Boca Raton (2005) · Zbl 1137.90622
[33] Mittelmann, H.D.: Benchmarks for Optimization Software (2010). http://plato.asu.edu/bench.html
[34] NEOS Server. http://neos-server.org/neos
[35] Neumaier, A., Shcherbina, O.: Safe bounds in linear and mixed-integer linear programming. Math. Program. 99(2), 283–296 (2004) · Zbl 1098.90043
[36] Nunez, M., Freund, R.M.: Condition measures and properties of the central trajectory of a linear program. Math. Program. 83, 1–28 (1998) · Zbl 0920.90097
[37] Ordónez, F., Freund, R.M.: Computational experience and the explanatory value of condition measures for linear optimization. SIAM J. Optim. 14(2), 307–333 (2003) · Zbl 1046.90001
[38] Pseudo-Boolean Competition (2010). http://www.cril.univ-artois.fr/PB10/
[39] Renegar, J.: Some perturbation theory for linear programming. Math. Program. 65, 73–91 (1994) · Zbl 0818.90073
[40] Renegar, J.: Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. 5, 506–524 (1995) · Zbl 0838.90139
[41] Renegar, J.: Linear programming, complexity theory and elementary functional analysis. Math. Program. 70, 279–351 (1995) · Zbl 0855.90085
[42] Steffy, D.E.: Topics in Exact Precision Mathematical Programming. Ph.D. thesis, Georgia Institute of Technology (2011)
[43] Steffy, D.E., Wolter, K.: Valid linear programming bounds for exact mixed-integer programming. Technical Report ZR 11–08, Zuse Institute Berlin. INFORMS J. Comput. (2011, to appear) · Zbl 1339.90244
[44] Vera, J.R.: On the complexity of linear programming under finite precision arithmetic. Math. Program. 80, 91–123 (1998) · Zbl 0894.90112
[45] Wilken, K., Liu, J., Heffernan, M.: Optimal instruction scheduling using integer programming. In: ACM SIGPLAN 2000, vol. 35, pp. 121–133. ACM Press, New York (2000)
[46] Zuse Institute Berlin. SCIP. http://scip.zib.de
[47] Zuse Institute Berlin. SoPlex. http://soplex.zib.de
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.