I am trying to solve a problem that involves constraints in which products of two decision variables appear. So far, I read that such products can be reformulated to a difference of two quadratic terms:

$x_1\cdot x_2=y_1^2-y_2^2$

Where $y_1 = 0.5 \cdot \left( x_1+x_2 \right)$ and $y_2 = 0.5 \cdot \left( x_1-x_2 \right)$

As stated in "Model building in mathematical programming" by H.P. Williams, I tried to linearize $y_1^2$ and $y_2^2$ by piecewise approximation. When I only use two node points (one interval) for the piecewise approximation, my solvers (Gurobi 5.6.3 and CPLEX 12.5.1) are able to solve the problem, but when I introduce more node points, both conclude that the problem becomes infeasible.

I already tried SOS2 variables as well as a binary approach for the linearization of $y_1^2$ and $y_2^2$.

I also used Taylor series to directly approximate $x_1\cdot x_2$ which resulted in similar results as the approximation using two node points. Since this method succeeded, I suppose that the rest of my model is feasible and only this product makes things complicated.

So my questions are:

  1. What can cause the infeasibility? I thought that adding more node points would be beneficial to the problem.
  2. Are there better ways to approximate such products? I have also experimented with a reformulation using logarithms, but this caused more computational effort and did not solve the infeasibility problem.
  • $\begingroup$ Are your decision variables of any specific type (continuous, integer, binary)? Do they have upper and/or lower bounds? $\endgroup$ – Axel Kemper Jun 19 '14 at 19:44
  • $\begingroup$ Both decision variables are continuous. They are also both bounded: $0\le x_1 \le 0.5$ and $20 \le x_2 \le 80$. I also tried to scale both to be between 1 and 2, but this did not help either. $\endgroup$ – Thomas Jun 20 '14 at 6:10

The AIMMS Modelling Guide in section 7.7 provides the following hint for bounded variables: enter image description here

  • $\begingroup$ Well, this is pretty much exactly what I did. As mentioned above, this works fine for me, when I only use 2 node points for approximating $y_1^2$ and $y_2^2$. But the problem does not solve any more, if I introduce more node points, attempting to approximate the parabolas better. $\endgroup$ – Thomas Jun 20 '14 at 9:29
  • $\begingroup$ And things don't improve if you make use of the bounds? $\endgroup$ – Axel Kemper Jun 20 '14 at 10:05
  • $\begingroup$ The above mentioned approximation with two points used these bounds. The larger valued node point represented the upper bound, the lower valued node point the lower bound. Since this approximation suffers from a large error between the real function and the approximation, I tried to introduce more node points (I used an equidistant grid), but as soon as I introduced even one more point, the problem became infeasible (according to CPLEX and GUROBI) $\endgroup$ – Thomas Jun 20 '14 at 11:39

Have a look at this paper. This article introduces 10 methods for your problem. on page 5, the authors introduce SOS procedure for bilinear terms.

  • $\begingroup$ All of these methods produce a MILP. The technique OP uses produces a linear program. Thus, this not only fails to address the original question, but it moves the optimization to a completely different computational paradigm. $\endgroup$ – Richard Apr 30 '19 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.