Cortes fraccionales de Gomory, el poder de un buen corte

Imagen de Abby Savage extraída de Unsplash

El método de planos de corte (cutting planes) es un enfoque estructurado dentro de la optimización matemática diseñado para resolver problemas de Optimización Lineal Entera y Optimización Lineal Entera Mixta. Su funcionamiento se basa en resolver primero la relajación continua del problema original e incorporar iterativamente nuevas restricciones lineales (denominadas cortes) que reducen el espacio de búsqueda continuo sin eliminar ninguna solución entera factible.

Fundamentos e introducción histórica

Ralph E. Gomory introdujo las bases teóricas de esta técnica mediante dos desarrollos fundamentales:

Método de planos de corte fraccionales para Optimización Lineal Entera pura (Gomory, 1958).
Método de planos de corte para Optimización Lineal Entera Mixta (Gomory, 1960).

A continuación se presentará el primer método, que se aplica a problemas de optimización donde todas las variables deben ser enteras. Este algoritmo garantiza la convergencia hacia la solución óptima en un número finito de iteraciones. Para asegurar la integralidad de las variables de holgura y la validez matemática del proceso, es indispensable que tanto la matriz de coeficientes $\mathbf{A}$ como el vector de recursos $\mathbf{b}$ contengan únicamente valores enteros.

Cada corte añadido debe cumplir estrictamente dos condiciones:

Apartar de la nueva región factible a la solución óptima del problema al que se introduce el corte.
Satisfacer todas las soluciones enteras factibles del problema.

Para la construcción formal del corte, cualquier número real $a$ se descompone en dos componentes:

Parte entera $[a]$: Es el mayor número entero menor o igual a $a$.

Parte fraccional $f_a$: Es la diferencia $a - [a]$, siempre cumple $0 \leqslant f_a < 1$.

Por ejemplo:

Para $a = 4.67$: parte entera $4$, parte fraccional $0.67$.
Para $a = -3.58$: parte entera $-4$, parte fraccional $0.42$.

Deducción del corte fraccional de Gomory

Sea $\bar{\mathbf{x}}$ la solución óptima obtenida al resolver la relajación continua. Se define el conjunto

\[\mathcal{I}_f(\bar{\mathbf{x}}) = \{s \in \mathcal{I} : f_s > 0\}\]

como el grupo de índices asociados a las variables básicas cuyos valores no son enteros. Si $\bar{\mathbf{x}}$ es entera, entonces $\mathcal{I}_f(\bar{\mathbf{x}}) = \varnothing$ y el problema original estaría resuelto.

Para cualquier variable básica $x_s$ no entera presente en la tabla Símplex final, la ecuación de la fila correspondiente adopta la forma:

\[x_s + \sum_{j \in \mathcal{J}} y_{sj} x_j = \bar{x}_s\]

Al descomponer los coeficientes $y_{sj}$ y el término independiente $\bar{x}_s$ en sus respectivas partes enteras y fraccionales ($y_{sj} = [y_{sj}] + f_{sj}$ y $\bar{x}_s = [\bar{x}_s] + f_s$), se obtiene:

\[x_s + \sum_{j \in \mathcal{J}} \big([y_{sj}] + f_{sj}\big) x_j = [\bar{x}_s] + f_s\]

Separando las componentes enteras a la izquierda y las fraccionales a la derecha se obtiene:

\[x_s + \sum_{j \in \mathcal{J}} [y_{sj}] x_j - [\bar{x}_s] = f_s - \sum_{j \in \mathcal{J}} f_{sj} x_j\]

Dado que las variables en la solución entera factible deben tomar valores enteros, el lado izquierdo de la igualdad es necesariamente entero. En consecuencia, el lado derecho también debe serlo. Sabiendo que $0 < f_s < 1$ y que $f_{sj} \geqslant 0$, se deduce la siguiente relación:

