Branch and bound
La poda de backtracking aplicada a problemas de optimización: en vez de descartar lo inválido, se descarta lo que ya no puede superar a la mejor solución encontrada.
Para este tema conviene tener claro:Backtracking y poda
En un problema de optimización no hay ramas inválidas que podar: cualquier combinación es una solución, apenas peor o mejor. Branch and bound encuentra igual qué descartar, comparando lo mejor que una rama podría llegar a dar contra lo mejor que ya se tiene.
Ramificar, acotar y podar
Hacen falta tres piezas. La ramificación: partir el problema en subproblemas que cubran todas las posibilidades, típicamente decidiendo una variable. La cota: una estimación optimista de lo mejor que se puede lograr dentro de ese subproblema. Y la incumbente: la mejor solución completa encontrada hasta ahora.
Con esas tres, la regla de poda es una comparación: si la cota optimista de una rama no supera a la incumbente, esa rama entera se descarta sin explorarla.
Mochila de capacidad 10 con tres objetos. Ramificamos decidiendo, en cada nivel, si el objeto entra o no.
Antes de seguir, predecí
La cota tiene que ser válida y ajustada
La cota tiene que cumplir dos cosas a la vez, y ahí está toda la dificultad. Debe ser válida —nunca subestimar el óptimo de la rama, o se poda la solución correcta— y ajustada, porque una cota floja no poda nada y el algoritmo degenera en fuerza bruta.
También tiene que ser barata: se calcula en cada nodo. El equilibrio entre precisión y costo es la decisión de diseño principal.
Relajar el problema para conseguir la cota
La forma habitual de obtener una cota es relajar el problema: resolver una versión más fácil cuyo óptimo es necesariamente igual o mejor que el real.
En la mochila 0/1, la relajación es permitir fracciones de objeto. Eso se resuelve con un algoritmo goloso en tiempo lineal y da una cota superior legítima del valor alcanzable: si ni siquiera partiendo objetos se supera la incumbente, la rama no sirve. Es el ejemplo canónico de una técnica que falla como solución exacta pero es perfecta como cota.
Acá el orden de exploración es parte del algoritmo
A diferencia de backtracking, acá el orden de exploración es parte del algoritmo. Se mantiene una cola de prioridad con los nodos abiertos y se expande primero el más prometedor: mejor cota primero.
La intuición es que encontrar rápido una buena incumbente mejora todas las podas posteriores. El costo es la memoria: mejor-cota-primero puede tener muchísimos nodos abiertos a la vez, mientras que en profundidad sólo se guarda una rama. Las implementaciones reales mezclan las dos: bajan en profundidad para conseguir una incumbente y después priorizan por cota.
El motor de los resolvedores enteros
Es el motor de los resolvedores de programación lineal entera. La relajación continua se resuelve con símplex; si el óptimo da valores fraccionarios, se ramifica sobre una variable —menor o igual a , mayor o igual a — y se repite. Eso es branch and bound.
También resuelve el viajante de comercio en instancias medianas, asignación de recursos y planificación. No cambia que los problemas sean NP-difíciles: los vuelve tratables en tamaños concretos.
Lo que sí garantiza, y lo que no
El peor caso sigue siendo exponencial y no hay forma de saber de antemano cuánto va a tardar una instancia. Lo que sí da, y es su ventaja sobre las heurísticas, es una garantía: en todo momento se conoce la incumbente y la mejor cota global, y la diferencia entre ambas —el gap— dice qué tan lejos se está del óptimo.
Eso permite cortar por tiempo con una respuesta útil: “esta solución está a lo sumo un 3% del óptimo”. Un goloso da un número sin ninguna garantía.
Contra fuerza bruta y contra las alternativas
| Fuerza bruta | Branch and bound | Heurística | |
|---|---|---|---|
| Encuentra el óptimo | sí | sí | no necesariamente |
| Sabe que es el óptimo | sí | sí, y puede demostrarlo | no |
| Costo | siempre exponencial | exponencial en el peor caso, mucho menos en la práctica | polinomial |
| Se puede cortar a mitad de camino | no sirve de nada | sí: queda la mejor encontrada más una cota | sí |
| Qué hace falta diseñar | nada | la cota, que es todo el trabajo | la regla |
Más a fondo · nivel seniorDe dónde sale una cota buena
La técnica general es relajar el problema: quitarle una restricción hasta que se vuelva fácil, y usar el óptimo del problema relajado como cota del original. Como el relajado tiene más soluciones posibles, su óptimo es al menos tan bueno, y por lo tanto es una cota válida.
En la mochila 0/1, relajar es permitir partir los objetos: la mochila fraccionaria se resuelve con un goloso en y da una cota superior ajustada. En el viajante, relajar es pedir un árbol generador en vez de un ciclo. En programación entera, relajar es permitir valores fraccionarios, que es exactamente lo que hacen todos los resolvedores comerciales antes de ramificar.
Ahí está el canje central de la técnica: una relajación más floja se resuelve más rápido y poda menos; una más ajustada poda mucho y cuesta calcularla en cada nodo. Encontrar ese punto es el trabajo de diseño, y es específico de cada problema.
Lo que preguntan sobre esto
Cierre
Branch and bound es ramificar, acotar con una relajación y podar contra la mejor solución conocida. La calidad de la cota decide todo, y el gap entre incumbente y cota es lo que convierte una búsqueda exponencial en una respuesta con garantía.
Autoevaluación
¿Lo entendiste?
Práctica