Linearization of a product of two decision variables

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.
• Are your decision variables of any specific type (continuous, integer, binary)? Do they have upper and/or lower bounds? – Axel Kemper Jun 19 '14 at 19:44
• 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. – Thomas Jun 20 '14 at 6:10

• 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. – Thomas Jun 20 '14 at 9:29