McCormick envelopes

Author: Susan Urban (smu29) (SYSEN 5800 Fall 2021)

Introduction

Optimization of a non-convex function f(x) is challenging since it may have multiple locally optimal points and it can take a significant amount of time or effort to determine if the problem has no solution or if the solution is global. Gradient based solvers are unable to certify optimality¹. Different techniques are used to address this challenge depending on the characteristics of the problem. One technique used is convex envelopes²:

Given a non-convex function f(x), g(x) is a convex envelope of f(x) for X $\in$ S if:

·      g(x) is convex under-estimator of f(x)

·      g(x)>=h(x) for all convex under-estimators h(x)

McCormick Envelopes

In particular, for bilinear (e.g., x*y, x²) Non-Linear Programming (NLP) problems³, the McCormick Envelope is a type of convex relaxation used for optimization.  

In case of an NLP, an LP relaxation is derived by replacing each bilinear term with a new variable and adding four sets of constraints. In the case of an MINLP, an MILP relaxation is derived. This strategy is known as McCormick relaxation.

The LP solution gives a lower bound and any feasible solution gives an upper bound.

As noted by Scott et al⁴, McCormick envelopes are attractive due to their recursive nature of their definition, which affords wide applicability and easy implementation computationally.  Furthermore, these relaxations are typically stronger than those resulting from convexification or linearization procedures.

Derivation of McCormick Envelopes

$w=xy$

$x^{L}\leq x\leq x^{U}$

$y^{L}\leq y\leq y^{U}$

where $x^{L},x^{U},y^{L},y^{U}$are   upper  and   lower  bound  values  for  $x$ and $y$, respectively.

$a=\left(x-x^{L}\right)$

$b=\left(y-y^{L}\right)$

$a*b\geq 0$

$a*b=\left(x-x^{L}\right)\left(y-y^{L}\right)=xy-x^{L}y-xy^{L}+x^{L}y^{L}\geq 0$

$w\geq x^{L}y+xy^{L}-x^{L}y^{L}$

$a=\left(x^{U}-x\right)$

$b=\left(y^{U}-y\right)$

$w\geq x^{U}y+xy^{U}-x^{U}y^{U}$

$a=\left(x^{U}-x\right)$

$b=\left(y-y^{L}\right)$

$w\leq x^{U}y+xy^{L}-x^{U}y^{L}$

$a=\left(x-x^{L}\right)$

$b=\left(y^{U}-y\right)$

$w\leq xy^{U}+x^{L}y-x^{L}y^{U}$

The underestimators of the function are represented by:

$w\geq x^{L}y+xy^{L}-x^{L}y^{L}$

$w\geq x^{U}y+xy^{U}-x^{U}y^{U}$

The overestimators of the function are represented by:

$w\leq x^{U}y+xy^{L}-x^{U}y^{L}$

$w\leq xy^{U}+x^{L}y-x^{L}y^{U}$

$\textstyle \sum _{j=1}^{n}\displaystyle c_{j}x_{j}^{*}=\textstyle \sum _{i=1}^{m}\displaystyle b_{i}y_{i}^{*}$

Example: Convex Relaxation

Original non convex problem:

$\min Z=\textstyle \sum _{i=1}\sum _{j=1}c_{i,j}x_{i}x_{j}+g_{0}(x)$

$s.t.\sum _{i=1}^{N}\sum _{j=1}^{N}c_{i,j}^{l}x_{i}x_{j}+g_{l}(x)\leq 0,\forall l\in L$

$x^{L}\leq x\leq x^{U}$

Replacing $u_{i,j}=x_{i}x_{j}$

Obtain relaxed, convex problem:

$\min Z=\textstyle \sum _{i=1}\sum _{j=1}c_{i,j}u_{i,j}+g_{0}(x)$

$s.t.\sum _{i=1}^{N}\sum _{j=1}^{N}c_{i,j}^{l}u_{i,j}+g_{l}(x)\leq 0,\forall l\in L$

$u_{i,j}\geq x_{i}^{L}x_{j}+x_{i}x_{j}^{L}-{x_{i}}^{L}{x_{j}}^{L},\forall l\in L$

$u_{i,j}\geq x_{i}^{U}x_{j}+x_{i}x_{j}^{U}-{x_{i}}^{U}{x_{j}}^{U},\forall l\in L$

$u_{i,j}\geq x_{i}^{L}x_{j}+x_{i}x_{j}^{U}-{x_{i}}^{L}{x_{j}}^{U},\forall l\in L$

$u_{i,j}\geq x_{i}^{U}x_{j}+x_{i}x_{j}^{L}-{x_{i}}^{U}{x_{j}}^{L},\forall l\in L$

$x^{L}\leq x^{U},u^{L}\leq u^{U}$

Good bounds are essential to focusing the feasible solution which may be obtained either by inspection or solving the optimization problem to minimize (maximize) x subject to the same constraints as the original problem.

As noted by Hazaji, state-of-the-art global optimization solvers implement bound contraction techniques in order to improve this bounding procedure. Once bound propagation is completed,

