¿Cómo linealizar un problema min-max que incluye una variable y parámetros?

Question

Cómo linealizar el siguiente modelo:

$\min\limits_{x,y}$ $\max\limits_{i \in \{1, ..., m\}}(|x-a_i| +b_i)$

s.t. x $\geq$ 0, y $\geq$ 0

donde x es una variable y $a_i$ y $b_i$ son parámetros

Sé que puedo reescribir la función objetivo a

$\min\limits_{x,y}$ $\max\limits_{i \in \{1, ..., m\}}$ $z(x-a_i) + (1-z)(a_i-x) + b_i$

con el siguiente nuevo conjunto de restricciones:

s.t. x $\geq$ 0, y $\geq$ 0, $z \in \{0,1\}$

¿Ya he terminado con la linealización, o debo seguir adelante? Si es así, ¿cómo?

Answer 1

No has terminado con la linealización, tienes algo cuadrático. Además, te faltan algunas restricciones en $z$ que te diría que es igual a $1$ si $x-a_i$ es positivo. Pero hay una forma más sencilla de hacerlo...

Se puede resolver el problema equivalente

$\min\limits_{x,y,t} t $ donde la variable $t \in \mathbb{R}$

con limitaciones

$\forall i \in \{1,..,m\}, x-a_i+b_i \leq t$

$\forall i \in \{1,..,m\}, a_i-x+b_i \leq t$

Y las limitaciones adicionales que tenías antes.

Esto es lineal, y $t$ será igual a $\max\limits_i (|x-a_i|+b_i)$

Rq : siempre es posible hacer algo así cuando se tiene un $\max$ o un valor absoluto (que es una especie de máximo) en la función de costes. Es más difícil cuando el $\max$ está en las limitaciones, sin embargo.