Saltar al contenido
Volver a los resultados

Branch and Bound

Propuesto por
Ailsa Land & Alison Doig
Año
1960
Tipo
Exact combinatorial optimization algorithm
Familia
Mathematical programming

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

Branch and Bound es un algoritmo exacto y sistemático para problemas de optimización combinatoria y entera, introducido por Ailsa Land y Alison Doig en 1960.

Organiza el espacio de búsqueda como un árbol de subproblemas, utiliza cotas superiores derivadas de relajaciones para podar ramas que no pueden mejorar la mejor solución conocida y garantiza la obtención de una solución entera óptima global. Es la columna vertebral de los modernos solucionadores de programación mixta entera utilizados en investigación de operaciones, logística, planificación e ingeniería de diseño.

La intuición detrás del método

Imagine buscar el objeto de mayor valor oculto en un vasto laberinto de habitaciones. En lugar de revisar cada habitación, estima el valor máximo posible que se puede alcanzar desde cada corredor antes de entrar en él. Si ese techo es inferior al mejor objeto que ya tiene, omite todo el corredor sin mirar dentro. Branch and Bound funciona de la misma manera: divide el problema en piezas más pequeñas, calcula cotas superiores optimistas para cada pieza y descarta inmediatamente cualquier pieza que, de forma demostrable, no pueda superar la mejor solución actual.

Historia

Land y Doig publicaron el artículo fundamental sobre Branch and Bound en Econometrica en 1960, presentándolo como un método automático para la programación discreta. Little et al. (1963) aplicaron la técnica al problema del viajante de comercio, consolidando su papel en la optimización combinatoria. Dakin (1965) introdujo la ramificación por relajación LP, la forma más utilizada hoy en día. Las décadas siguientes vieron la integración de planos de corte (branch-and-cut) y generación de columnas (branch-and-price), convirtiendo a Branch and Bound en el motor de todos los principales solucionadores comerciales de programación entera.

Cuándo usarlo

Utilice Branch and Bound cuando deba encontrar la solución demostrablemente óptima para un programa lineal mixto o entero puro y no pueda aceptar una respuesta aproximada. Asume que el problema puede formularse con relajaciones lineales (o convexas) que proporcionan cotas útiles. Es menos adecuado para instancias muy grandes donde el árbol de enumeración explota, para programas enteros no lineales sin relajaciones ajustadas, o para entornos en tiempo real donde el tiempo de cálculo está estrictamente limitado. En tales casos, se pueden preferir heurísticas o metaheurísticas.

Limitaciones y consideraciones

  • La complejidad en el peor de los casos es exponencial; en instancias mal estructuradas, el árbol puede crecer prohibitivamente grande.
  • El rendimiento es muy sensible a la elección de la variable de ramificación y la estrategia de selección de nodos.
  • Requiere una relajación tratable que proporcione cotas superiores significativas; las cotas débiles conducen a una poda mínima.
  • Los requisitos de memoria pueden ser sustanciales cuando se deben almacenar simultáneamente muchos nodos abiertos.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Garantiza la optimalidad global para programas enteros y combinatorios.
  • Reduce drásticamente la búsqueda mediante la poda basada en cotas — a menudo solo se explora una pequeña fracción del árbol de enumeración completo.
  • Flexible: puede incorporar planos de corte (branch-and-cut) o cotas heurísticas (branch-and-price) para una mayor eficiencia.
  • Ampliamente implementado en solucionadores comerciales maduros (CPLEX, Gurobi) y herramientas de código abierto (GLPK, CBC).

Aplicaciones

  • Planificación de tripulaciones de aerolíneas y asignación de flotas en investigación de operaciones.
  • Diseño de redes de cadenas de suministro y problemas de localización de instalaciones.
  • Diseño de circuitos VLSI y asignación de registros en ingeniería informática.
  • Predicción de la estructura de proteínas y ensamblaje de genomas en biología computacional.
  • Optimización de carteras financieras con restricciones de cardinalidad.

