×

zbMATH — the first resource for mathematics

A computational study of primal heuristics inside an MI(NL)P solver. (English) Zbl 1394.90432
Summary: Primal heuristics are a fundamental component of state-of-the-art global solvers for mixed integer linear programming (MIP) and mixed integer nonlinear programming (MINLP). In this paper, we investigate the impact of primal heuristics on the overall solution process. We present a computational study, in which we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics on six test sets with altogether 983 instances from academic and industrial sources. We analyze how primal heuristics affect the solver regarding seven different measures of performance and show that the impact differs by orders of magnitude. We further argue that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes.
MSC:
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T, SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476
[2] Achterberg, T; Berthold, T, Improving the feasibility pump, Discrete Optim. Spec. Issue, 4, 77-86, (2007) · Zbl 1170.90443
[3] Achterberg, T; Berthold, T; Hendel, G; Klatte, D (ed.); Lüthi, HJ (ed.); Schmedders, K (ed.), Rounding and propagation heuristics for mixed integer programming, 71-76, (2012), Berlin · Zbl 1306.90100
[4] Achterberg, T., Berthold, T., Koch, T., Wolter, K.: Constraint integer programming: a new approach to integrate CP and MIP. In: Perron, L., Trick, M.A. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008, Lecture Notes in Computer Science, vol. 5015, pp. 6-20. Springer, Berlin (2008) · Zbl 1142.68504
[5] Achterberg, T; Koch, T; Martin, A, Miplib 2003, Oper. Res. Lett., 34, 1-12, (2006) · Zbl 1133.90300
[6] Achterberg, T; Wunderling, R; Jünger, M (ed.); Reinelt, G (ed.), Mixed integer programming: analyzing 12 years of progress, 449-481, (2013), Berlin · Zbl 1317.90206
[7] Arnold, T., Berthold, T., Heinz, S., Vigerske, S., Henrion, R., Grötschel, M., Koch, T., Tischendorf, C., Römisch, W.: A jack of all trades? solving stochastic mixed-integer nonlinear constraint programs. In: Deuflhard, P., Grötschel, M., Hömberg, D., Horst, U., Kramer, J., Mehrmann, V., Polthier, K., Schmidt, F., Schütte, C., Skutella, M., Sprekels, J. (eds.) Matheon—Mathematics for Key Technologies, EMS Series in Industrial and Applied Mathematics, vol. 1, pp. 135-146. European Mathematical Society (2014) · Zbl 1276.90041
[8] Belotti, P; Lee, J; Liberti, L; Margot, F; Wächter, A, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[9] Berthold, T.: Primal heuristics for mixed integer programs. Diploma Thesis, Technische Universität Berlin (2006) · Zbl 1287.90037
[10] Berthold, T, Measuring the impact of primal heuristics, Oper. Res. Lett., 41, 611-614, (2013) · Zbl 1287.90037
[11] Berthold, T.: Heuristic algorithms in global MINLP solvers. Ph.D. Thesis, Technische Universität Berlin (2014) · Zbl 1077.90039
[12] Berthold, T, RENS—the optimal rounding, Math. Program. Comput., 6, 33-54, (2014) · Zbl 1304.90147
[13] Berthold, T; Gleixner, AM, Undercover: a primal MINLP heuristic exploring a largest sub-MIP, Math. Program., 144, 315-346, (2014) · Zbl 1291.90144
[14] Berthold, T., Heinz, S., Pfetsch, M.E., Vigerske, S.: Large neighborhood search beyond MIP. In: Gaspero, L.D., Schaerf, A., Stützle, T. (eds.) Proceedings of the 9th Metaheuristics International Conference (MIC 2011), pp. 51-60 (2011) · Zbl 1180.90245
[15] Berthold, T; Heinz, S; Vigerske, S; Lee, J (ed.); Leyffer, S (ed.), Extending a CIP framework to solve miqcps, No. 154, 427-444, (2011), New York · Zbl 1242.90120
[16] Bixby, RE; Ceria, S; McZeal, CM; Savelsbergh, MW, An updated mixed integer programming library: MIPLIB 3.0, Optima, 58, 12-15, (1998)
[17] Bonami, P; Cornuéjols, G; Lodi, A; Margot, F, A feasibility pump for mixed integer nonlinear programs, Math. Program., 119, 331-352, (2009) · Zbl 1163.90013
[18] Bonami, P; Gonçalves, J, Heuristics for convex mixed integer nonlinear programs, Comput. Optim. Appl., 51, 729-747, (2012) · Zbl 1241.90189
[19] Bonami, P; Lee, J, Bonmin user’s manual, Numer. Math., 4, 1-32, (2007)
[20] Bussieck, MR; Drud, AS; Meeraus, A, Minlplib—a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 114-119, (2003) · Zbl 1238.90104
[21] CppAD: A package for differentiation of C++ algorithms. http://www.coin-or.org/CppAD/ · Zbl 1242.90120
[22] D’Ambrosio, C; Frangioni, A; Liberti, L; Lodi, A, A storm of feasibility pumps for nonconvex MINLP, Math. Program., 136, 375-402, (2012) · Zbl 1257.90056
[23] Fischetti, M; Glover, F; Lodi, A, The feasibility pump, Math. Program., 104, 91-104, (2005) · Zbl 1077.90039
[24] Fischetti, M; Monaci, M, Exploiting erraticism in search, Oper. Res., 62, 114-122, (2014) · Zbl 1291.90148
[25] Fischetti, M; Salvagnin, D, Feasibility pump 2.0, Math. Program. Comput., 1, 201-222, (2009) · Zbl 1180.90208
[26] Floudas, C; Gounaris, C, A review of recent advances in global optimization, J. Glob. Optim., 45, 3-38, (2009) · Zbl 1180.90245
[27] Gamrath, G., Koch, T., Martin, A., Miltenberger, M., Weninger, D.: Progress in presolving for mixed integer programming. ZIB-Report 13-48, Zuse Institute Berlin (2013) · Zbl 1329.90089
[28] GloMIQO 2.0. http://helios.princeton.edu/GloMIQO/
[29] Ipopt (Interior Point OPTimizer). http://www.coin-or.org/Ipopt/ · Zbl 1170.90443
[30] 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)
[31] 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)
[32] Koch, T., Bargmann, D., Ebbers, M., Fügenschuh, A., Geißler, B., Geißler, N., Gollmer, R., Gotzes, U., Hayn, C., Heitsch, H., Henrion, R., Hiller, B., Humpola, J., Joormann, I., Kühl, V., Lehmann, T., Leövey, H., Martin, A., Mirkov, R., Möller, A., Morsi, A., Oucherif, D., Pelzer, A., Pfetsch, M.E., Schewe, L., Römisch, W., Rövekamp, J., Schmidt, M., Schultz, R., Schwarz, R., Schweiger, J., Spreckelsen, K., Stangl, C., Steinbach, M.C., Steinkamp, A., Wegner-Specht, I., Willert, B.M., Vigerske, S.: Evaluating gas network capacities. MOS-SIAM Series on Optimization (2014) (in preparation) · Zbl 1171.90476
[33] Koch, T; Ralphs, TK; Shinano, Y, Could we use a million cores to solve an integer program?, Math. Methods Oper. Res., 76, 67-93, (2012) · Zbl 1262.90106
[34] Liberti, L; Mladenović, N; Nannicini, G, A recipe for finding good solutions to minlps, Math. Program. Comput., 3, 349-390, (2011) · Zbl 1276.90041
[35] McNemar, Q, Note on the sampling error of the difference between correlated proportions or percentages, Psychometrika, 12, 153-157, (1947)
[36] Misener, R; Floudas, CA, Glomiqo: global mixed-integer quadratic optimizer, J. Glob. Optim., 57, 3-50, (2013) · Zbl 1272.90034
[37] Mittelmann, H.: Benchmarks for optimization software: Miplib2010. http://plato.asu.edu/bench.html
[38] Nannicini, G; Belotti, P, Rounding-based heuristics for nonconvex minlps, Math. Program. Comput., 4, 1-31, (2012) · Zbl 1257.90059
[39] Nannicini, G., Belotti, P., Liberti, L.: A local branching heuristic for MINLPs. e-prints (2008). http://arxiv.org/abs/0812.2188 · Zbl 1291.90144
[40] Pfetsch, M.E., Fügenschuh, A., ler, B.G., ler, N.G., Gollmer, R., Hiller, B., Humpola, J., Koch, T., Lehmann, T., Martin, A., Morsi, A., Rövekamp, J., Schewe, L., Schmidt, M., Schultz, R., Schwarz, R., Schweiger, J., Stangl, C., Steinbach, M., Vigerske, S., Willert, B.: Validation of nominations in gas network optimization: models, methods, and solutions. Optimization Methods and Software (2012)
[41] Sahinidis, NV, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[42] Shinano, Y; Achterberg, T; Berthold, T; Heinz, S; Koch, T; Bischof, C (ed.); Hegering, HG (ed.); Nagel, WE (ed.); Wittum, G (ed.), Parascip—a parallel extension of SCIP, 135-148, (2012), Berlin
[43] Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T., Winkler, M.: Solving hard MIPLIB 2003 problems with ParaSCIP on supercomputers: an update. ZIB-Report 13-66, Zuse Institute Berlin (2013)
[44] SoPlex. An open source LP solver implementing the revised simplex algorithm. http://soplex.zib.de/ · Zbl 1257.90059
[45] Vigerske, S.: Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. Ph.D. Thesis, Humboldt-Universität zu Berlin (2012) (submitted)
[46] Wächter, A; Biegler, LT, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57, (2006) · Zbl 1134.90542
[47] Wilcoxon, F, Individual comparisons by ranking methods, Biomet. Bull., 1, 80-83, (1945)
[48] Wunderling, R.: Paralleler und objektorientierter Simplex-Algorithmus. Ph.D. Thesis, Technische Universität Berlin (1996) · Zbl 0871.65048
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.