Encontrar la aguja sin mirar todo el pajar

Imagen de Jakub Żerdzicki extraída de Unsplash

La Optimización Lineal es una de las herramientas más potentes en investigación operativa. Sin embargo, cuando añadimos la restricción realista de que las variables deben ser números enteros (como el número de camiones a fletar, fábricas a abrir o personas a contratar), el problema cambia drásticamente de categoría.

El redondeo ingenuo de la solución continua rara vez funciona y a menudo conduce a soluciones infactibles o distantes del verdadero óptimo. Para resolver este desafío sin caer en una búsqueda exhaustiva imposible de computar, el algoritmo de Ramificación y Acotación (Branch and Bound) se posiciona como uno de los referentes.

Breve contexto histórico

El concepto básico del procedimiento de ramificación y acotación surgió a principios de los años 60:

• 1960: Las investigadoras Ailsa Land y Alison Harcourt (Doig) publicaron el trabajo pionero (Land & Doig, 1960) que dio origen a la metodología de ramificación y acotación para resolver problemas numéricos discretos.
• 1965: R. J. Dakin formuló una variación orientada a la Optimización Entera (Dakin, 1965) basada en la división del espacio mediante restricciones sobre las variables fraccionarias, dando lugar a la estructura de árbol jerárquico tal y como la conocemos hoy.

Conceptos fundamentales

Para entender la ramificación y acotación, imaginemos un proceso inteligente de “divide y vencerás” apoyado en tres pilares (asumiendo un problema de minimización):

1. Relajación Continua: Consiste en resolver el problema eliminando temporalmente las condiciones de integralidad de las variables. Esto nos permite aplicar algoritmos rápidos (como el Símplex o Punto Interior) y obtener una cota teórica del mejor valor posible.

2. Ramificación (Branching): Si la solución relajada devuelve un valor no entero para una variable $x_k^*$ que debería ser entera, dividimos el problema original en dos subproblemas excluyentes agregando nuevas restricciones: \(x_k \leqslant \lfloor x_k^* \rfloor\) y \(x_k \geqslant \lceil x_k^* \rceil\) que permiten ignorar una zona en la que no puede haber soluciones enteras.

3. Acotación (Bounding): Conforme exploramos el árbol de subproblemas, mantenemos el control de las cotas:

   • Cota Inferior ($z_S$): El valor de la función objetivo en los nodos relajados.
   • Cota Superior ($z_I$): El valor objetivo de la mejor solución entera conocida hasta el momento.
   • Estas cotas se invierten en el caso de un problema de maximización.

Ejemplo práctico paso a paso

Para ver cómo funciona el algoritmo en la práctica, consideremos el siguiente problema de minimización:

\[\begin{aligned} \min \quad & z = -80x_1 - 45x_2 \\ \text{s.a:} \quad & x_1 + x_2 \leqslant 7 \\ & 12x_1 + 5x_2 \leqslant 60 \\ & x_1, x_2 \geqslant 0\\ & x_1, x_2 \in \mathbb{Z} \end{aligned}\]

Gráficamente, el conjunto de soluciones enteras se muestra en la siguiente figura (puntos azul claro) junto a la solución continua (rombo azul oscuro):

Nodo raíz ($P_1$): Relajación continua

Resolvemos el problema eliminando la condición de integralidad de las variables ($x_1, x_2 \geqslant 0$ continuas):

• Solución óptima: $x^* = \left(\frac{25}{7}, \frac{24}{7}\right) \approx (3.57, 3.43)$
• Valor de la función objetivo: $z^* = -440$

Dado que ni $x_1$ ni $x_2$ son valores enteros, debemos ramificar. Elegimos la variable $x_1 = 3.57$ para dividir el problema en $x_1 \leqslant 3$ y $x_1 \geqslant 4$. De este modo, evitamos la zona $3 < x_1 <4$ donde no existe ninguna solución entera. Se fija la cota inferior en $z_S = -440$.

Nivel 1: Ramificación en $x_1$

Una vez que se ha decidido ramificar sobre la variable $x_1$, los problemas a resolver gráficamente son $P2$ (lado izquiedo de la gráfica) y $P3$ (lado derecho de la gráfica):

• Subproblema $P_2$ ($x_1 \leqslant 3$)

  Añadimos la restricción $x_1 \leqslant 3$ al problema original y resolvemos el nuevo problema (usando técnicas de post-optimización para ahorrar iteraciones):

  • Solución: $x^* = (3, 4)$
  • Valor objetivo: $z^* = -420$

  La solución es entera, es una solución factible del problema original.

  Al ser factible y entera, fijamos nuestra primera cota superior entera conocida: $z_I = -420$. Por tanto, ya no es necesario seguir ramificando desde $P_2$.

• Subproblema $P_3$ ($x_1 \geqslant 4$) Añadimos la restricción $x_1 \geqslant 4$:

  • Solución: $x^* = \left(4, \frac{12}{5}\right) = (4, 2.4)$
  • Valor objetivo: $z^* = -428$

  Como $z^* = -428 < z_I = -420$, este nodo aún puede obtener una mejor solución que la que tenemos actualmente. Sin embargo, $x_2 = 2.4$ no es entero, por lo que debemos ramificar $P_3$ respecto a $x_2$ en $x_2 \leqslant 2$ y $x_2 \geqslant 3$.

