(522d) Heuristic for Improved Mccormick Relaxations in a Branch-and-Bound Framework

Deterministic Global Optimization (DGO) has many applications in the field of Chemical Engineering reaching from phase and chemical equilibrium problems [2, 4, 6, 7] to robust parameter estimation [8]. Modelling Chemical Engineering tasks often eventuate in a large number of variables making the solution of the underlying model very difficult for DGO. DGO relies on tight convex and concave relaxations, in best-case envelopes, of the functions used in the underlying model are needed. In many problems, the number of degrees of freedom is relatively small and this fact can be exploited by the application of the McCormick technique to algorithmic structures presented in [5]. The original McCormick rules [3] are applicable to factorable functions, i.e., functions of the form F₁(f₁)+F₂(f₂)·F₃(f₃), where F_i are univariate and f_i are multivariate functions and were extended to multivariate outer functions in [9]. When constructing McCormick under- and overestimators, valid range bounds for each factor are needed. As the number of propagations increases, the quality of estimated range bounds gets worse [1]. This is particularly true when using simple interval arithmetics for the underlying variable bounds and each factor in the propagation procedure. To overcome this issue, we present a heuristic to improve the range bounds in each factor based in part on [5]. Theoretically, the heuristic cannot worsen the range bounds but it does not guarantee to improve the bounds. Practically, we demonstrate substantial improvement. Finally, we compare its performance to other known range and domain reduction techniques.

References

[1] Bompadre, A. and A. Mitsos (2012). Convergence rate of McCormick relaxations. Journal of Global Optimization 52(1), 1 - 28.

[2] Duran, M. A. and I. E. Grossmann (1986). An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming 36(3), 307 - 339.

[3] McCormick, G. P. (1976). Computability of global solutions to factorable nonconvex programs:
Part I-Convex underestimating problems. Mathematical Programming, 10(1):147-175.

[4] McDonald, C. and C. Floudas (1995). Global optimization for the phase and chemical equilibrium problem: Application to the NRTL equation. Computers & Chemical Engineering 19(11), 1111 - 1139.

[5] Mitsos, A., B. Chachuat, and P. I. Barton (2009). McCormick-based relaxations of algorithms. SIAM Journal on Optimization 20(2), 573 - 601.

[6] Ryoo, H. S. and N. V. Sahinidis (1995). Global optimization of nonconvex NLPs and MINLPs with applications in process design. Computers & Chemical Engineering 19(5), 551 - 566.

[7] Sahinidis, N.V., I.E. Grossmann, R.E. Fornari and M. Chathrathi (1989). Optimization model for long range planning in the chemical industry. Computers & Chemical Engineering 13(9), 1049 – 1063.

[8] Singer, A.B., J. W. Taylor, P. I. Barton, and W. H. Green (2006). Global dynamic optimization for parameter estimation in chemical kinetics, J. Phys. Chem. A, 110, pp. 971–976.

[9] Tsoukalas, A. and A. Mitsos (2014). Multivariate McCormick relaxations. Journal of Global Optimization, 59:633-662.