×

zbMATH — the first resource for mathematics

Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON. (English) Zbl 1398.90110
Summary: In this paper, we present recent developments in the global optimization software BARON to address problems with integer variables. A primary development was the addition of mixed-integer linear programming relaxations to BARON’s portfolio of linear and nonlinear programming relaxations, aiming to improve dual bounds and offer good starting points for primal heuristics. Since such relaxations necessitate the solution of NP-hard problems, their introduction to a branch-and-bound algorithm raises many practical issues regarding their effective implementation. In addition to describing BARON’s dynamic strategy for deciding under what conditions to activate integer programming relaxations in the course of branch-and-bound, the paper also describes cutting plane and probing techniques that originate from the literature of integer linear programming and have been adapted in BARON to solve nonlinear problems. Finally, we describe BARON’s primal heuristics for finding good solutions of mixed-integer nonlinear programmes. For all these techniques, we report extensive computational results on a public data set, aiming to analyse the impact of each technique in the solution process and identify techniques that expedite solution the most.

MSC:
90C11 Mixed integer programming
90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.; Berthold, T., improving the feasibility pump, Discrete Optim, 4, 77-86, (2007) · Zbl 1170.90443
[2] Achterberg, T.; Koch, T.; Martin, A., branching rules revisited, Oper. Res. Lett, 33, 42-54, (2005) · Zbl 1076.90037
[3] Adams, W.P.; Sherali, H.D., A tight linearization and an algorithm for zero-one quadratic programming problems, Manage. Sci, 32, 1274-1290, (1986) · Zbl 0623.90054
[4] Atamtürk, A.; Nemhauser, G.L.; Savelsbergh, M.W.P., conflict graphs in solving integer programming problems, Eur. J. Oper. Res, 121, 40-55, (2000) · Zbl 0959.90034
[5] Bao, X.; Sahinidis, N.V.; Tawarmalani, M., multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs, Optim. Methods Softw, 24, 485-504, (2009) · Zbl 1179.90252
[6] Bao, X.; Khajavirad, A.; Sahinidis, N.V.; Tawarmalani, M., global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput, 7, 1-37, (2015) · Zbl 1317.90243
[7] 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
[8] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., mixed-integer nonlinear optimization, Acta Numer, 22, 1-131, (2013) · Zbl 1291.65172
[9] Heuristic algorithms in global MINLP solvers, Ph.D. diss., Technischen Universität Berlin, 2014
[10] Berthold, T., RENS: the optimal rounding, Math. Program. Comput, 6, 33-54, (2014) · Zbl 1304.90147
[11] Bonami, P.; Gonçalves, J.P.M., heuristics for convex mixed integer nonlinear programs, Comput. Optim. Appl, 51, 729-747, (2012) · Zbl 1241.90189
[12] 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
[13] Algorithms and software for convex mixed integer nonlinear programs, in Mixed Integer Nonlinear Programming, J. Lee and S. Leyffer, eds., The IMA Volumes in Mathematics and Its Applications, Vol. 154, Springer, New York, 2012, pp. 1-39 · Zbl 1242.90121
[14] Burer, S.; Letchford, A.N., non-convex mixed-integer nonlinear programming: A survey, Surv. Oper. Res. Manage. Sci, 17, 97-106, (2012)
[15] Bussieck, M.R.; Drud, A.S.; Meeraus, A., minlplib—A collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput, 15, 114-119, (2003) · Zbl 1238.90104
[16] CMU-IBM open source MINLP project test set. Available at http://egon.cheme.cmu.edu/ibm/page.htm
[17] COIN-OR Project, FilterSD 2 Coin FilterSD solver. Available at https://projects.coin-or.org/filterSD
[18] Polyhedral approaches to mixed integer linear programming, in 50 Years of Integer Programming 1958-2008, M. Jünger, T.M. Liebling, D. Naddef, G.L. Nemhauser, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and L.A. Wolsey, eds., Springer, Berlin, 2010, pp. 343-385
[19] Crowder, H.; Johnson, E.L.; Padberg, M.W., solving large scale zero-one linear programming problems, Oper. Res, 31, 803-834, (1983) · Zbl 0576.90065
[20] Danna, E.; Rothberg, E.; LePape, C., exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program, 102, 71-90, (2005) · Zbl 1131.90036
[21] Dolan, E.D.; Moré, J.J., benchmarking optimization software with performance profiles, Math. Program, 91, 201-213, (2002) · Zbl 1049.90004
[22] CONOPT 3.17A, User’s Manual, ARKI Consulting and Development A/S, Bagsvaerd, 2016
[23] Fischetti, M.; Lodi, A., local branching, Math. Program, 98, 23-47, (2002) · Zbl 1060.90056
[24] Floudas, C.A., Nonlinear and Mixed-integer Optimization: Fundamentals and Applications, (1995), Oxford University Press, New York, NY · Zbl 0886.90106
[25] Floudas, C.A., Deterministic Global Optimization, Vol. 37, (1999), Springer, Secaucus, NJ · Zbl 1045.90094
[26] User’s guide for SNOPT 7: A FORTRAN package for large-scale nonlinear programming, Tech. Rep., University of California, San Diego and Stanford University, Stanford, CA, 2008
[27] Mixed-integer nonlinear programming: A survey of algorithms and applications, in Large-scale Optimization with Applications, Part II: Optimal Design and Control, L.T. Biegler, T.F. Coleman, A.R. Conn, and F.N. Santosa, eds., Springer, New York, 199773100
[28] Lifted cover inequalities for 0-1 and mixed 0-1 integer programs, Ph.D. diss., Georgia Institute of Technology, 1995
[29] Gu, Z.; Nemhauser, G.L.; Savelsbergh, M.W.P., lifted cover inequalities for 0-1 integer programs: computation, INFORMS J. Comput, 10, 427-437, (1998)
[30] Nonlinear integer programming, in 50 Years of Integer Programming 1958-2008, M. Jönger, T.M. Liebling, D. Naddef, G.L. Nemhauser, W.R. Pulleyblank, G. Reinelt, G. Rinaldi, and L.A. Wolsey, eds., Springer, Heidelberg, 2010, pp. 561-618
[31] Horst, R.; Tuy, H., Global Optimization: Deterministic Approaches, (1996), Springer Verlag, Berlin · Zbl 0867.90105
[32] IBM: CPLEX Optimizer (2016). Available at http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
[33] Khajavirad, A.; Sahinidis, N.V., convex envelopes of products of convex and component-wise concave functions, J. Global Optim, 52, 391-409, (2011) · Zbl 1268.90052
[34] Khajavirad, A.; Sahinidis, N.V., convex envelopes generated from finitely many compact convex sets, Math. Program, 137, 371-408, (2013) · Zbl 1284.90055
[35] Khajavirad, A.; Sahinidis, N.V., A hybrid LP/NLP paradigm for global optimization relaxations, Math. Program. Comput · Zbl 1400.90227
[36] Solving MINLPs with BARON. Mixed-integer Nonlinear Programming Workshop Website, 2014. Available at minlp.cheme.cmu.edu/2014/papers/kilinc.pdf
[37] State-of-the-art in mixed-integer nonlinear programming, in Advances and Trends in Optimization with Engineering Applications, T. Terlaky, M. Anjos and S. Ahmed, eds., MOS-SIAM Book Series on Optimization, SIAM, Philadelphia, PA, 2017273292
[38] Lee, J.; Leyffer, S., Mixed Integer Nonlinear Programming, (2012), Springer Science & Business Media, New York, NY
[39] Lin, Y.; Schrage, L., the global solver in the LINDO API, Optim. Methods Softw, 24, 657-668, (2009) · Zbl 1177.90325
[40] The SCIP optimization suite 4.0, Tech. Rep. 17-12, ZIB, Berlin, 2017
[41] McCormick, G.P., computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems, Math. Program, 10, 147-175, (1976) · Zbl 0349.90100
[42] Misener, R.; Floudas, C.A., glomiqo: global mixed-integer quadratic optimizer, J. Global Optim, 57, 3-50, (2013) · Zbl 1272.90034
[43] Misener, R.; Floudas, C.A., ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations, J. Global Optim, 59, 503-526, (2014) · Zbl 1301.90063
[44] MINOS 5.5 User’s Guide, Tech. Rep. SOL 83-20R, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA, 1995
[45] A local branching heuristic for MINLPs, preprint (2008). Available at arXiv:0812.2188
[46] Domain reduction techniques for global NLP and MINLP optimization, Constraints222017338376 · Zbl 1387.90164
[47] Rikun, A.D., A convex envelope formula for multilinear functions, J. Global Optim, 10, 425-437, (1997) · Zbl 0881.90099
[48] Ryoo, H.S.; Sahinidis, N.V., global optimization of nonconvex NLPs and MINLPs with applications in process design, Comput. Chem. Eng, 19, 551-566, (1995)
[49] Ryoo, H.S.; Sahinidis, N.V., A branch-and-reduce approach to global optimization, J. Global Optim, 8, 107-138, (1996) · Zbl 0856.90103
[50] Sahinidis, N.V., BARON: A general purpose global optimization software package, J. Global Optim, 8, 201-205, (1996) · Zbl 0856.90104
[51] Savelsbergh, M.W.P., preprocessing and probing techniques for mixed integer programming problems, ORSA J. Comput, 6, 445-454, (1994) · Zbl 0814.90093
[52] Shectman, J.P.; Sahinidis, N.V., A finite algorithm for global minimization of separable concave programs, J. Global Optim, 12, 1-36, (1998) · Zbl 0906.90159
[53] Smith, E.M.B.; Pantelides, C.C., global optimisation of nonconvex MINLPs, Comput. Chem. Eng, 21, S791-S796, (1997)
[54] Tawarmalani, M.; Sahinidis, N.V., Convexification and Global Optimization in Continuous and Mixed-integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, (2002), Kluwer Academic Publishers, Dordrecht · Zbl 1031.90022
[55] Tawarmalani, M.; Sahinidis, N.V., global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Math. Program, 99, 563-591, (2004) · Zbl 1062.90041
[56] Tawarmalani, M.; Sahinidis, N.V., A polyhedral branch-and-cut approach to global optimization, Math. Program, 103, 225-249, (2005) · Zbl 1099.90047
[57] MINLPLib 2. Available at
[58] Wächter, A.; Biegler, L.T., on the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program, 106, 25-57, (2006) · Zbl 1134.90542
[59] Zeng, B.; Richard, J.-P.P., A polyhedral study on 0–1 knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting, Discrete Optim, 8, 277-301, (2011) · Zbl 1241.90128
[60] Zhou, K.; Kılınç, M.; Chen, X.; Sahinidis, N.V., an efficient strategy for the activation of MIP relaxations in a multicore global MINLP solver, J. Global Optim · Zbl 1393.90076
[61] Zorn, K.; Sahinidis, N.V., computational experience with applications of bilinear cutting planes, Ind. Eng. Chem. Res, 52, 7514-7525, (2013)
[62] Zorn, K.; Sahinidis, N.V., global optimization of general non-convex problems with intermediate bilinear substructures, Optim. Methods Softw, 29, 442-462, (2013) · Zbl 1285.90043
[63] Zorn, K.; Sahinidis, N.V., global optimization of general nonconvex problems with intermediate polynomial substructures, J. Global Optim, 59, 673-693, (2014) · Zbl 1301.90066
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.