MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. (English) Zbl 1476.90191
Summary: We report on the selection process leading to the sixth version of the Mixed Integer Programming Library, MIPLIB 2017. Selected from an initial pool of 5721 instances, the new MIPLIB 2017 collection consists of 1065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, these sets were compiled using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encode requirements on diversity and balancedness with respect to instance features and performance data.
MSC:
| 90C06 | Large-scale problems in mathematical programming |
| 90C09 | Boolean programming |
| 90C10 | Integer programming |
| 90C11 | Mixed integer programming |
Keywords:
mixed integer linear optimization; MIP; benchmarking; selection methodology; instance librarySoftware:
DIP; Mosek; Cbc; XPRESS; MIPLIB2003; MINLPLib; OR-Library; AMPL; DipPy; SAS/OR; AS 136; UG; Gurobi; MIPLIB; gmp; Benchmarks for Optimization Software; SCIP; t-SNE; IPET; ParaSCIP; ASlib; QPLIBReferences:
| [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. (2019) · Zbl 07290858 · doi:10.1287/ijoc.2018.0857 |
| [3] | Achterberg, T.; Koch, T.; Martin, A., MIPLIB 2003, Oper. Res. Lett., 34, 4, 361-372 (2006) · Zbl 1133.90300 · doi:10.1016/j.orl.2005.07.009 |
| [4] | Beasley, JE, OR-Library: distributing test problems by electronic mail, J. Oper. Res. Soc., 41, 11, 1069-1072 (1990) · doi:10.1057/jors.1990.166 |
| [5] | Beyer, K., Goldstein, J., Ramakrishnan, R., Shaft, U.: When is “nearest neighbor” meaningful? In: C. Beeri, P. Buneman (eds.) Database Theory-ICDT’99, pp. 217-235. Springer, Berlin (1999). doi:10.1007/3-540-49257-7_15 |
| [6] | Bischl, B.; Kerschke, P.; Kotthoff, L.; Lindauer, M.; Malitsky, Y.; Fréchette, A.; Hoos, H.; Hutter, F.; Leyton-Brown, K.; Tierney, K., ASlib: a benchmark library for algorithm selection, Artif. Intell., 237, 41-58 (2016) · Zbl 1357.68202 · doi:10.1016/j.artint.2016.04.003 |
| [7] | Bixby, RE, Solving real-world linear programs: a decade and more of progress, Oper. Res., 50, 1, 3-15 (2002) · Zbl 1163.90643 · doi:10.1287/opre.50.1.3.17780 |
| [8] | Bixby, RE; Boyd, EA; Indovina, RR, MIPLIB: a test set of mixed integer programming problems, SIAM News, 25, 16 (1992) |
| [9] | Bixby, RE; Ceria, S.; McZeal, C.; Savelsbergh, M., An updated mixed integer programming library: MIPLIB 3.0, Optima, 58, 12-15 (1998) |
| [10] | Browne, S., Dongarra, J., Grosse, E., Rowan, T.: The Netlib mathematical software repository. D-lib Magazine 1(9), (1995) |
| [11] | Bussieck, MR; Drud, AS; Meeraus, A., MINLPLib—a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 1, 114-119 (2003) · Zbl 1238.90104 · doi:10.1287/ijoc.15.1.114.15159 |
| [12] | COIN-OR branch-and-cut MIP solver (2019). https://github.com/coin-or/Cbc |
| [13] | IBM ILOG CPLEX Optimizer (2019). http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/ |
| [14] | Crowder, HP; Dembo, RS; Mulvey, JM, Reporting computational experiments in mathematical programming, Math. Program., 15, 316-329 (1978) · Zbl 0389.65031 · doi:10.1007/BF01609036 |
| [15] | Fourer, RM; Gay, DW; Kernighan, B., AMPL: A Modeling Language for Mathematical Programming (2002), California: Duxbury Press, California · Zbl 0701.90062 |
| [16] | Furini, F.; Traversi, E.; Belotti, P.; Frangioni, A.; Gleixner, A.; Gould, N.; Liberti, L.; Lodi, A.; Misener, R.; Mittelmann, H., QPLIB: a library of quadratic programming instances, Math. Program. Comput., 11, 2, 237-265 (2019) · Zbl 1435.90099 · doi:10.1007/s12532-018-0147-4 |
| [17] | Galati, M., Ralphs, T., Wang, J.: Computational Experience with Generic Decomposition using the DIP Framework. In: Proceedings of RAMP 2012 (2012). http://coral.ie.lehigh.edu/ ted/files/papers/RAMP12.pdf |
| [18] | Galati, M., Ralphs, T., Wang, J.: DIP/DipPy version 0.92 (2019). doi:10.5281/zenodo.2656800. http://github.com/coin-or/Dip |
| [19] | Galati, M.V.: Decomposition in Integer Programming. Phd, Lehigh University (2009). http://coral.ie.lehigh.edu/ ted/files/papers/MatthewGalatiDissertation09.pdf |
| [20] | Gamrath, G.; Koch, T.; Martin, A.; Miltenberger, M.; Weninger, D., Progress in presolving for mixed integer programming, Math. Program. Comput. (2015) · Zbl 1329.90089 · doi:10.1007/s12532-015-0083-5 |
| [21] | Gamrath, G., Lübbecke, M.: Experiments with a generic Dantzig-Wolfe decomposition for integer programs. In: P. Festa (ed.) Experimental Algorithms, Lect. Notes in Comp. Sci., vol. 6049, pp. 239-252. Springer, Berlin (2010). doi:10.1007/978-3-642-13193-6_21 |
| [22] | Georges, A., Gleixner, A., Gojic, G., Gottwald, R.L., Haley, D., Hendel, G., Matejczyk, B.: Feature-based algorithm selection for mixed integer programming. ZIB-Report 18-17, Zuse Institute Berlin (2018) |
| [23] | Gleixner, A., Bastubbe, M., Eifler, L., Gally, T., Gamrath, G., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Lübbecke, M.E., Maher, S.J., Miltenberger, M., Müller, B., Pfetsch, M.E., 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. ZIB-Report 18-26. Zuse Institute, Berlin (2018) |
| [24] | Granlund, T., the GMP development team: GNU MP: The GNU Multiple Precision Arithmetic Library, 6.1.2 edn (2016). http://gmplib.org/ |
| [25] | GUROBI Optimizer (2019). http://www.gurobi.com/products/gurobi-optimizer/gurobi-overview |
| [26] | Hartigan, JA; Wong, MA, Algorithm AS 136: A K-Means clustering algorithm, Appl. Stat., 28, 1, 100-108 (1979) · Zbl 0447.62062 · doi:10.2307/2346830 |
| [27] | Hendel, G.: IPET interactive performance evaluation tools. https://github.com/GregorCH/ipet |
| [28] | Hoffman, A.; Mannos, M.; Sokolowsky, D.; Wiegmann, N., Computational experience in solving linear programs, J. Soc. Ind. Appl. Math., 1, 1, 17-33 (1953) · Zbl 0053.41805 · doi:10.1137/0101002 |
| [29] | Hooker, J., Needed: an empirical science of algorithms, Oper. Res., 42, 2, 210-212 (1993) · Zbl 0805.90119 |
| [30] | IBM Corporation, White Plains, N.Y.: Mathematical Programming System/360 Version 2, Linear and Separable Programming—User’s Manual, 3 edn. (1969). Publication H20-0476-2 |
| [31] | Jackson, RHF; Boggs, PT; Nash, SG; Powell, S., Guidelines for reporting results of computational experiments. Report of the ad hoc committee, Math. Program., 49, 413-425 (1991) · doi:10.1007/BF01588801 |
| [32] | Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, RE; Danna, E.; Gamrath, G.; Gleixner, AM; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Steffy, DE; Wolter, K., MIPLIB 2010, Math. Program. Comput., 3, 103-163 (2011) · doi:10.1007/s12532-011-0025-9 |
| [33] | Laundy, R.; Perregaard, M.; Tavares, G.; Tipi, H.; Vazacopoulos, A., Solving hard mixed integer programming problems with Xpress-MP: A MIPLIB 2003 case study, INFORMS J. Comput., 21, 304-319 (2009) · Zbl 1243.90149 · doi:10.1287/ijoc.1080.0293 |
| [34] | Linderoth, JT; Ralphs, TK, Noncommercial software for mixed-integer linear programming, Integ. Program. Theory Pract., 3, 253-303, 144-189 (2005) · Zbl 1137.90622 |
| [35] | Lodi, A.; Jünger, M.; Liebling, T.; Naddef, D.; Nemhauser, G.; Pulleyblank, W.; Reinelt, G.; Rinaldi, G.; Wolsey, L., MIP computation, 50 Years of Integer Programming 1958-2008, 619-645 (2009), Berlin: Springer, Berlin |
| [36] | MathWorks: MATLAB Optimization Toolbox (2019). https://de.mathworks.com/products/optimization.html |
| [37] | McGeoch, CC, Toward an experimental method for algorithm simulation, INFORMS J. Comput., 8, 1, 1-15 (1996) · Zbl 0854.68038 · doi:10.1287/ijoc.8.1.1 |
| [38] | McGeoch, CC, Experimental analysis of algorithms, Notices AMS, 48, 3, 304-311 (2001) · Zbl 0981.68187 |
| [39] | MIPLIB 2.0. http://miplib2010.zib.de/miplib2/miplib2.html |
| [40] | Mittelmann, H.: Benchmarks for optimization software. http://plato.asu.edu/bench.html |
| [41] | MOSEK (2019). https://www.mosek.com/ |
| [42] | Nazareth, JL, Computer Solutions of Linear Programs. Monographs on Numerical Analysis (1987), Oxford: Oxford University Press, Oxford · Zbl 0643.90042 |
| [43] | Rice, J.R.: The algorithm selection problem. In: Advances in computers, vol. 15, pp. 65-118. Elsevier (1976) |
| [44] | SAS: SAS/OR (2019). https://www.sas.com/en_us/software/or.html |
| [45] | Solving Constraint Integer Programs (2019). http://scip.zib.de/ |
| [46] | Shinano, Y.: The Ubiquity Generator framework: 7 years of progress in parallelizing branch-and-bound. In: N. Kliewer, J.F. Ehmke, R. Borndörfer (eds.) Operations Research Proceedings 2017, pp. 143-149. Springer International Publishing, Cham (2018). doi:10.1007/978-3-319-89920-6_20 · Zbl 1397.90405 |
| [47] | Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T., Winkler, M.: Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores. In: Proceedings of the 30th IEEE International Parallel & Distributed Processing Symposium (2016). doi:10.1109/IPDPS.2016.56 |
| [48] | Smith-Miles, K.; Baatar, D.; Wreford, B.; Lewis, R., Towards objective measures of algorithm performance across instance space, Comput. Oper. Res., 45, 12-24 (2014) · Zbl 1348.90646 · doi:10.1016/j.cor.2013.11.015 |
| [49] | Smith-Miles, K.; Bowly, S., Generating new test instances by evolving in instance space, Comput. Oper. Res., 63, 102-113 (2015) · Zbl 1349.68325 · doi:10.1016/j.cor.2015.04.022 |
| [50] | van der Maaten, L.; Hinton, G., Visualizing high-dimensional data using t-SNE, J. Mach. Learn. Res., 9, 2579-2605 (2008) · Zbl 1225.68219 |
| [51] | Xpress: FICO Xpress-Optimizer (2019). http://www.fico.com/en/Products/DMTools/xpress-overview/Pages/Xpress-Optimizer.aspx |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
