##  [Branch And Bound](/es/node/58867) 

 Definición

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

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

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

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

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

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

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 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

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.