Una técnica general de optimización que explora sistemáticamente un espacio de búsqueda ramificando en subproblemas y usando cotas calculadas sobre la mejor solución posible dentro de cada rama para podar regiones que no pueden contener la solución óptima.

Principio

Combinar ramificación (descomposición del espacio de búsqueda) con acotamiento (cálculo de límites optimistas o pesimistas) y una estrategia de búsqueda para eliminar ramas cuyas cotas demuestran que no pueden superar la mejor solución actual.

Demostración

Resolver un programa lineal entero ramificando sobre variables fraccionarias: cada nodo representa un subproblema con restricciones de integridad adicionales, y una relajación (programa lineal) proporciona una cota superior; los nodos cuya cota de relajación es peor que la del incumbente se podan. En el TSP, ramificar sobre elecciones de subtours y usar cotas inferiores para podar ramas no prometedoras temprano.

Aplicación incorrecta

Usar cotas débiles o holgadas, malas decisiones de ramificación o un orden de nodos inapropiado que resulte en poco o ningún poda, haciendo que el algoritmo se transforme en una búsqueda casi exhaustiva y desperdicie cómputo.

Consecuencia

Si hay cotas y heurísticas efectivas, el método puede reducir sustancialmente el espacio explorado y garantizar optimalidad al finalizar; también puede producir cotas válidas y mejores soluciones parciales en tiempo de ejecución.

Inversión

Enumeración exhaustiva sin poda (búsqueda por fuerza bruta) que examina todos los candidatos sin usar cotas, o búsqueda puramente heurística que nunca garantiza optimalidad.

Límite

Se adapta principalmente a problemas de optimización discretos y combinatorios donde se pueden calcular cotas (p. ej., programación entera, planificación combinatoria). Es menos aplicable a problemas sin relajaciones calculables eficientemente o a problemas continuos sin discretización/relajación.

Tensión semántica

Tensión entre la precisión de las cotas y el coste computacional para obtenerlas: cotas más ajustadas podan más pero pueden ser caras de computar; contrasta con métodos de planos de corte o heurísticos que mejoran las cotas de otra manera o sacrifican optimalidad por rapidez.

Síntesis

Branch and bound organiza una búsqueda completa dividiendo el problema en subproblemas y usando cotas para descartar regiones no prometedoras; el rendimiento práctico depende de la calidad de las cotas, las reglas de ramificación y la selección de nodos, produciendo soluciones exactas si se lleva hasta el final y incumbents útiles antes de concluir.