De la optimización continua a la optimización entera, el poder de las variables enteras

Imagen de Fernando Santander extraída de Unsplash

La optimización lineal continua es uno de los mayores éxitos de la optimización matemática. Desde su desarrollo a mediados del siglo XX ha permitido resolver problemas de asignación de recursos, planificación de la producción, transporte o logística con millones de variables y restricciones. Sin embargo, existe una limitación fundamental: el mundo real no siempre es continuo.

No podemos construir 3,7 hospitales, contratar 2,4 trabajadores o abrir 5,6 fábricas. En muchos problemas las decisiones son, por naturaleza, discretas. Además, hay un tipo particular de decisiones, que son binarias, es decir, un proyecto se ejecuta o no, una máquina se compra o no, un vehículo realiza una ruta o no.

La optimización entera surge precisamente para modelar este tipo de decisiones. A primera vista parece una modificación mínima de la optimización lineal continua: basta con exigir que algunas variables tomen valores enteros, o de forma particular, binarios. Sin embargo, esa pequeña condición transforma por completo la estructura matemática del problema y explica por qué la optimización entera constituye uno de los mayores retos de la optimización.

Los orígenes de la optimización lineal entera

Los primeros desarrollos de la optimización lineal aparecen en la década de 1930 con los trabajos de Leonid Kantorovich, aunque fue tras la Segunda Guerra Mundial cuando George Dantzig revolucionó el campo con el desarrollo del Método Símplex.

Sin embargo, pronto quedó claro que muchos problemas prácticos no podían representarse adecuadamente mediante variables continuas. Las decisiones relacionadas con la selección, asignación o localización suelen tener una naturaleza discreta: una instalación se construye o no, un vehículo se utiliza o no, y una máquina se compra o no.

Durante la década de 1950 comenzaron a desarrollarse métodos específicamente orientados a resolver este tipo de problemas. Entre los primeros hitos destacan los trabajos de Ralph Gomory (1958, 1960) (Gomory, 1958; Gomory, 1960), quien desarrolló algoritmos basados en planos de corte (cutting planes) para obtener soluciones enteras a partir del problema continuo, y los de Ailsa H. Land y Alison G. Doig (1960) (Land & Doig, 1960), quienes en 1960 publicaron un procedimiento de resolución de problemas de programación discreta que constituye el pilar fundamental de los métodos de Ramificación y Acotación (Branch and Bound).

Estos enfoques introdujeron dos ideas que siguen siendo fundamentales en los optimizadores actuales: utilizar la relajación continua para obtener información sobre el problema entero y reducir progresivamente el espacio de búsqueda mediante cotas y restricciones adicionales.

El problema lineal continuo puede escribirse como

\[\begin{aligned} \min \quad & z = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.a:} \quad & \mathbf{Ax} \leqslant \mathbf{b}, \\ & \mathbf{x} \geqslant \mathbf{0}. \end{aligned}\]

Una de sus propiedades más importantes es geométrica: el conjunto factible es un poliedro convexo. Esta convexidad proporciona propiedades matemáticas muy buenas:

el óptimo siempre puede encontrarse en un vértice.
existen algoritmos muy eficientes.
la teoría de la dualidad permite obtener cotas y garantías de optimalidad.
pequeñas modificaciones del problema pueden analizarse mediante análisis de sensibilidad.

Parecía que la optimización estaba prácticamente resuelta… hasta que aparecieron las variables enteras. Imaginemos que queremos decidir cuántos camiones comprar. La optimización lineal continua puede devolver una solución como $x = 7.42$. Desde el punto de vista matemático la solución es perfectamente válida. Desde el punto de vista práctico, no. La solución natural parece evidente:

“Resolvamos el problema continuo y redondeemos la solución.”

Sin embargo, esta idea casi nunca funciona.

¿Por qué no basta con redondear?

La primera idea que podría surgir al obtener una solución fraccional del problema continuo es simplemente redondearla. Sin embargo, el redondeo no garantiza ni siquiera que obtengamos una solución factible y, aunque la obtengamos, tampoco garantiza que sea óptima. El problema continuo del problema entero se denomina relajación continua.

El redondeo puede producir soluciones infactibles.

Consideremos el siguiente problema entero:
\[\begin{aligned} \min \quad & z = -x_1-x_2 \\ \text{s.a:} \quad & -2x_1+2x_2 \leqslant 1, \\ & 16x_1-14x_2 \leqslant 7, \\ & x_1,x_2 \geqslant 0, \textrm{ enteras}. \end{aligned}\]
Si eliminamos temporalmente la condición de integralidad y resolvemos la relajación continua, obtenemos la solución
\[(x_1,x_2)=(7,7.5)\]
Esta solución es perfectamente válida para el problema continuo, pero no para el problema entero, ya que $x_2$ no es un número entero.

