McCormick envelopes

From optimization
Revision as of 16:44, 24 May 2015 by Dombrowskijd (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.

Contents

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}

Section 1.2

Section 2

Section 3