×

Tighter McCormick relaxations through subgradient propagation. (English) Zbl 1429.49033

Summary: Tight convex and concave relaxations are of high importance in deterministic global optimization. We present a method to tighten relaxations obtained by the McCormick technique. We use the McCormick subgradient propagation [the second author et al., SIAM J. Optim. 20, No. 2, 573–601 (2009; Zbl 1192.65083)] to construct simple affine under- and overestimators of each factor of the original factorable function. Then, we minimize and maximize these affine relaxations in order to obtain possibly improved range bounds for every factor resulting in possibly tighter final McCormick relaxations. We discuss the method and its limitations, in particular the lack of guarantee for improvement. Subsequently, we provide numerical results for benchmark cases found in the MINLPLib2 library and case studies presented in previous works, where the McCormick technique appears to be advantageous, and discuss computational efficiency. We see that the presented algorithm provides a significant improvement in tightness and decrease in computational time, especially in the case studies using the reduced space formulation presented in [D. Bongartz and the second author, J. Glob. Optim. 69, No. 4, 761–796 (2017; Zbl 1386.90112)].

MSC:

49M20 Numerical methods of relaxation type
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Androulakis, I.P., Maranas, C.D., Floudas, C.A.: \[ \alpha\] αBB: a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7(4), 337-363 (1995) · Zbl 0846.90087
[2] Belotti, P., Lee, J., Liberti, L., Margot, F., Wächter, A.: Branching and bounds tightening techniques for non-convex minlp. Optim. Method Softw. 24(4-5), 597-634 (2009) · Zbl 1179.90237
[3] Bendtsen, C., Staunin, O.: FADBAD++, A Flexible C++ Package for Automatic Differentiation. Version 2.1 (2012). http://www.fadbad.com. Accessed 18 Octob 2016
[4] Bertsekas, D.P.: Convex Optimization Algorithms. Athena Scientific, Belmont (2015) · Zbl 1347.90001
[5] Bertsekas, D.P., Nedic, A., Ozdaglar, A.E., et al.: Convex Analysis and Optimization. Athena Scientific, Belmont (2003) · Zbl 1140.90001
[6] Bompadre, A., Mitsos, A., Chachuat, B.: Convergence analysis of Taylor models and McCormick-Taylor models. J. Glob. Optim. 57(1), 75-114 (2013) · Zbl 1295.90052
[7] Bongartz, D., Mitsos, A.: Deterministic global optimization of process flowsheets in a reduced space using McCormick relaxations. J. Glob. Optim. 69, 761-796 (2017) · Zbl 1386.90112
[8] Bongartz, D., Mitsos, A.: Deterministic global flowsheet optimization - between equation-oriented and sequential-modular. AIChE J 65, 1022-1034 (2019)
[9] Bongartz, D., Najman, J., Sass, S., Mitsos, A.: MAiNGO: McCormick-based algorithm for mixed-integer nonlinear global optimization. In: Technical Report, Process Systems Engineering (AVT.SVT), RWTH Aachen University (2018). http://permalink.avt.rwth-aachen.de/?id=729717. Accessed 7 Jan 2019
[10] Brearley, A.L., Mitra, G., Williams, H.P.: Analysis of mathematical programming problems prior to applying the simplex algorithm. Math. Program. 8(1), 54-83 (1975) · Zbl 0317.90037
[11] Chachuat, B., Houska, B., Paulen, R., Peri’c, N., Rajyaguru, J., Villanueva, M.E.: Set-theoretic approaches in analysis, estimation and control of nonlinear systems. IFAC PapersOnLine 48(8), 981-995 (2015)
[12] Comba, J.L.D., Stolfi, J.: Affine arithmetic and its applications to computer graphics. In: Proceedings of VI SIBGRAPI (Brazilian Symposium on Computer Graphics and Image Processing), pp. 9-18. Citeseer (1993)
[13] Cornelius, H., Lohner, R.: Computing the range of values of real functions with accuracy higher than second order. Computing 33(3-4), 331-347 (1984) · Zbl 0556.65037
[14] International Business Machines Corporation:: IBM ILOG CPLEX v12.8. Armonk (2009)
[15] De Figueiredo, L.H., Stolfi, J.: Affine arithmetic: concepts and applications. Numer. Algorithms 37(1-4), 147-158 (2004) · Zbl 1074.65050
[16] Du, K., Kearfott, R.B.: The cluster problem in multivariate global optimization. J. Glob. Optim. 5(3), 253-265 (1994) · Zbl 0824.90121
[17] Gleixner, A.M., Berthold, T., Müller, B., Weltge, S.: Three enhancements for optimization-based bound tightening. J. Glob. Optim. 67(4), 731-757 (2017) · Zbl 1369.90106
[18] Gould, N., Scott, J.: A note on performance profiles for benchmarking software. ACM Trans. Math. Softw. 43(2), 15:1-15:5 (2016) · Zbl 1369.65202
[19] Hamed, A.S.E.D., McCormick, G.P.: Calculation of bounds on variables satisfying nonlinear inequality constraints. J. Glob. Optim. 3(1), 25-47 (1993) · Zbl 0845.90105
[20] Hansen, P., Jaumard, B., Lu, S.H.: An analytical approach to global optimization. Math. Program. 52(1), 227-254 (1991) · Zbl 0747.90091
[21] Johnson, S.: The NLopt nonlinear-optimization package. http://ab-initio.mit.edu/nlopt. Accessed Feb 2018
[22] Kannan, R., Barton, P.I.: The cluster problem in constrained global optimization. J. Glob. Optim. 69, 629-676 (2017) · Zbl 1379.49027
[23] Kannan, R., Barton, P.I.: Convergence-order analysis of branch-and-bound algorithms for constrained problems. J. Glob. Optim. 71, 753-813 (2017) · Zbl 1397.49042
[24] Kearfott, B., Du, K.: The Cluster Problem in Global Optimization: The Univariate Case, pp. 117-127. Springer, Vienna (1993) · Zbl 0791.65045
[25] Khan, K.A.: Subtangent-based approaches for dynamic set propagation. In: 57th IEEE Conference on Decision and Control (2018)
[26] Lin, Y., Schrage, L.: The global solver in the LINDO API. Optim. Methods Softw. 24(4-5), 657-668 (2009) · Zbl 1177.90325
[27] Locatelli, M., Schoen, F.: Global optimization: theory, algorithms, and applications. In: SIAM, (2013) · Zbl 1286.90003
[28] Maranas, C.D., Floudas, C.A.: A global optimization approach for Lennard-Jones microclusters. J. Chem. Phys. 97(10), 7667-7678 (1992)
[29] 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
[30] McCormick, G.P.: Nonlinear Programming: Theory, Algorithms, and Applications. Wiley, New York (1983) · Zbl 0563.90068
[31] Misener, R., Floudas, C.: Antigone: algorithms for continuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59(2-3), 503-526 (2014) · Zbl 1301.90063
[32] Mitsos, A., Chachuat, B., Barton, P.I.: McCormick-based relaxations of algorithms. SIAM J. Optim. 20(2), 573-601 (2009) · Zbl 1192.65083
[33] Moore, R.E., Bierbaum, F.: Methods and applications of interval analysis. In: SIAM Studies in Applied and Numerical Mathematics, Society for Industrial and Applied Mathematics (1979)
[34] Morrison, D., Jacobson, S., Sauppe, J., Sewell, E.: Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning. Discret. Optim. 19, 79-102 (2016) · Zbl 1387.90010
[35] Najman, J., Bongartz, D., Tsoukalas, A., Mitsos, A.: Erratum to: multivariate McCormick relaxations. J. Glob. Optim. 68, 1-7 (2016) · Zbl 1476.90265
[36] Najman, J.; Mitsos, A.; Kravanja, Z. (ed.); Bogataj, M. (ed.), Convergence order of mccormick relaxations of LMTD function in heat exchanger networks, No. 38, 1605-1610 (2016), Amsterdam
[37] Najman, J., Mitsos, A.: On tightness and anchoring of McCormick and other relaxations. J. Glob. Optim. (2017). https://doi.org/10.1007/s10898-017-0598-6 · Zbl 1425.49014
[38] Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization. 4OR 13(3), 247-277 (2015) · Zbl 1320.90065
[39] Puranik, Y., Sahinidis, N.V.: Bounds tightening based on optimality conditions for nonconvex box-constrained optimization. J. Glob. Optim. 67(1-2), 59-77 (2017) · Zbl 1359.90107
[40] Puranik, Y., Sahinidis, N.V.: Domain reduction techniques for global NLP and MINLP optimization. Constraints 22, 1-39 (2017) · Zbl 1387.90164
[41] Ratschek, H., Rokne, J.: Computer Methods for the Range of Functions. Halsted Press Chichester, New York (1984) · Zbl 0584.65019
[42] Ryoo, H.S., Sahinidis, N.V.: Global optimization of nonconvex NLPs and MINLPs with applications in process design. Comput. Chem. Eng. 19(5), 551-566 (1995)
[43] Ryoo, H.S., Sahinidis, N.V.: A branch-and-reduce approach to global optimization. J. Glob. Optim. 8(2), 107-138 (1996) · Zbl 0856.90103
[44] Sahlodin, A., Chachuat, B.: Convex, concave relaxations of parametric odes using taylor models. Comput. Chem. Eng. 35(5), 844-857, : Selected Papers from ESCAPE-20 (European Symposium of Computer Aided Process Engineering-20), Ischia, Italy (2011) · Zbl 1214.65041
[45] Schichl, H., Neumaier, A.: Interval analysis on directed acyclic graphs for global optimization. J. Glob. Optim. 33(4), 541-562 (2005) · Zbl 1094.65061
[46] Schweidtmann, A.M., Mitsos, A.: Global deterministic optimization with artificial neural networks embedded. J. Optim. Theory Appl. (2018) · Zbl 1407.90263
[47] Scott, J.K., Stuber, M.D., Barton, P.I.: Generalized McCormick relaxations. J. Glob. Optim. 51(4), 569-606 (2011) · Zbl 1232.49033
[48] Shectman, J.P., Sahinidis, N.V.: A finite algorithm for global minimization of separable concave programs. J. Glob. Optim. 12(1), 1-36 (1998) · Zbl 0906.90159
[49] Smith, E.M., Pantelides, C.C.: Global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 21, 791-796 (1997)
[50] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, vol. 65. Springer, New York (2002) · Zbl 1031.90022
[51] Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225-249 (2005) · Zbl 1099.90047
[52] Tsoukalas, A., Mitsos, A.: Multivariate McCormick relaxations. J. Glob. Optim. 59, 633-662 (2014) · Zbl 1312.90068
[53] Vigerske, S., Gleixner, A.: SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework. Optim. Method. Softw. 33(3), 563-593 (2018) · Zbl 1398.90112
[54] 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(1), 25-57 (2006) · Zbl 1134.90542
[55] Wechsung, A.: Global optimization in reduced space. In: Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge (2014)
[56] Wechsung, A., Schaber, S.D., Barton, P.I.: The cluster problem revisited. J. Glob. Optim. 58(3), 429-438 (2014) · Zbl 1297.49046
[57] Wechsung, A., Scott, J.K., Watson, H.A.J., Barton, P.I.: Reverse propagation of McCormick relaxations. J. Glob. Optim. 63(1), 1-36 (2015) · Zbl 1322.49048
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.