Linearize non-linear constraint (product of two continuous variables)

Question

I have a problem with linearizing a constraint because of the product of two continuous variables.

Suppose that the non-linear constraint is A = b + x1 x2 : A,x1,x2 are non-negative continuous variables.

How can I linearize this constraint?

I tried to reformulate it by creating two new continuous variables (y1 and y2) where y1 = 1/2 (x1 + x2) and y2= 1/2 (x1 - x2). In this case, the constraint also becomes non-linear.

What should I do?

Answer 1

There is no exact way to linearize w=x*y if x and y are continuous.

• The reformulation z1 = 1/2 (x + y) and z2 = 1/2 (x - y) gives w = z1^2 - z2^2. This is indeed still non-linear, but this is easier to handle when using a piecewise linear approximation.
• You can use McCormick envelopes (https://optimization.mccormick.northwestern.edu/index.php/McCormick_envelopes). But this gives just an approximation. To get more precision, split the range in segments.
• Sometimes (in special cases) a logarithmic transform can help.
• Some solvers can handle this quadratic expression directly.