McCormick envelopes

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Author Name: John Dombrowski
Steward: Dajun Yue and Fengqi You

Introduction

Graphical Representation of McCormick Envelope

McCormick Envelopes are a type of convex relaxation used in bilinear Non Linear Programming problems. Many times these envelopes are used to solve a Mixed Integer Non Linear Programming problem by relaxing the MINLP problem so that it becomes a convex NLP. Solving this convex NLP will provide a lower bound number on the optimal solution of the original MINLP. For more information on solving MINLPs see Spatial Branch and Bound method.

Solving non convex problems is a complicated task. First, the non convex function is transformed into a convex function by relaxing the parameters on the problem. Relaxing the bounds through a convex relaxation decreases the computational difficulty of solving the problem at the cost of introducing solutions that do not correspond to the original objective function i.e. the optimal solution in the relaxed problem will not always be the optimal solution to the objective problem. Solving the convex problem will provide a lower bound for the optimal solution. Having a tighter relaxation that is still convex will provide a lower bound that is closer to the solution. Therefore, it is important to choose a convex relaxation that has the tightest bounds. The McCormick Envelope is one particular kind of relaxation that guarantees convexity but keeps the bounds sufficiently tight 1 .

Using McCormick envelopes relaxes a non-convex problem into a convex problem. This eliminates the possibility of having several local minima that a solver may interpret as a global minimum. By making the problem convex, the minimum that is found for the problem will be a global minimum for that relaxed problem. This solution is then a lower bound solution for the original problem. An upper bound can be obtained by solving the original non convex problem using values obtained from the relaxed problem and then checking for feasibility. McCormick Envelopes provide an envelope that retains convexity while minimizing the size of the new feasible region. This allows the lower bound solutions obtained from using these envelopes to be closer to the true solution than if other convex relaxations were used. Tighter envelopes decreases the time needed to solve complex computational problems.2

Derivation for bilinear term

$w=xy$
$x^{L}\le x\le x^{U}$ $y^{L}\le y\le y^{U}$ where $x^{L}, x^{U}, y^{L}, y^{U}$ are upper and lower bound values for x and y respectively
$a=(x-x^{L})$ $b=(y-y^{L})$
$a*b \ge 0$
$a*b =$ $(x-x^{L})$ $(y-y^{L})=$ $xy -$ $x^{L}y -$ $xy^{L}+$ $x^{L}y^{L} \ge 0$
$w \ge x^{L}y+$ $xy^{L}-$ $x^{L}y^{L}$

$a=(x^{U}-x)$ $b=(y^{U}-y)$
$w \ge x^{U}y+$ $xy^{U}-$ $x^{U}y^{U}$

$a=(x^{U}-x)$ $b=(y-y^{L})$
$w \le x^{U}y+$ $xy^{L}-$ $x^{U}y^{L}$

$a=(x-x^{L})$ $b=(y^{U}-y)$
$w \le xy^{U}+$ $x^{L}y-$ $x^{L}y^{U}$

The underestimators of the function are represented by:
$w \ge x^{L}y+$ $xy^{L}-$ $x^{L}y^{L}$  ; $w \ge x^{U}y+$ $xy^{U}-$ $x^{U}y^{U}$

The overestimators of the function are represented by:
$w \le x^{U}y+$ $xy^{L}-$ $x^{U}y^{L}$ ; $w \le xy^{U}+$ $x^{L}y-$ $x^{L}y^{U}$

Obtaining Upper and Lower Bounds

Values of upper and lower bounds for each term must be estimated if they are not provided explicitly in the problem statement. A very good way to do this is to eliminate the objective function and then maximize or minimize the variable subject to the constraints of the original problem to find the maximum and minimum of the variable. Using these values will give a tighter relaxation on the problem while still containing the optimal solution.

Example: Convex Relaxation

Given a general non-convex function, we can relax the function into a convex problems using McCormick Envelopes. This new problem can then be solved as a Non Linear Programming problem which will yield a lower bound solution to the original problem. $Z= \text{min} \sum_i \sum_j c_{ij}x_{i}x_{j} + g_{o}(x)$
$s.t. \sum_i \sum_j c_{ij}^{l}x_{i}x_{j} + g_{l}(x) \le 0 \text{ } \forall l\in L$
$x^{L} \le x \le x^{U}$

