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
Then their product satisfies the four constraints:
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
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.
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
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
and so we have the valid inequality to get a lower bound on ϕxy:
This is a convex constraint in the three variables x, y, and ϕxy.
For more details, see .