Cómo funciona

Cómo funciona

1

El algoritmo comienza resolviendo una versión relajada del problema —típicamente la relajación lineal (LP)— que ignora las restricciones de integralidad. Esta relajación produce una cota superior sobre el valor óptimo real porque cada solución entera factible es también factible en la relajación. Si la solución relajada resulta tener valores enteros, el problema se resuelve inmediatamente.

Fórmula
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}
2

Cuando la solución relajada contiene una variable fraccionaria, el algoritmo particiona la región factible añadiendo restricciones complementarias que fuerzan a la variable a su valor entero inferior o superior. Cada partición crea un nuevo nodo hijo en el árbol de búsqueda, dividiendo efectivamente un subproblema en dos subproblemas más pequeños con dominios más acotados.

Fórmula
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
3

Cada nodo activo recibe su propia cota de relajación LP. Un nodo cuya cota no supere la mejor solución entera encontrada hasta el momento —llamada el actual— no puede contener una mejor solución, por lo que se poda. Las cotas ajustadas son críticas: cuanto más ajustada sea la cota, menos nodos se necesitarán explorar.

Fórmula
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}
4

Un nodo se considera culminado (cerrado permanentemente) bajo tres condiciones: su relajación es infactible, su cota no es mejor que la actual, o su solución relajada ya es factible entera. En este último caso, la actual se actualiza si la nueva solución la mejora. El algoritmo termina cuando todos los nodos se han culminado, momento en el cual la actual es el óptimo global.

Fórmula
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)

Errores comunes

  • Elegir mal la variable de ramificación (por ejemplo, ramificar siempre en la primera variable fraccionaria) a menudo conduce a árboles profundos y desequilibrados y a una convergencia lenta.
  • Ignorar desigualdades válidas (planos de corte) significa perder la oportunidad de ajustar significativamente las cotas de relajación.
  • La terminación prematura con una brecha de subóptimalidad que no se informa como tal puede inducir a error a los profesionales, haciéndoles tratar una solución casi óptima como exacta.
  • Aplicar Branch and Bound a relajaciones no lineales o no convexas sin una convexificación especializada puede producir cotas inválidas y resultados incorrectos.

Preguntas frecuentes

¿Cómo difiere Branch and Bound de la enumeración exhaustiva?

La enumeración exhaustiva evalúa explícitamente cada solución entera factible, lo cual es computacionalmente inviable para problemas grandes. Branch and Bound lo evita calculando cotas superiores basadas en relajaciones en cada nodo del árbol de búsqueda y podando subárboles enteros siempre que la cota no pueda superar la mejor solución ya encontrada. En la práctica, solo se examina una pequeña fracción del árbol.

¿Cuál es el papel de la relajación LP en Branch and Bound?

La relajación LP elimina las restricciones de integralidad, haciendo que el problema sea resoluble en tiempo polinomial mediante el método simplex o de puntos interiores. Su valor óptimo sirve como cota superior para el subproblema entero correspondiente. Cuando esta cota es ajustada —cercana al óptimo entero real— se necesitan explorar menos ramas. Las relajaciones más ajustadas, a menudo logradas añadiendo desigualdades válidas, aceleran drásticamente el algoritmo general.

¿Cuándo debo usar Branch and Bound en lugar de una metaheurística como los algoritmos genéticos?

Elija Branch and Bound cuando requiera un certificado de optimalidad y pueda permitirse el tiempo de cálculo. Es ideal para problemas de tamaño mediano con relajaciones LP bien estructuradas. Las metaheurísticas son preferibles cuando el problema es extremadamente grande, carece de una relajación útil, o debe resolverse dentro de un presupuesto de tiempo ajustado donde una solución casi óptima es aceptable. Muchos profesionales combinan ambos: utilizan Branch and Bound con una tolerancia de brecha de terminación temprana.

Métodos relacionados

Fuentes

  1. Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.

    Abrir referencia DOI
    Copiado.