Nivel 2: Ramificación desde $P_3$ en $x_2$

Ramificando $P_3$ sobre la variable $x_2$, los problemas a resolver gráficamente son $P4$ (parte inferior de la gráfica) y $P4$ (parte superior de la gráfica):

• Subproblema $P_4$ ($x_1 \geqslant 4, x_2 \leqslant 2$)

  • Solución: $x^* = \left(\frac{25}{6}, 2\right) \approx (4.17, 2)$
  • Valor objetivo: $z^* = \frac{1270}{3} \approx -423.33$

  Dado que $z^* = -423.33 < z_I = -420$ y la variable $x_1 = 4.17$ no es entera, mantendremos este nodo abierto para ramificarlo más adelante.

• Subproblema $P_5$ ($x_1 \geqslant 4, x_2 \geqslant 3$)

  • Resultado: El sistema no tiene región factible (Infactible).

Nivel 3: Ramificación desde $P_4$ en $x_1$

Ramificando $P_4$ sobre la variable $x_1$, los problemas a resolver gráficamente son $P6$ (lado izquiedo de la gráfica) y $P7$ (lado derecho de la gráfica):

Ramificamos el nodo $P_4$ respecto a la variable fraccionaria $x_1 \approx 4.17$ evaluando $x_1 \leqslant 4$ y $x_1 \geqslant 5$.

• Subproblema $P_6$ ($x_1 \leqslant 4$, manteniendo $x_1 \geqslant 4$ y $x_2 \leqslant 2 \implies x_1 = 4, x_2 \leqslant 2$)
  • Solución: $x^* = (4, 2)$ (Entera)
  • Valor objetivo: $z^* = -410$
  • Análisis: Aunque es entera, $z^* = -410 \geqslant z_I = -420$. Esta solución es peor que nuestra cota entera conocida, por lo que se descarta.
• Subproblema $P_7$ ($x_1 \geqslant 5$, manteniendo $x_2 \leqslant 2$)
  • Solución: $x^* = (5, 0)$ (Entera)
  • Valor objetivo: $z^* = -400$
  • Análisis: De igual forma, $z^* = -400 \geqslant z_I = -420$. Se descarta por no mejorar la cota.

Solución óptima final

No quedan nodos pendientes de exploración. La mejor solución entera obtenida a lo largo del proceso es la del nodo $P_2$:

\[\mathbf{x}^* = (3,4) \quad \implies \quad z^* = -420\]

Todo este procedimiento se puede representar en un árbol del siguiente modo:

Criterios de Poda y Estrategias (Tuning)

El verdadero poder del Branch & Bound no reside únicamente en dividir el problema, sino en saber cuándo dejar de explorar una rama. Si tuviéramos que explorar todo el árbol, el número de nodos crecería exponencialmente.

Aquí es donde entra en juego el tuning del algoritmo mediante los criterios de poda y las estrategias de exploración.

• Criterios de Poda (Cierre de Nodos)

  Un nodo del árbol se da por finalizado (se “poda”) y no se vuelve a ramificar cuando ocurre uno de estos tres escenarios:

  1. Poda por integralidad: La relajación del subproblema produce una solución cuyas variables con restricción entera toman valores enteros. Esta solución se convierte en la nueva cota superior ($z_I$) si su valor mejora a la mejor solución conocida hasta el momento.
  2. Poda por Infactibilidad: El subproblema generado por las nuevas restricciones no tiene ninguna solución factible (como ocurrió en el nodo $P_5$).
  3. Poda por Cota (Dominancia): El valor de la función objetivo relajada del nodo (\(z^*\)) es peor o igual que la cota entera ya conocida (\(z^* \geqslant z_I\) en minimización). Si la versión “relajada” (ideal) ya no mejora a lo que ya tenemos garantizado, sus soluciones sucesivas tampoco lo harán.

• Estrategias de Exploración del Árbol

  La eficiencia práctica del algoritmo depende enormemente del orden en el que elegimos qué nodo explorar a continuación:

  • Búsqueda en Profundidad (Depth-First Search - DFS): Explora una rama hasta encontrar rápidamente una solución entera. Su ventaja es que encuentra una cota $z_I$ de forma temprana para empezar a podar por cota lo antes posible.
  • Búsqueda en Anchura (Breadth-First Search - BFS): Explora todos los nodos del mismo nivel antes de descender. Garantiza una visión global de las cotas, aunque consume más memoria.
  • Búsqueda por Mejor Cota (Best-Bound Search): Selecciona el nodo con el valor de $z$ relajado más prometedor. Es la estrategia preferida por la mayoría de los motores modernos porque suele minimizar el número total de nodos evaluados.

En la actualidad, los optimizadores comerciales y de código abierto (como Gurobi, CPLEX o CBC, por ejemplo) no emplean Branch & Bound puro, sino una versión evolucionada llamada Branch & Cut. Esta técnica añade planos de corte (como los cortes de Gomory) en cada nodo para reducir la región continua antes de ramificar, resolviendo problemas industriales con millones de variables en cuestión de segundos.

---

Branch & Bound demuestra que no hace falta evaluar las billones de combinaciones posibles de un problema discreto para encontrar la solución óptima con total certeza matemática. Mediante la relajación continua y el uso inteligente de las cotas, podemos descartar enormes regiones del espacio de búsqueda sin explorarlas.

---

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