×

zbMATH — the first resource for mathematics

An efficient strategy for the activation of MIP relaxations in a multicore global MINLP solver. (English) Zbl 1393.90076
Summary: Solving mixed-integer nonlinear programming (MINLP) problems to optimality is a NP-hard problem, for which many deterministic global optimization algorithms and solvers have been recently developed. MINLPs can be relaxed in various ways, including via mixed-integer linear programming (MIP), nonlinear programming, and linear programming. There is a tradeoff between the quality of the bounds and CPU time requirements of these relaxations. Unfortunately, these tradeoffs are problem-dependent and cannot be predicted beforehand. This paper proposes a new dynamic strategy for activating and deactivating MIP relaxations in various stages of a branch-and-bound algorithm. The primary contribution of the proposed strategy is that it does not use meta-parameters, thus avoiding parameter tuning. Additionally, this paper proposes a strategy that capitalizes on the availability of parallel MIP solver technology to exploit multicore computing hardware while solving MINLPs. Computational tests for various benchmark libraries reveal that our MIP activation strategy works efficiently in single-core and multicore environments.

MSC:
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
PDF BibTeX Cite
Full Text: DOI
References:
[1] Belotti, P; Lee, J; Liberti, L; Margot, F; Waechter, A, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[2] 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
[3] CMU-IBM cyber-infrastructure for MINLP collaborative site. www.minlp.org (2016). Accessed 27 Sept 2016 · Zbl 1099.90047
[4] Dolan, E; More, J, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[5] FICO Xpress-optimizer reference manual, 20.0 edition. http://www.fico.com/xpress (2009). Accessed 27 Sept 2016 · Zbl 0906.90159
[6] Floudas, CA; Gounaris, CE, A review of recent advances in global optimization, J. Glob. Optim., 45, 3-38, (2009) · Zbl 1180.90245
[7] Goux, J-P; Leyffer, S, Solving large MINLPs on computational grids, Optim. Eng., 3, 327-346, (2002) · Zbl 1035.90049
[8] Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht (1995) · Zbl 0836.90134
[9] Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 2nd edn. Springer, Berlin (1993) · Zbl 0704.90057
[10] International Business Machines Corporation. CPLEX User’s Manual V12.6. http://www.ibm.com/support/knowledgecenter/SSSA5P (2015). Accessed 27 Sept 2016 · Zbl 1035.90049
[11] Khajavirad, A., Sahinidis, N.V.: A hybrid LP/NLP paradigm for global optimization relaxations. Math. Program. Comput. (under review) (2017) · Zbl 1400.90227
[12] Kılınç, M.R., Sahinidis, N.V.: Solving MINLPs with BARON, Mixed-Integer Nonlinear Programming Workshop Website. http://minlp.cheme.cmu.edu/2014/papers/kilinc.pdf (2014). Accessed 27 Sept 2016 · Zbl 1049.90004
[13] 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)
[14] Lin, Y; Schrage, L, The global solver in the LINDO API, Optim. Methods Softw., 24, 657-668, (2009) · Zbl 1177.90325
[15] Misener, R; Floudas, CA, ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Glob. Optim., 59, 503-526, (2014) · Zbl 1301.90063
[16] Pintér, J.D. (ed.): Global Optimization: Scientific and Engineering Case Studies, vol. 85. Springer, New York (2006) · Zbl 1103.90011
[17] Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, J. Glob. Optim., 8, 107-138, (1996) · Zbl 0856.90103
[18] Sahinidis, NV; Bliek, C (ed.); Jermann, C (ed.); Neumaier, A (ed.), Global optimization and constraint satisfaction: the branch-and-reduce approach, No. 2861, 1-16, (2003), Berlin
[19] Sahinidis, N.V.: BARON Manual. BARON official website. http://www.minlp.com/downloads/docs/baron%20manual.pdf (2016). Accessed 26 Sept 2016 · Zbl 0856.90103
[20] Shectman, JP; Sahinidis, NV, A finite algorithm for global minimization of separable concave programs, J. Glob. Optim., 12, 1-36, (1998) · Zbl 0906.90159
[21] Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T.: ParaSCIP: A Parallel Extension of SCIP. Competence in High Performance Computing 2010, pp. 135-148. Springer, Berlin (2011)
[22] Smith, EM; Pantelides, CC, Global optimisation of nonconvex minlps, Comput. Chem. Eng., 21, s791-s796, (1997)
[23] Tawarmalani, M; Ahmed, S; Sahinidis, NV, Product disaggregation and relaxations of mixed-integer rational programs, Optim. Eng., 3, 281-303, (2002) · Zbl 1035.90064
[24] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Nonconvex Optimization and Its Applications, vol. 65. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1031.90022
[25] Tawarmalani, M; Sahinidis, NV, Convex extensions and convex envelopes of l.s.c. functions, Math. Program., 93, 247-263, (2002) · Zbl 1065.90062
[26] Tawarmalani, M; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591, (2004) · Zbl 1062.90041
[27] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[28] Vigerske, S., Gleixner, A.: SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework. Optim. Methods Softw. 1-31 (2017). doi:10.1080/10556788.2017.1335312 · Zbl 1062.90041
[29] Zhou, K; Chen, X; Shao, Z; Wan, W; Biegler, LT, Heterogeneous parallel method for mixed integer nonlinear programming, Comput. Chem. Eng., 66, 290-300, (2014)
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.