¿Cómo modelar las declaraciones iff y union en MILP?

Question

Estoy tratando de modelar $\{Ax\leq b\}\iff\{Bx\leq c\}$ . ¿Qué diferencia hay con $\{Ax\leq b\}\wedge\{Bx\leq c\}$ ?

1. Cómo modelar con variables binarias cuando $b$ y $c$ son $0$ vectores.

2. También estoy tratando de modelar $\{Ax\leq 0\}\cup\{Bx\leq 0\}$ .

Para modelar la unión si $b$ y $c$ fueron $non$ - $zero$ entonces basta con introducir variables binarias $z_1,z_2\in\{0,1\}$ e introducir los criterios:

1. $z_1+z_2=1$

2. $x_1$ es un vector tal que $Ax_1\leq bz_1$ y $x_1$ es un vector tal que $Bx_2\leq cz_2$ .

3. $x=x_1+x_2$ .

Si $b$ y/o $c$ son $0$ vectores entonces este truco falla.

¿Hay una forma mejor?

Answer 1

Para ver la diferencia mira un ejemplo. En $x=(x_1\:x_2)$ , $A=\begin{pmatrix} 1 & 0\\0 & 0\end{pmatrix}$ , $b=0$ , $B=\begin{pmatrix} 0 & 0\\0 & 1\end{pmatrix}$ , $c=0$ tienes

con la equivalencia a la izquierda y la conjunción a la derecha. Por lo tanto, en general $\{Ax\leq b\}\iff\{Bx\leq c\}$ no es convexo y no se puede modelar sin variables binarias.

Answer 2

He borrado mi primera respuesta porque era completamente errónea. (He negado incorrectamente una desigualdad vectorial).

Es posible acercarse al resultado deseado utilizando un conjunto de variables binarias, suponiendo que (a) el conjunto de variables factibles $x$ está acotado y (b) está dispuesto a ignorar algunas soluciones factibles. Esto último es necesario porque la negación de una desigualdad débil es una desigualdad fuerte, y los modelos PIM (y los solucionadores) aborrecen las desigualdades fuertes.

Dejemos que $m$ y $n$ sean las dimensiones de $b$ y $c$ respectivamente, dejemos que $M$ y $\epsilon$ sean constantes positivas suficientemente grandes y pequeñas (respectivamente), y que $z_1,\dots,z_m$ y $y_1,\dots,y_n$ sean variables binarias. Añade las restricciones $$b_i+\epsilon-M(1-z_i)\le (Ax)_i \le b_i + Mz_i\,(i=1,\dots,m)$$ y $$c_i+\epsilon-M(1-y_i)\le (Bx)_i\le c_i + My_i\, (i=1,\dots,n).$$ Observe que $z_i=0\implies (Ax)_i \le b_i$ y $z_i=1\implies (Ax)_i \ge b_i + \epsilon$ . Queda desterrada de la región factible cualquier solución en la que $b_i \lt (Ax)_i \lt b_i + \epsilon$ que es el coste de hacer negocios. Observaciones similares son válidas para el segundo conjunto de restricciones.

Para hacer cumplir $Ax\le b \iff Bx\le c$ necesitamos exigir que $\sum_{i=1}^m z_i \ge 1 \iff \sum_{j=1}^n y_j \ge 1$ . Hay varias formas de hacerlo, cambiando más restricciones por relajaciones (posiblemente) más estrictas. Una forma es añadir las restricciones $$n\sum_{i=1}^m z_i\ge \sum_{j=1}^n y_j$$ y $$m\sum_{j=1}^n y_j \ge \sum_{i=1}^m z_i.$$

He utilizado un único parámetro $\epsilon$ y un único parámetro $M$ pero es posible que desee buscar los valores adecuados fila por fila (especialmente para $M$ , ya que los valores más grandes de $M$ tenderá a debilitar las relajaciones).

Las disyunciones son más fáciles. Sólo se necesitan dos variables binarias ( $z_1$ y $z_2$ ), con las desigualdades $$Ax \le b + M_1z_1$$ y $$Bx \le c +M_2z_2.$$ Aquí $M_1$ y $M_2$ son vectores de valores constantes grandes. Para obtener su disyunción, necesita $z_1=0$ o $z_2=0$ (o ambos). Esto se puede aplicar mediante la restricción $z_1 + z_2 \le 1$ .