Cuando las variables se mezclan: cortes mixtos de Gomory

Imagen de Vicky Nguyen extraída de Unsplash

En Optimización Lineal Entera Mixta es habitual encontrar problemas donde conviven decisiones discretas (variables enteras o binarias) y decisiones continuas (cantidades de flujo, capacidades continuas…). Al resolver la relajación continua de un problema lineal entero mixto mediante el Algoritmo del Símplex, se eliminan temporalmente las condiciones de integralidad. Si la solución resultante no es entera en las variables que lo requieren, se debe recurrir a algoritmos como Ramificación y Acotación o a los Métodos de Planos de Corte.

Sin embargo, cuando intentamos aplicar directamente el corte fraccional de Gomory (diseñado originalmente para problemas enteros puros), nos encontramos con un obstáculo matemático fundamental.

Cuando se introducen variables continuas

Si la fila de la tabla del Símplex contiene al menos una variable no básica $x_j$ que es continua (\(x_j \geqslant 0\), sin restricción de integralidad), la justificación del corte fraccional puro se desmorona por tres razones esenciales:

1. Pérdida de la propiedad modular: Una variable continua $x_j$ no salta de entero en entero, puede tomar cualquier valor real no negativo (como por ejemplo \(x_j = 0.001\)). Por tanto, la suma ya no está acotada por saltos discretos módulo 1.
2. Absorción continua de la fracción: Una pequeña variación en la variable continua $x_j$ puede cambiar el valor del lado izquierdo de forma continua, “absorbiendo” la fracción \(f_s\) sin forzar a las variables enteras a modificar su valor.
3. Invalidez de las partes fraccionales de los coeficientes: Descomponer el coeficiente $\bar{y}_{ij}$ de una variable continua en \(\lfloor \bar{y}_{ij} \rfloor + f_{ij}\) carece de sentido algebraico para acotar el problema, ya que \(f_{ij} x_j\) no genera valores discretos cuando \(x_j\) es continua. Si se forzara el corte fraccional puro sobre variables continuas, se eliminarían soluciones factibles del problema original, violando la condición de validez de un corte.

El siguiente ejemplo ilustra este último hecho.

\[\begin{align*} \min \quad & z = 3x_1 + 2x_2 + x_3 \\ \text{s.a:} \quad & x_1 + 2x_2 - x_3 = 6 \\ & 2x_1 - 2x_2 + 2x_3 = 5 \\ & x_1, x_2, x_3 \geqslant 0 \\ & x_2 \text{ entera} \end{align*}\]

La tabla final del Símplex para la relajación continua es:

\[\begin{array}{rc|rrr|r} & & \color{gray}{3} & \color{gray}{2} & \color{gray}{1} & \\ & & x_1 & x_2 & x_3 & \\ \hline & z_j - c_j & 0 & 0 & -4/5 & 62/5 \\ \hline \color{gray}{3} & x_1 & 1 & 0 & 3/5 & 16/5 \\ \color{gray}{2} & x_2 & 0 & 1 & -4/5 & 7/5 \\ \hline \end{array}\]

que, al introducir el plano de corte fraccional de Gomory

\[\frac{1}{5} x_3 \geqslant \frac{2}{5}\]

se obtiene la tabla:

\[\begin{array}{rc|rrrr|r} & & \color{gray}{3} & \color{gray}{2} & \color{gray}{1} & \color{gray}{0} & \\ & & x_1 & x_2 & x_3 & x_4^h & \\ \hline & z_j - c_j & 0 & 0 & 0 & -4 & 14 \\ \hline \color{gray}{3} & x_1 & 1 & 0 & 0 & 3 & 2 \\ \color{gray}{2} & x_2 & 0 & 1 & 0 & -4 & 3 \\ \color{gray}{1} & x_3 & 0 & 0 & 1 & -5 & 2 \\ \hline \end{array}\]

obteniendo la solución: \(\bar{\mathbf{x}} = (2,3,2,0)^\intercal\) con \(z^* = 14\) ya que el corte introducido fuerza que $x_3 \geqslant 2$. Sin embargo, la solución óptima del problema es: \(\mathbf{x}^* = (11/4, 2, 3/4, 0)^\intercal\) con \(z^* = 13\). Se puede observar que $x_3$ en la solución óptima toma un valor inferior a $2$, contradiciendo la condición impuesta por el corte fraccional de Gomory.

Justificación y deducción del corte de Gomory mixto

Para la obtención del corte mixto de Gomory (Gomory, 1960) es necesario introducir cierta notación. En primer lugar se divide el conjunto de variables $\mathcal{I}$ en sus variables continuas $\mathcal{I}^1$ y enteras $\mathcal{I}^2$, permitiendo introducir los conjuntos

• $$\mathcal{I}_f^1 (\bar{\mathbf{x}}) = \{s \in \mathcal{I}: f_s > 0, x_s \text{ continua}\}$$
• $$\mathcal{I}_f^2 (\bar{\mathbf{x}}) = \{s \in \mathcal{I}: f_s > 0, x_s \text{ entera}\}$$
• $$\mathcal{J}_s^+ = \{j \in \mathcal{J}: y_{sj} \geqslant 0\}$$
• $$\mathcal{J}_s^- = \{j \in \mathcal{J}: y_{sj} \leqslant 0\}$$