\[f_s - \sum_{j \in \mathcal{J}} f_{sj} x_j \leqslant f_s < 1 \implies f_s - \sum_{j \in \mathcal{J}} f_{sj} x_j \leqslant 0\]

Reordenando la desigualdad se define la restricción del Corte Fraccional de Gomory:

\[\sum_{j \in \mathcal{J}} f_{sj} x_j \geqslant f_s \iff \sum_{j \in \mathcal{J}} -f_{sj} x_j \leqslant -f_s\]

En su forma estándar, agregando la variable de holgura entera $w_s$, se obtiene:

\[\sum_{j \in \mathcal{J}} -f_{sj} x_j + w_s = -f_s\]

Estructura del algoritmo fraccional de Gomory

El procedimiento algorítmico sigue una secuencia definida:

Resolver la relajación continua $P$ del problema entero original. Sea $\bar{\mathbf{x}}$ la solución obtenida.
Mientras exista alguna variable básica no entera ($\mathcal{I}_f(\bar{\mathbf{x}}) \neq \varnothing$):
- Seleccionar una variable de corte $x_s$ con $s \in \mathcal{I}_f(\bar{\mathbf{x}})$.
- Agregar a $P$ la restricción del corte: $\sum_{j \in \mathcal{J}} f_{sj}x_j \geqslant f_s$.
- Resolver el problema extendido $P$ aplicando el Algoritmo Dual del Símplex.
- Si el problema resultante no admite solución factible, se concluye que el problema entero original tampoco la tiene.
- Si admite solución, actualizar $\bar{\mathbf{x}}$ con la nueva solución de $P$.
Al alcanzar $\mathcal{I}_f(\bar{\mathbf{x}}) = \varnothing$, la solución $\mathbf{x} = \bar{\mathbf{x}}$ se declara como la solución óptima del problema entero.

Criterios para la selección de la variable de corte

Cuando existen múltiples variables básicas no enteras, la elección del corte no condiciona la convergencia final, pero sí influye en la velocidad del algoritmo. Seleccionar un corte más fuerte elimina una mayor porción del espacio de soluciones continuas. Existen dos reglas principales de selección:

Regla 1: Seleccionar $x_s$ tal que minimice la razón entre la suma de las partes fraccionales de la fila y la parte fraccional del término independiente: $\frac{\sum_{j \in \mathcal{J}} f_{sj}}{f_s} = \min_{i \in \mathcal{I}_f(\bar{\mathbf{x}})} \left\{ \frac{\sum_{j \in \mathcal{J}} f_{ij}}{f_i} \right\}$
Regla 2: Seleccionar $x_s$ cuya parte fraccional del término independiente sea máxima: $f_s = \max_{i \in \mathcal{I}_f(\bar{\mathbf{x}})} \{ f_i \}$

Ejemplo

Sea el siguiente problema de optimización entera:

\[\begin{align*} \min \quad & z = 4x_1 - 6x_2 \\ \text{s.a:} \quad & -x_1 + x_2 \leqslant 1 \\ & x_1 + 3x_2 \leqslant 9 \\ & 3x_1 + x_2 \leqslant 15 \\ & x_1, x_2 \geqslant 0 \\ & x_1, x_2 \in \mathbb{Z} \end{align*}\]

La representación gráfica con sus soluciones enteras es:

Si se resuelve el problema usando el Algoritmo del Símplex, la tabla final resultante es:

\[\begin{array}{rc|rrrrr|r} & & \textcolor{gray}{4} & \textcolor{gray}{-6} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \\ & & x_1 & x_2 & x_3^h & x_4^h & x_5^h & \\ \hline & z_j - c_j & 0 & 0 & -9/2 & -1/2 & 0 & -9 \\ \hline \textcolor{gray}{-6} & x_2 & 0 & 1 & 1/4 & 1/4 & 0 & 5/2 \\ \textcolor{gray}{4} & x_1 & 1 & 0 & -3/4 & 1/4 & 0 & 3/2 \\ \textcolor{gray}{0} & x_5^h & 0 & 0 & 2 & -1 & 1 & 8 \\ \hline \end{array}\]

