Modelando decisiones con variables binarias

Imagen de Yannis Papanastasopoulos extraída de Unsplash

Se va a presentar a continuación una de las herramientas más potentes dentro del modelado de problemas de optimización matemática: el uso de variables binarias.

En los problemas puros de optimización lineal entera (Integer Linear Optimization), todas las variables deben tomar valores enteros, pero existe un subgrupo importantísimo conocido como problemas binarios (Binary Linear Optimization), donde las variables sólo pueden tomar los valores $0$ o $1$. Este enfoque no sólo sirve para decidir “sí o no”, sino que es la clave para traducir condiciones lógicas complejas a restricciones matemáticas que mantengan lineal el modelo matemático.

Modelando Relaciones Frecuentes

El verdadero arte de la optimización matemática surge cuando necesitamos representar relaciones lógicas más complejas. A continuación, veremos cómo linealizarlas.

Condiciones Disyuntivas (Condiciones “O”)

En ocasiones, una solución debe satisfacer una restricción u otra, aunque también puede ocurrir que se cumplan ambas. Estas condiciones se conocen como restricciones disyuntivas.

Por ejemplo, imaginemos un problema de la mochila en el que queremos imponer la siguiente condición: o bien escogemos los objetos 2 y 3 juntos, o bien escogemos el objeto 5 (pudiendo darse ambas situaciones a la vez).

Sea $x_j$ una variable binaria que toma el valor $1$ si seleccionamos el objeto $j$ y $0$ en caso contrario. La condición puede expresarse lógicamente como:

\[(x_2 + x_3 \geqslant 2) \lor (x_5 \geqslant 1)\]

Para incorporar esta condición al modelo introducimos una variable binaria auxiliar $\delta$, llevando toda la información de cada restricción inicial a un lado de la desigualdad y dejando la variable binaria (o su complementaria) multiplicando a una constante suficientemente grande.

En este caso podemos escribir:

\[2-x_2-x_3 \leqslant M_1(1-\delta)\] \[1-x_5 \leqslant M_2\delta\]

donde $M_1=2$ y $M_2=1$ son las menores cotas válidas para este problema. En una formulación con valores M, no conviene utilizar arbitrariamente valores grandes: lo adecuado es utilizar la menor cota válida que permita relajar completamente la restricción cuando esta no debe estar activa. Esto evita introducir una formulación innecesariamente débil y puede facilitar el trabajo del optimizador.

La variable $\delta$ determina cuál de las dos condiciones se fuerza, aunque la otra también puede cumplirse:

Si $\delta=1$, la primera restricción queda $2-x_2-x_3\leqslant 0$, por lo que necesariamente $x_2=x_3=1$. La segunda restricción queda relajada.
Si $\delta=0$, la segunda restricción queda $1-x_5\leqslant 0$, por lo que necesariamente $x_5=1$. La primera restricción queda relajada.

Por tanto, la variable auxiliar permite transformar una condición lógica del tipo A o B en un conjunto de restricciones lineales.

Implicaciones Simples (Condiciones “Si … entonces …”)

Otra situación habitual aparece cuando una decisión obliga a tomar otra. Por ejemplo, si seleccionamos los objetos 1, 2 y 3, entonces debemos seleccionar también los objetos 4 y 5.

Si $x_j$ indica si seleccionamos el objeto $j$, esta condición puede expresarse lógicamente como:

\[x_1+x_2+x_3 \geqslant 3 \Rightarrow x_4+x_5\geqslant 2\]

Una implicación del tipo si A entonces B equivale a no A o B, es decir, se puede usar el procedimiento anterior para modelar una implicación. En el ejemplo anterior, la implicación equivale a:

\[x_1+x_2+x_3 \leqslant 2 \lor x_4+x_5\geqslant 2\]

y su modelización resultante es:

$x_1 + x_2 + x_3 - 2 \leqslant M_1 (1 - \delta)$, donde $M_1 = 1$.
$2 - x_4 - x_5 \leqslant M_2 \delta$, donde $M_2 = 2$.

