Branch & Bound: ramificar, acotar y podar

¿Por qué no basta el Simplex para variables enteras?

Cuando un modelo exige variables enteras (ILP) o binarias (MILP), el conjunto factible deja de ser un poliedro continuo y pasa a ser un conjunto de puntos discretos. El Simplex recorre vértices de un poliedro continuo, así que no aplica directo: su óptimo suele caer en un punto con coordenadas fraccionarias que no es una solución entera válida.

La estrategia de Branch & Bound (ramificar y acotar) es el método central para MILP. Se apoya en tres movimientos: relajar la integralidad, ramificar sobre una variable fraccionaria y acotar/podar ramas que no pueden mejorar lo que ya tenemos.

La relajación lineal entrega una cota

Si borramos la exigencia de integralidad (dejamos $x\in \mathbb{R}$ en vez de $x\in \mathbb{Z}$), obtenemos la relajación lineal, un LP que el Simplex sí resuelve. Su óptimo es una cota del óptimo entero: superior en un problema de maximización, inferior en uno de minimización (porque relajar amplía el factible, nunca puede dar algo peor que el entero).

La mejor relajación posible: la envoltura convexa

La relajación ideal sería la envoltura convexa de los puntos enteros factibles: el menor conjunto convexo que los contiene. Si pudiéramos describirla con desigualdades lineales, el Simplex daría directo el óptimo entero (sus vértices ya serían enteros). No la conocemos explícitamente, pero tanto B&B como los planos cortantes buscan acercarse a ella.

Ramificar sobre una variable fraccionaria

Si la relajación de un nodo da, por ejemplo, $x_j=4,5$, ese valor es imposible en el entero. Ramificamos creando dos subproblemas excluyentes que juntos cubren todos los enteros pero descartan el intervalo fraccionario:

Cada rama es un nuevo LP (el mismo problema más esa cota extra). El proceso genera un árbol de subproblemas.

La incumbente

La incumbente es la mejor solución entera factible encontrada hasta el momento. Empieza vacía (o en $\pm \infty$) y se actualiza cada vez que un nodo entrega una solución entera mejor. Es la cota del óptimo por el lado opuesto a la relajación.

Podar (fathoming): cerrar una rama sin explorarla

Una rama se poda —se cierra sin seguir ramificando— por una de tres razones:

• Infactibilidad: el LP de ese nodo no tiene solución (las cotas acumuladas se contradicen).
• Integralidad: la relajación ya da una solución entera → es candidata a incumbente, no hay nada más que ramificar en esa rama.
• Cota: la relajación del nodo no supera a la incumbente (en un max, su $z$ relajado es $\le$ incumbente; en un min, $\ge$). Aunque siguiéramos, no encontraríamos nada mejor.

Estrategias de exploración

• DFS (profundidad): baja hasta las hojas primero. Usa poca memoria y tiende a encontrar una incumbente rápido.
• Best-first: explora primero el nodo con mejor cota relajada. Suele podar más, a costa de más memoria.

En un problema de max, el $z$ de un nodo padre es cota superior del $z$ de sus hijos (agregar restricciones solo puede empeorar la relajación).

¿Qué tan cerca del óptimo estamos mientras el árbol sigue abierto?

El GAP de optimalidad mide la distancia entre lo que ya tenemos y lo mejor que aún es posible, usando dos cotas:

• Incumbente: mejor solución entera encontrada.
• Mejor cota: el valor más favorable entre las relajaciones de todos los nodos vivos (no podados y no explorados). Un nodo hijo aún sin resolver hereda la cota de su padre hasta que se resuelva.

Solvers como Gurobi usan el GAP relativo para detenerse antes (parámetro MIPGap): cuando el gap ya es tolerable, cortan sin cerrar todo el árbol. GAP $=0$ certifica optimalidad.

Ejemplo de examen: leer un árbol y calcular el GAP

En un árbol de minimización con raíz $z^{\ast }=-56,4$, la rama $P_1$ ($z^{\ast }=-55,5$) se abre en $P_{11}$ ($z^{\ast }=-54$, entero $x^{\ast }=(6,0,0)$) y $P_{12}$ ($z^{\ast }=-52,\overline{6}$); la rama $P_2$ da la primera incumbente ($z=-48$).

Tras recorrer $P^R\to P_2\to P_1\to P_{11}$: $P_2$ fija la incumbente en $-48$, y $P_{11}$ la mejora a $-54$. El único nodo vivo es $P_{12}$, que aún no se evalúa y hereda la cota de su padre $P_1$ ($-55,5$). Entonces:

El orden cambia qué se poda

El orden de exploración no cambia el óptimo, pero sí cuánto trabajo cuesta. Si un nodo con solución entera se resuelve antes que un hermano de peor cota, ese hermano se poda por cota de inmediato. Resuelto al revés, el hermano se ramifica innecesariamente. (Truco de examen: si en el árbol un nodo sí fue ramificado pese a tener peor cota que una hoja entera, es que se exploró antes que ella.)

Un atajo: relajaciones que ya salen enteras

A veces la relajación lineal ya entrega una solución entera sin ramificar nada. Eso ocurre cuando la matriz de restricciones $A$ es totalmente unimodular (TU).

Definición

El resultado clave

Si $A$ es TU y el vector $b$ es entero, entonces todos los vértices del poliedro son enteros, así que la relajación lineal ya da una solución entera — no hace falta B&B. Muchas matrices de redes (incidencia nodo-arco, transporte, asignación) son TU, y por eso esos modelos se resuelven con Simplex puro.