Convertir la implicación en restricción lineal

Question

Tengo la siguiente restricción en lógica (simplificada):

$$\forall r \in R, t \in T: x_{rt} = 1 \implies t_a < r_p < t_b$$

Necesito linealizar esto. Lo que se me ha ocurrido es: \begin{align} x_{rt}t_a &< r_p \\ x_{rt}r_p &< t_b \end{align} Pero esto parece un poco chapucero. Aunque creo que debería funcionar, ¿hay alguna forma mejor de convertir mi restricción?

Necesito asignar reservas a las mesas. $R$ es la lista de reservas. $T$ es la lista de tablas. Obviamente, la cantidad de personas en la reserva tiene que ser menor que la cantidad máxima de asientos en una mesa y mayor que la cantidad mínima de asientos. $x_{rt}$ es el booleano que dice que la reserva $r$ se asigna a la tabla $t$ . $t_a$ es el mínimo de asientos en la mesa, $t_b$ es el máximo y $r_p$ es la cantidad de personas en la reserva. $t_a$ , $t_b$ y $r_p$ puede suponerse constante. $x_{rt}$ es una variable (y debe optimizarse).

Answer 1

Reformularé el problema a lo que creo que quieres, que no es lo que planteas en la formulación. Para simplificar, prescindiré de todos los subíndices excepto en las t.

En primer lugar, $r$ tiene que ser una variable de decisión (es decir, de optimización) en su formulación de optimización; no puede considerarse constante, o toda su formulación carece de sentido. En segundo lugar, todas las desigualdades deben ser no estrictas, es decir, $\le$ en lugar de $\lt$ .

Aunque se introduzcan estos cambios, su formulación propuesta es incorrecta. Si $x = 0$ sus limitaciones se convierten en $0 \le r$ y $0 \le t_b$ . No hay nada que obligue a $r$ a igual $0$ en este caso, que es uno de sus requisitos.

He aquí una formulación correcta: Añadir las restricciones $xt_a \le r$ y $r \le xt_b $ y x es binario.

Si $x = 1$ se convierte en $t_a \le r \le t_b$ .

Si $x = 0$ se convierte en $0 \le r \le 0$ . En otras palabras, $r = 0$ según sea necesario.