Podríamos intentar redondear la solución. Dependiendo de la dirección del redondeo, obtendríamos $(7,7)$ o $(7,8)$.

Sin embargo, ninguna de las dos soluciones es factible. Para $(7,7)$ se viola la segunda restricción $14\nleqslant7$. Para $(7,8)$ se viola la primera restricción $2\nleqslant 1$.

La solución óptima del problema entero es, en cambio, $(x_1,x_2)=(3,3)$.

La siguiente figura representa geométricamente este ejemplo. En ella puede observarse la región factible de la relajación continua, la solución fraccional $(7,7.5)$ y los puntos enteros obtenidos mediante redondeo, que son infactibles, además de las soluciones enteras del problema.

Por tanto, el redondeo no sólo puede alejarnos de la solución óptima: puede producir una solución que ni siquiera sea admisible.

El redondeo puede producir una solución factible pero subóptima.

Podríamos pensar entonces que basta con redondear de alguna manera que preserve la factibilidad. Pero esto tampoco resuelve el problema: una solución redondeada puede ser factible y, aun así, estar lejos del óptimo entero.

Consideremos el siguiente problema:
\[\begin{aligned} \max \quad & z=8x_1+7x_2 \\ \text{s.a:} \quad & 5x_1+4x_2\leqslant 6, \\ & 0\leqslant x_1,x_2\leqslant1, \\ & x_1,x_2\in\mathbb{Z}. \end{aligned}\]
que puede escribirse también como (expresando las variables binarias explícitamente):
\[\begin{aligned} \max \quad & z=8x_1+7x_2 \\ \text{s.a:} \quad & 5x_1+4x_2\leqslant 6, \\ & x_1,x_2 \in \{0,1\} \end{aligned}\]
Como las variables son binarias, las únicas soluciones enteras posibles son
\[(0,0) \quad (1,0) \quad(0,1) \quad(1,1)\]
La solución $(1,1)$ no es factible, ya que viola la primera restricción $9 \nleqslant 6$. Las otras soluciones tienen los siguientes valores de la función objetivo:
\[\begin{array}{c|c}(x_1,x_2) & z \\ \hline (0,0) & 0\\ (1,0) & 8\\ (0,1) & 7 \end{array}\]
Por tanto, la solución óptima entera es $(x_1,x_2)=(1,0)$ con $z_I=8$.

Veamos ahora qué ocurre si eliminamos la condición de integralidad. El problema a resolver es:
\[\begin{aligned} \max \quad & z=8x_1+7x_2 \\ \text{s.a:} \quad & 5x_1+4x_2\leqslant6, \\ & 0\leqslant x_1,x_2\leqslant 1 \end{aligned}\]
En este caso, la solución óptima es $(x_1,x_2)=(0.4,1)$ con valor $z_C=10.2$.

Si ahora aplicamos un redondeo convencional, obtenemos que la solución $(0.4,1)$ se redondea a $(0,1)$. Esta solución sí es factible para el problema entero y tiene valor $z=7$.

Sin embargo, acabamos de comprobar que existe otra solución entera factible, $(1,0)$ cuyo valor es $z=8$. Por tanto, el redondeo nos ha proporcionado una solución factible, pero no óptima.

Este ejemplo muestra una diferencia fundamental entre ambos problemas. La relajación continua nos proporciona una solución fraccional que puede ser muy útil para obtener información y cotas, pero no existe una regla general que nos permita transformar esa solución mediante redondeo en el óptimo entero.

En otras palabras, el problema no consiste únicamente en “eliminar los decimales”. Hay que encontrar la mejor combinación discreta posible y, además, poder demostrar que ninguna otra combinación es mejor.

La relajación continua

Para entender cómo se resuelve la optimización entera conviene definir un concepto fundamental del que se ha hablado previamente: la relajación continua.

Supongamos un problema entero

\[\begin{aligned} \min \quad & z_I=\mathbf{c}^\intercal \mathbf{x} \\ \text{s.a:} \quad & \mathbf{Ax} \leqslant \mathbf{b},\\ & \mathbf{x} \in \mathbb{Z}^n \end{aligned}\]

Su relajación continua consiste simplemente en eliminar la restricción de integralidad:

\[\begin{aligned} \min \quad & z_C = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.a:} \quad & \mathbf{Ax} \leqslant \mathbf{b} \end{aligned}\]

