Piecewise linearization of a product of continuous decision variables

[Thomas S.]

Hello everyone,

I am trying to reformulate a constraint that involves a product of two continuous (but bounded) decision variables.
So far, I found in H.P. Williams "Model building in mathematical programming" as well as the AIMMS Optimization Modelling book that a product, such as x_1 * x_2 can be reformulated:
x_1 * x_2 = y_1^2 - y_2^2,
where y_1 = (x_1+x_2)/2 and y_2 = (x_1-x_2)/2

I tried to piecewise linearize the quadratic terms, using SOS2 variables and a binary variables approach. When I only use one interval (two approximation nodes), GUROBI very quickly finds the optimal solution, but when I increase the number of node points, the problem becomes infeasible.

Has anybody faced similar problems or are there better ways to linearize such products? I also tried the McCormick envelopes and Taylor series, but the results are even worse than the linearization with only two node points.

Any help is highly appreciated.
Thomas

[Jakob Sch.]

Hi Thomas,

It looks like you already tried some techniques that can work for the type of problem of yours. Note that McCormick can also be refined (see http://minlp.cheme.cmu.edu/2014/papers/castro.pdf for example). Depending on where the term is occuring it might be possible to use SOCP constraints. Have you tried to directly linearize the bilinear term?

Best regards,
Jakob