domain partitioning becomes necessary. Spatial branch and bound schemes [6, 7] are among the most effective partitioning methods in global optimization.

By splitting the domain of a given variable, the solver is able to divide the original domain into two smaller regions, further tightening the convex relaxations of each partition.

Example: Numerical$minZ=xy+6x+y$

$s.t.xy\leq 18$

$0\leq x\leq 10$

$0\leq y\leq 2$

$Letw=xy$

$minZ=-w+6x+y$

$s.t.w\leq 18$

$w\geq 0$

$w\geq 10y+2x-20$

$w\leq 10y$

$w\leq 2x$

Solved this linear programming problem using GAMS,

Application

Bilinear expressions are the most common nonconvex components in mathematical formulations modeling problems in: ⁵

Chemical engineering ^{8, 9, 10, 11}

Process network problems¹² (Quesada & Grossmann, 1995)

Water networks¹³ (Bagajewicz, 2000)                                                            

Pooling and blending¹⁴ (Haverly, 1978)

Supply Chain and Transportation ^{15, 9, 10, 11}

Energy Systems ^{16 17 18 19}

Conclusion

McCormick Envelopes provide a relaxation technique for bilinear non-convex nonlinear programming problems3. Since non-convex NLP are challenging to solve and may be time or resource intensive, McCormick envelopes are attractive due to their recursive nature of their definition, which affords wide applicability and easy implementation computationally.  Furthermore, these relaxations are typically stronger than those resulting from convexification or linearization procedures⁴.

References

1. Castro, Pedro. "A Tighter Piecewise McCormick Relaxation for Bilinear Problems." (n.d.): n. pag. 3 June 2014. Web. 6 June 2015. <http://minlp.cheme.cmu.edu/2014/papers/castro.pdf
2. You, F (2021). Notes for a lecture on Mixed Integer Non-Linear Programming (MINLP). Archives for SYSEN 5800 Computational Optimization (2021FA), Cornell University, Ithaca, NY.
3. Dombrowski, J. (2015, June 7). Northwestern University Open Text Book on Process Optimization, McCormick Envelopes Retrieved from https://optimization.mccormick.northwestern.edu/index.php/McCormick_envelopes
4.  Scott, J. K. Stuber, M. D. & Barton, P. I. (2011). Generalized McCormick Relaxations. Journal of Global Optimization, Vol. 51, Issue 4, 569-606 doi: 10.1007/s10898-011-9664-7
5. Hijazi, H., Perspective Envelopes for Bilinear Functions, unpublished manuscript, The Australian National University, Canberra, Australia 4841.pdf
6. Androulakis, I., Maranas, C., Floudas, C.: alphabb: A global optimization method for general constrained nonconvex problems. Journal of Global Optimization 7(4), 337{363 (1995)
7. Smith, E., Pantelides, C.: A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex fMINLPsg. Computers & Chemical Engineering 23(4), 457 { 478 (1999)
8. Geunes, J., Pardalos, P.: Supply chain optimization, vol. 98. Springer Science & BusinessMedia (2006)
9. Nahapetyan, A.: Bilinear programming: applications in the supply chain management bilinear programming: Applications in the supply chain management. In: C.A. Floudas, P.M. Pardalos (eds.) Encyclopedia of Optimization, pp. 282{288. Springer US (2009)
10. Nahapetyan, A.G., Pardalos, P.M.: A bilinear reduction based algorithm for solving capacitated multi-item dynamic pricing problems. Computers & Operations Research 35(5), 1601 { 1612 (2008). Part Special Issue: Algorithms and Computational Methods in Feasibility and Infeasibility
11. Rebennack, S., Nahapetyan, A., Pardalos, P.: Bilinear modeling solution approach for_xed charge network ow problems. Optimization Letters 3(3), 347{355 (2009)
12. Quesada, Ignacio & Grossmann, Ignacio. (1995). A Global Optimization Algorithm for Linear Fractional and Bilinear Programs. Journal of Global Optimization. 6. 39-76. 10.1007/BF01106605.
13. Bagajewicz, 2000
14. Haverly, 1978
15. Geunes, J., Pardalos, P.: Supply chain optimization, vol. 98. Springer Science & Business Media (2006)
16. Co_rin, C., Hijazi, H., Van Hentenryck, P., Lehmann, K.: Primal and dual bounds for optimal transmission switching. Proceedings of the 18th Power Syst. Computation Conf., Wroclaw Poland, PSCC (2014)
17. Gemine, Q., Ernst, D., Louveaux, Q., Corn_elusse, B.: Relaxations for multi-period optimal power ow problems with discrete decision variables. Proceedings of the 18th Power Syst. Computation Conf., Wroclaw, Poland, PSCC 2014 (2014)
18. Hijazi, H., Corin, C., Van Hentenryck, P.: Convex Quadratic Relaxations for Mixed-Integer Nonlinear Programs in Power Systems. NICTA Technical Report (2014)
19. Hijazi, H., Thiebaux, S.: Optimal AC distribution systems reconfiguration. Proceedings of the 18th Power Syst. Computation Conf., Wroclaw, Poland, PSCC 2014 (2014)