En este caso, los valores de $M_1$ y $M_2$ se pueden determinar directamente a partir de las cotas de las variables. Como $x_1,x_2,x_3$ son binarias, $x_1+x_2+x_3-2$ puede tomar como máximo el valor $1$, por lo que $M_1=1$ es suficiente. Del mismo modo, $2-x_4-x_5$ puede tomar como máximo el valor $2$, por lo que $M_2=2$ es suficiente.

Cuando las implicaciones involucran únicamente variables binarias, muchas de estas relaciones pueden modelarse directamente mediante desigualdades sencillas. Las cuatro posibilidades básicas y su correspondiente modelización son:

\[\begin{array}{c|c} x_j=0 \Rightarrow x_i=0 & x_j=0 \Rightarrow x_i=1 \\ x_i \leqslant x_j & x_i \geqslant 1-x_j \\ \hline\hline x_j=1 \Rightarrow x_i=0 & x_j=1 \Rightarrow x_i=1 \\ x_i \leqslant 1-x_j & x_i \geqslant x_j \end{array}\]

Por ejemplo, si queremos expresar si no seleccionamos el objeto 4, no podemos seleccionar el objeto 7, la condición lógica es:

\[x_4=0 \Rightarrow x_7=0\]

que se puede modelar simplemente como:

\[x_7 \leqslant x_4\]

La idea general es que las variables binarias permiten representar decisiones lógicas mediante restricciones lineales. Esto resulta especialmente útil para expresar condiciones del tipo “si … entonces …“, “o bien … o bien …” y otras relaciones entre decisiones.

Costes fijos

En muchos problemas de optimización, utilizar un recurso implica pagar un coste fijo, independientemente de la cantidad utilizada, además de un coste variable que depende de dicha cantidad.

Por ejemplo, imaginemos que queremos comprar un determinado producto. Sea $x$ la cantidad comprada, con un coste de $c$ euros por unidad. Además, el proveedor cobra un coste fijo $f>0$ cada vez que realizamos un pedido. En ese caso, el coste total no es simplemente proporcional a la cantidad comprada:

\[C(x) = \begin{cases} 0 & \text{si } x=0,\\ f+cx & \text{si } x>0. \end{cases}\]

El problema es que esta función es discontinua en $x=0$, y este tipo de comportamiento no se puede representar directamente con una función lineal. Una forma habitual de modelarlo es introducir una variable binaria $y$ que indique si se realiza o no el pedido:

\[y = \begin{cases} 1 & \text{si se realiza el pedido},\\ 0 & \text{si no se realiza el pedido}. \end{cases}\]

Podemos entonces escribir el coste como:

\[\min \; z = fy + cx\]

y añadir la restricción :

\[x \leqslant My\]

donde $M$ es una cota superior válida para la cantidad que podemos comprar.

Esta restricción es la que establece el vínculo entre las dos variables:

Si $y=0$, entonces $x \leqslant 0$ y, como $x \geqslant 0$, necesariamente $x=0$. No se realiza el pedido y no se paga el coste fijo.
Si $y=1$, podemos tener $x>0$. En ese caso, en la función objetivo aparece $f+cx$: pagamos tanto el coste fijo como el coste variable.

Por tanto, el modelo completo queda:

\[\begin{align*} \min \quad & z = fy + cx\\ \text{s.a:}\quad & x \leqslant My\\ & x \geqslant 0\\ & y\in\{0,1\} \end{align*}\]

La idea importante es que la variable binaria permite representar la decisión de activar o no una determinada actividad, mientras que la variable continua representa la cantidad asociada a esa actividad.

Este patrón aparece constantemente en modelos de optimización. Siempre que una decisión implique un coste fijo por el hecho de activar, utilizar, abrir, contratar, instalar o realizar algo, podemos introducir una variable binaria que represente esa decisión y vincularla con la cantidad correspondiente mediante una restricción del tipo

\[x \leqslant My\]

Así, una función de coste discontinua puede incorporarse a un modelo lineal mediante una variable binaria.