Si al resolver la relajación continua de un problema entero mixto se obtiene que $\mathcal{I}_f^2 \neq \emptyset$, es necesario introducir un corte para lograr una solución que satisfaga la integralidad de esas variables. Tomando la variable $x_s \in \mathcal{I}_f^2(\bar{\mathbf{x}})$ se tiene en el sistema explícito:

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

que resulta equivalente a:

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

En este punto se descompone el conjunto de índices \(\mathcal{J} = \mathcal{J}_s^+ \cup \mathcal{J}_s^-\) obteniendo que la expresión anterior es equivalente a:

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

Ahora se seleccionará un corte que excluya el valor de $\bar{x}_s$ de la solución óptima, distinguiendo dos casos:

• $x_s \geqslant [\bar{x}_s] + 1$: Como $x_s$ debe ser entera, $[\bar{x}_s]-x_s$ debería ser un entero negativo y, como $0<f_s<1$, se verifica que:

  \[f_s + ([\bar{x}_s] - x_s) \leqslant f_s - 1\]

  y, por tanto:

  \[\left. \begin{aligned} \sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \sum_{j \in \mathcal{J}_s^-} y_{sj} x_j &\leqslant f_s - 1 \\ \sum_{j \in \mathcal{J}_s^+} y_{sj} x_j &\geqslant 0 \end{aligned} \right\} \Rightarrow \sum_{j \in \mathcal{J}_s^-} y_{sj} x_j \leqslant f_s - 1\]

  deduciéndose que:

  \[\frac{f_s}{f_s-1}\sum_{j \in \mathcal{J}_s^-} y_{sj}x_j \geqslant f_s\]

  Añadiendo el término asociado a $\mathcal{J}_s^+$ se obtiene el corte:

  \[\sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \frac{f_s}{f_s-1}\sum_{j \in \mathcal{J}_s^-} y_{sj}x_j \geqslant f_s\]

• $x_s \leqslant [\bar{x}_s]$: Como $x_s$ debe ser entera y como $f_s < 1$, se deduce que \([\bar{x}] - x_s \geqslant 0\) y, por tanto, la restricción se convierte en:

  \[\sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \sum_{j \in \mathcal{J}_s^-} y_{sj} x_j \geqslant f_s\]

  Por la definición del conjunto $\mathcal{J}_s^-$ y por ser $0 < f_s < 1$ se verifica:

  \[\sum_{j \in \mathcal{J}_s^-} y_{sj} x_j \leqslant 0 \leqslant \frac{f_s}{f_s-1}\sum_{j \in \mathcal{J}_s^-} y_{sj}x_j\]

  concluyendo también que el corte asociado es el mismo que el obtenido en el caso anterior:

  \[\sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \frac{f_s}{f_s-1}\sum_{j \in \mathcal{J}_s^-} y_{sj}x_j \geqslant f_s\]

Por tanto, el corte de Gomory mixto en ambos casos, se puede reescribir:

\[\sum_{j \in \mathcal{J}_s^+} y_{sj} x_j + \frac{f_s}{1-f_s}\sum_{j \in \mathcal{J}_s^-} (-y_{sj}) x_j \geqslant f_s\]

Resolución del ejemplo anterior

En la tabla de la relajación continua, el corte asociado a la variable $x_2$ (por no haberse obtenido un valor entero) es:

\[\frac{\frac{2}{5}}{1-\frac{2}{5}}(\frac{4}{5}) x_3 \geqslant \frac{2}{5} \equiv \frac{8}{15}x_3 \geqslant \frac{2}{5}\]

que al introducirlo en la tabla y aplicar el Algoritmo Dual del Símplex se obtiene la tabla final:

\[\begin{array}{rc|rrrr|r} & & \color{gray}{3} & \color{gray}{2} & \color{gray}{1} & \color{gray}{0} & \\ & & x_1 & x_2 & x_3 & x_4^h & \\ \hline & z_j - c_j & 0 & 0 & 0 & -3/2 & 13 \\ \hline \color{gray}{3} & x_1 & 1 & 0 & 0 & 9/8 & 11/4 \\ \color{gray}{2} & x_2 & 0 & 1 & 0 & - 3/2 & 2 \\ \color{gray}{1} & x_3 & 0 & 0 & 1 & -15/8 & 3/4 \\ \hline \end{array}\]

proporcionando la solución óptima del problema:

\[\mathbf{x}^* = (11/4, 2, 3/4)^\intercal \quad z^* = 13\]

---

Los cortes de Gomory mixtos representan uno de los pilares de los motores de optimización modernos (optimizadores como Gurobi, CPLEX o SCIP). Al combinar estos cortes con el esquema en árbol de Branch & Bound, se da lugar al algoritmo Branch & Cut, capaz de resolver problemas industriales complejos de gran escala de manera rápida y matemáticamente rigurosa.

---

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