Geométricamente, esto significa que dejamos de considerar únicamente los puntos enteros del poliedro y permitimos cualquier punto de su región factible.

La relajación continua suele ser mucho más fácil de resolver y proporciona una información muy valiosa:

ofrece una cota para el problema entero.
permite detectar rápidamente soluciones imposibles.
permite medir cuánto se separa la solución continua de la solución entera.
constituye una pieza fundamental de los principales algoritmos modernos de optimización entera.

Por ejemplo, en un problema de maximización, si la relajación continua proporciona un valor

\[z_C=120\]

mientras que la mejor solución entera conocida tiene valor

\[z_I=100\]

existe una diferencia de 20 unidades entre ambas soluciones. Una forma habitual de expresar esta diferencia de manera relativa es

\[\text{gap}=\frac{|z_C-z_I|}{|z_I|} \cdot 100\]

En este caso, $\text{gap}=\frac{|120-100|}{|100|}\cdot 100=20\%$

Cuanto más cercana esté la relajación continua al problema entero, más información útil proporciona como aproximación del valor óptimo. Por el contrario, una brecha o gap grande indica que la relajación deja una región considerable entre la solución continua y las soluciones enteras, haciendo potencialmente más difícil el proceso de resolución.

Paradójicamente, la optimización lineal continua sigue siendo la herramienta principal para resolver optimización entera.

Una pequeña restricción que lo cambia todo

A simple vista, la única diferencia entre ambos modelos parece ser una línea adicional:

\[\mathbf{x} \in \mathbb{Z}^n\]

Sin embargo, esa restricción modifica completamente la estructura del problema. En optimización lineal continua trabajamos sobre un conjunto convexo:

\[\mathcal{S}=\{\mathbf{x} : \mathbf{Ax} \leqslant \mathbf{b} \}\]

En optimización entera únicamente interesan los puntos

\[\mathcal{S} \cap \mathbb{Z}^n\]

es decir, el poliedro definido por las restricciones sigue siendo convexo, pero al restringirnos a sus puntos enteros, el conjunto de soluciones factibles deja de ser, en general, convexo. El problema pasa de ser continuo a convertirse en un problema combinatorio.

¿Por qué la optimización entera es más difícil?

La diferencia fundamental no reside en que existan variables enteras, la diferencia es que el espacio de búsqueda cambia completamente.

En optimización lineal continua buscamos el mejor punto dentro de un conjunto convexo.
En el caso entero debemos decidir cuál de los, quizá millones de puntos enteros posibles, es el óptimo.

Por este motivo, muchos problemas de optimización entera son computacionalmente difíciles y están relacionados con problemas de la clase $\mathcal{NP}$-difíciles. Para estos problemas no se conocen algoritmos que garanticen resolver todos los casos en tiempo polinomial.

Es posible resolver problemas lineales continuos con millones de variables de forma muy eficiente, mientras que problemas enteros mucho más pequeños pueden resultar computacionalmente muy difíciles. Incluso un modelo con unas pocas centenas de variables binarias puede, en determinadas formulaciones, requerir horas o incluso días de cálculo.

¿Cómo se resuelven estos problemas?

La respuesta es: resolviendo muchos problemas continuos.

Los algoritmos modernos, como Ramificación y Acotación (Branch and Bound), Planos de Corte (Cutting Planes) o Ramificación y corte (Branch and Cut), utilizan continuamente la relajación continua para obtener cotas, descartar regiones del espacio de búsqueda y acercarse progresivamente a la solución óptima.

En cierto sentido, la optimización lineal continua no desaparece con la optimización entera, sino que se convierte en su principal aliada.

La optimización entera suele presentarse como una simple extensión de la optimización lineal continua. Desde el punto de vista de la formulación esto es cierto: basta con añadir la condición de integralidad. Sin embargo, desde el punto de vista matemático y computacional, el cambio es mucho más profundo: aunque el poliedro definido por las restricciones sigue siendo convexo, al restringirnos a sus puntos enteros el conjunto de soluciones factibles deja de ser, en general, convexo. Aparecen dificultades combinatorias y desaparecen muchas de las propiedades que hacían tan eficientes los procedimientos de resolución en optimización lineal continua.

Precisamente por ello, la optimización entera ha impulsado algunos de los desarrollos más importantes de la optimización moderna y continúa siendo una herramienta imprescindible para modelar problemas reales de logística, energía, telecomunicaciones, finanzas, planificación…

Al fin y al cabo, no todo puede ser continuo: muchas de las decisiones que tomamos sólo admiten opciones concretas.

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