Linealización de Productos de Variables

Los productos de variables hacen que una función o una restricción deje de ser lineal. Sin embargo, cuando intervienen variables binarias, estos productos pueden transformarse en relaciones lineales introduciendo una variable auxiliar.

La idea consiste en sustituir el producto por una nueva variable y añadir restricciones que garanticen que dicha variable toma exactamente el valor del producto.

Producto de dos variables binarias

Supongamos que tenemos dos decisiones binarias $\beta_1$ y $\beta_2$ y queremos representar si ambas decisiones se toman simultáneamente. Definimos una nueva variable binaria $\delta$ como:

\[\delta = \beta_1\beta_2\]

Como $\beta_1$ y $\beta_2$ sólo pueden tomar los valores $0$ y $1$, el producto $\delta$ vale $1$ únicamente cuando ambas variables valen $1$. Podemos eliminar el producto y sustituirlo por las siguientes restricciones lineales:

$\delta \leqslant \beta_1$
$\delta \leqslant \beta_2$
$\beta_1+\beta_2-\delta \leqslant 1$

Estas restricciones garantizan que:

Si $\beta_1=0$ o $\beta_2=0$, entonces $\delta=0$.
Si $\beta_1=\beta_2=1$, entonces $\delta=1$.

Por tanto, podemos utilizar $\delta$ en el resto del modelo como sustituto del producto $\beta_1\beta_2$.

Conviene matizar que linealizar un producto no siempre es la mejor opción. La linealización introduce una nueva variable y varias restricciones adicionales, lo que puede aumentar considerablemente el tamaño y la complejidad del modelo.

Por ello, antes de introducir una variable auxiliar para representar un producto, es recomendable comprobar si existe una formulación equivalente más sencilla que permita expresar directamente la misma relación aprovechando las demás restricciones del problema.

La linealización resulta especialmente útil cuando el producto aparece explícitamente en la función objetivo o en alguna restricción y no existe una forma sencilla de reformularlo mediante las variables que ya forman parte del modelo. En cambio, si las variables que intervienen en el producto ya están relacionadas mediante otras restricciones, puede ser posible aprovechar esas relaciones y evitar la introducción de nuevas variables y restricciones.

Producto de una variable binaria y una continua

La misma idea anterior puede utilizarse cuando multiplicamos una variable binaria por una variable continua no negativa. Por ejemplo, supongamos que $x \geqslant 0$ representa una cantidad y $\beta$ indica si una determinada actividad está activa. Si queremos que la cantidad relevante para el modelo sea $x$ únicamente cuando $\beta=1$, podemos definir:

\[\delta = x\beta\]

El problema es que el producto $x\beta$ no es lineal. Para linealizarlo, necesitamos conocer una cota superior para $x$. Supongamos que:

\[0\leqslant x\leqslant M\]

donde $M$ es una cota superior válida para $x$. Podemos utilizar las siguientes restricciones:

$\delta \leqslant x$
$\delta \leqslant M\beta$
$\delta \geqslant x-M(1-\beta)$
$\delta \geqslant 0$

Estas son las conocidas condiciones de Fortet (Fortet, 1960) para este caso. De este modo:

Si $\beta=0$, las restricciones fuerzan $\delta=0$, independientemente del valor de $x$.
Si $\beta=1$, las restricciones fuerzan $\delta=x$.

Por tanto, en ambos casos se cumple:

\[\delta=x\beta\]

La idea general es que, cuando aparece un producto de variables que rompe la linealidad, podemos introducir una variable auxiliar que represente dicho producto y añadir restricciones lineales que garanticen la equivalencia.

Este procedimiento permite transformar determinados términos no lineales en un conjunto de restricciones lineales y es una de las técnicas más habituales para construir modelos de optimización lineal entera mixta.

Dominar la formulación mediante variables binarias es lo que convierte a la optimización matemática en una herramienta versátil capaz de abordar decisiones estratégicas del mundo real.

¿Quieres seguir explorando el mundo de la Investigación Operativa? Descubre más posts sobre el tema aquí.