obteniendo como solución óptima (de la relajación continua) el punto:

\[\mathbf{x}^* = (3/2,5/2,0,0,8)^\intercal \quad z^* = -9\]

Dado que la solución no es entera, se selecciona la variable $x_2$ para generar el corte. Con su parte fraccional $f_2 = 1/2$, la restricción fraccional asociada a las variables no básicas $x_3^h$ y $x_4^h$ resulta: $\frac{1}{4}x_3^h + \frac{1}{4}x_4^h \geqslant \frac{1}{2} \iff -\frac{1}{4}x_3^h - \frac{1}{4}x_4^h + x_6^h = -\frac{1}{2}$.

Al introducir este corte en el problema, se obtiene la tabla del Símplex:

\[\definecolor{maincolor2}{RGB}{21,182,184} \begin{array}{rc|rrrrrr|r} & & \textcolor{gray}{4} & \textcolor{gray}{-6} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \\ & & x_1 & x_2 & x_3^h & x_4^h & x_5^h & x_6^h & \\ \hline & z_j - c_j & 0 & 0 & -9/2 & -1/2 & 0 & 0 & -9 \\ \hline \textcolor{gray}{-6} & x_2 & 0 & 1 & 1/4 & 1/4 & 0 & 0 & 5/2 \\ \textcolor{gray}{4} & x_1 & 1 & 0 & -3/4 & 1/4 & 0 & 0 & 3/2 \\ \textcolor{gray}{0} & x_5^h & 0 & 0 & 2 & -1 & 1 & 0 & 8 \\ \textcolor{gray}{0} & x_6^h & 0 & 0 & -1/4 & \textcolor{maincolor2}{-1/4} & 0 & 1 & -1/2 \\ \hline \end{array}\]

y al iterar usando el Algoritmo Dual del Símplex, se obtiene la tabla:

\[\begin{array}{rc|rrrrrr|r} & & \textcolor{gray}{4} & \textcolor{gray}{-6} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \\ & & x_1 & x_2 & x_3^h & x_4^h & x_5^h & x_6^h & \\ \hline & z_j - c_j & 0 & 0 & -4 & 0 & 0 & -2 & -8 \\ \hline \textcolor{gray}{-6} & x_2 & 0 & 1 & 0 & 0 & 0 & 1 & 2 \\ \textcolor{gray}{4} & x_1 & 1 & 0 & -1 & 0 & 0 & 1 & 1 \\ \textcolor{gray}{0} & x_5^h & 0 & 0 & 3 & 0 & 1 & -4 & 10 \\ \textcolor{gray}{0} & x_4^h & 0 & 0 & 1 & 1 & 0 & -4 & 2 \\ \hline \end{array}\]

obteniendo en una sola iteración la solución óptima del problema entero:

\[\mathbf{x}^* = (1, 2, 0, 2, 10, 0)^\intercal \quad z^* = -8\]

Para interpretar este corte en el espacio de decisión original ($x_1, x_2$), se sustituyen las ecuaciones de las variables de holgura $x_3^h = 1 + x_1 - x_2$ y $x_4^h = 9 - x_1 - 3x_2$:

\[\frac{1}{4}(1 + x_1 - x_2) + \frac{1}{4}(9 - x_1 - 3x_2) \geqslant \frac{1}{2} \iff x_2 \leqslant 2\]

es decir, el corte fraccional de Gomory es equivalente a $x_2 \leqslant 2$.

Geométricamente, el corte en el problema original (variables $x_1$ y $x_2$) se representa en la siguiente figura:

donde se observa que se reduce el espacio de soluciones continuas sin eliminar ninguna solución entera.

En definitiva, los cortes fraccionales de Gomory demuestran la elegancia de la investigación operativa: esculpir el espacio continuo con precisión quirúrgica para acorralar la solución entera sin perder un solo punto factible en el camino.

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