By replacing $x_{i}x_{j} = w_{ij}$ and introducing the inequalities derived above we create the following convex problem:

$Z= \text{min} \sum_i \sum_j c_{ij}w_{ij} + g_{o}(x)$
$s.t. \sum_i \sum_j c_{ij}^{l}w_{ij} + g_{l}(x) \le 0 \text{ } \forall l\in L$

$w_{ij} \ge x^{L}_{i}x_{j}+$ $x_{i}x_{j}^{L}-$ $x^{L}_{i}x^{L}_{j}$
$w_{ij} \ge x_{i}^{U}x_{j}+$ $x_{i}x_{j}^{U}-$ $x_{i}^{U}x_{j}^{U}$
$w_{ij} \le x_{i}^{U}x_{j}+$ $x_{i}x_{j}^{L}-$ $x_{i}^{U}x_{j}^{L}$
$w_{ij} \le x_{i}x_{j}^{U}+$ $x_{i}^{L}x_{j}-$ $x_{i}^{L}x_{j}^{U}$
$x^{L}\le x\le x^{U}$ $w^{L}\le w\le w^{U}$

If g(x) is a linear function this problem is now an LP. Solving will yield a lower bound solution to the original problem.

Example: Numerical

Given the following non convex function: $\text{min } Z=-xy-2x$
$\text{s.t. } xy \le 12$
$0 \le x \le 6,$ $0 \le y \le 3$

Introducing McCormick convex envelopes:
$\text{min } Z=-w-2x$
$\text{s.t. } w \le 12$
$w \ge x^{L}y+$ $xy^{L}-$ $x^{L}y^{L}$  ; $w \ge x^{U}y+$ $xy^{U}-$ $x^{U}y^{U}$
$w \le x^{U}y+$ $xy^{L}-$ $x^{U}y^{L}$ ; $w \le xy^{U}+$ $x^{L}y-$ $x^{L}y^{U}$
$0 \le x \le 6 ,$ $0 \le y \le 3$

Substituting for $x^{U}, x^{L}, y^{U}, y^{L}$ we get the following LP:
$\text{min } Z=-w-2x$
$\text{s.t. } w \le 12$
$w \ge 0$
$w \ge 6y+$ $3x-$ $18$
$w \le 6y$
$w \le 3x$
$0 \le x \le 6 ,$ $0 \le y \le 3$

This problem is now an LP which can be easily solved using GAMS. Solving the LP, we find that $x=6, y=2, Z=-24$

Applications

McCormick Envelopes can be applied when solving a variety of problems1,3,4:

• Process Network Problems
• Water Networks
• Pools and Blending
• Electricity Transmissions
• Any problem with bilinear terms

Conclusion

McCormick envelopes allow much easier computation of solution to complex non convex problems. By introducing convexity into the problems, a global minimum is created. This global minimum can be solved for as a lower bound to the original problem. By using the spatial branch and bound method, new lower bounds that are closer and closer to the true solution can be solved for. Using McCormick envelopes allows a solution to be found using less iterations of the branch and bound thereby using less computational power and lowering the time of computation. These envelopes have applications in any situation that has bilinear terms such as Chemical mixing or electrical transmission problems.

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. Lundell, Andreas. "On Convex Relaxations in Nonconvex Optimization." (2011): 403-12. Akademi University, 10 May 2011. Web. 6 June 2015. <http://users.abo.fi/alundell/files/ICheaP10.pdf>.
3. Gupte, Ashay. "MIXED INTEGER BILINEAR PROGRAMMING WITH APPLICATIONS TO THE POOLING PROBLEM." (n.d.): n. pag. Georgia Institute of Technology, Dec. 2012. Web. 6 June 2015. <https://smartech.gatech.edu/bitstream/handle/1853/45761/gupte_akshay_s_201212_phd.pdf>.
4. Namazifar, Mahti. "Convex Envelopes for Bounded Multilinear Functions." (2011): n. pag. University of Wisconsin Madison, 28 May 2009. Web. 6 June 2015. <http://www.cs.utep.edu/mceberio/Research/br-cpaior09/media/A2-namazifar-slides.pdf>.