Linealización de un producto de dos variables de decisión

Question

Estoy tratando de resolver un problema que implica restricciones en las que aparecen productos de dos variables de decisión. Hasta ahora, he leído que dichos productos se pueden reformular a una diferencia de dos términos cuadráticos:

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

Dónde $y_1 = 0.5 \cdot \left( x_1+x_2 \right)$ y $y_2 = 0.5 \cdot \left( x_1-x_2 \right)$

Como se indica en "Model building in mathematical programming" de H.P. Williams, intenté linealizar $y_1^2$ y $y_2^2$ por aproximación a trozos. Cuando sólo utilizo dos puntos de nodo (un intervalo) para la aproximación a trozos, mis solucionadores (Gurobi 5.6.3 y CPLEX 12.5.1) son capaces de resolver el problema, pero cuando introduzco más puntos de nodo, ambos concluyen que el problema se vuelve inviable.

Ya he probado las variables SOS2 así como un enfoque binario para la linealización de $y_1^2$ y $y_2^2$ .

También he utilizado las series de Taylor para aproximar directamente $x_1\cdot x_2$ que dio resultados similares a la aproximación con dos puntos de nodo. Como este método tuvo éxito, supongo que el resto de mi modelo es factible y sólo este producto complica las cosas.

Así que mis preguntas son:

1. ¿Qué puede causar la inviabilidad? Pensé que añadir más puntos de nodo sería beneficioso para el problema.
2. ¿Existen mejores formas de aproximar estos productos? También he experimentado con una reformulación usando logaritmos, pero esto causó más esfuerzo computacional y no resolvió el problema de infeasibilidad.

Answer 1

El Guía de modelización AIMMS en la sección 7.7 proporciona la siguiente pista para las variables acotadas:

Answer 2

Echa un vistazo en este documento . Este artículo presenta 10 métodos para su problema. en la página 5, los autores introducen el procedimiento SOS para términos bilineales.