# McCormick envelopes

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

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

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.

# Overview

In his original paper, McCormick

## Derivation for bilinear term

$w=xy$
$x^{L}\le x\le x^{U}$ $y^{L}\le y\le y^{U}$
$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}$