McCormick Cuts
John Mitchell

Products of variables can be replaced by new variables, with the new variables and old variables linked using linear constraints. These constraints can be tight, especially if at least one of the old variables is binary.

Assume the two variables x and y satisfy the bounds

lx ≤ x ≤ ux   and  ly ≤ y ≤ uy.
(1)

Then their product satisfies the four constraints:

xy  ≤   lyx + uxy -  lyux                               (2)
xy  ≤   lxy + uyx -  lxuy                               (3)
xy  ≥   lx + l y - l l                                (4)
        y     x     xy
xy  ≥   uyx + uxy - uxuy.                             (5)
These inequalities can be proved by looking at quadratic products. For example, we have
0 ≤  (x -  lx)(uy - y) =  - xy + uyx + lxy - lxuy

which can be rearranged to give (3).

A quadratic term xy in an optimization problem can be replaced by a new variables ϕxy with linear constraints

ϕxy   ≤  lyx + uxy - lyux                              (6)
ϕ     ≤  l y + u x - l u                               (7)
  xy      x     y     x y
ϕxy   ≥  lyx + lxy - lxly                               (8)
ϕxy   ≥  uyx + uxy -  uxuy.                            (9)
This is the convex envelope of ϕxy over the box given by (1); it is also known as the McCormick envelope [21].

When the variables are binary, the constraints become

ϕxy ≥ 0,ϕxy ≤  x,ϕxy ≤ y,ϕxy ≥ x +  y - 1.

The variable ϕxy is also binary and is given exactly by the constraints when x and y are binary. The linear programming relaxation may not be exact. For example, if x = y = 0.5 then the linear constraints only force 0 ϕxy 0.5.

A strengthening

If there are additional constraints on x and y, it may be possible to get a tighter convex envelope for ϕxy. For any scalar α, we have the equality

        2           2
(x +  αy)  = (x - αy)  + 4αxy.
(10)

Assume

αl ≤ x - αy ≤  αu

for any feasible x and y. We can construct a linear overestimator for (x - αy)2:

The slope of the line is

         α2 - α2
slope =  -u-----l=  αu + αl
         αu - αl

and the intercept is

              2
intercept  = α l - αl(αu + αl) = - αlαu.

This gives

(x - αy )2 ≤ (αl + αu )(x - αy ) - αlαu
(11)

and so we have the valid inequality to get a lower bound on ϕxy:

(x + αy )2 ≤ 4αϕxy + (αl + αu)(x - αy ) - αlαu.
(12)

This is a convex constraint in the three variables x, y, and ϕxy.

For more details, see [3].

References

[1]   F. A. Al-Khayyal and J. E. Falk. Jointly constrained biconvex programming. Mathematics of Operations Research, 8(2):273–286, 1983.

[2]   G. P. McCormick. Computability of global solutions to factorable nonconvex programs: part I — convex underestimating problems. Mathematical Programming, 10:147–175, 1976.

[3]   J. E. Mitchell, J.S. Pang, and B. Yu. Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs. Optimization Methods and Software, 29(1):120–136, 2014.