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

 (1)

Then their product satisfies the four constraints:

These inequalities can be proved by looking at quadratic products. For example, we have

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

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

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

 (10)

Assume

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

The slope of the line is

and the intercept is

This gives

 (11)

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

 (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.