Branch and Bound es una técnica para resolver problemas de optimización explorando un árbol de decisiones. En cada nodo se calcula una cota que estima qué tan buena podría llegar a ser la mejor solución dentro de esa rama.

La técnica combina dos acciones: ramificar y acotar. Ramificar significa dividir el problema en decisiones más específicas. Acotar significa estimar si una rama todavía tiene posibilidad de mejorar la mejor solución encontrada.

El algoritmo mantiene una mejor solución conocida y una lista de nodos pendientes. Cada nodo se conserva o se descarta según sus cotas.

En un problema de maximización, $CS(N)$ es la cota superior (estimación optimista) del nodo $N$. Si este valor máximo posible ni siquiera alcanza a la mejor solución ya encontrada (mejor), la rama se corta porque no tiene sentido seguir explorando algo que no puede superar lo que ya tenemos.

En minimización, $CI(N)$ representa la cota inferior (el costo mínimo estimado). Si el costo más bajo que podríamos conseguir en esta rama es mayor o igual que el mejor costo ya conocido, descartamos el nodo.

Cada nodo representa una solución parcial. Además de las decisiones tomadas, el nodo guarda el valor acumulado, los recursos usados, una cota optimista y el siguiente nivel de decisión.

Un nodo N se define por el vector de decisiones parciales $X_k$, el valor y recurso consumido hasta el momento, las cotas inferior ($CI$) y superior ($CS$), y el nivel $k$ en el árbol de decisiones.

Ramificar consiste en dividir el problema actual en dos o más subproblemas. En el caso binario, esto suele significar tomar una decisión (valor 1) o ignorarla (valor 0) para el siguiente elemento del problema.

La variable $mejor$ se actualiza únicamente cuando encontramos una solución que es factible (cumple restricciones), completa (todas las decisiones tomadas) y que además supera el valor previo.

Este modelo resume el destino de un nodo. Puede morir por exceder recursos, por ser una hoja del árbol, o por ser suboptimal (su cota superior no supera al mejor). Si no cumple nada de esto, el nodo permanece vivo para ser explorado más tarde.

En la mochila entera 0/1 se tienen objetos con valor y peso. El objetivo es maximizar el valor total sin superar la capacidad.

La variable de decisión $x_i$ es binaria. Un valor de 1 indica que el objeto forma parte de la mochila, y un 0 indica que se queda fuera.

Buscamos maximizar la suma de los valores ($v_i$) de los objetos elegidos, con la restricción de que la suma de sus pesos ($w_i$) no exceda la capacidad total W.

Para estimar una cota superior en mochila 0/1, permitimos tomar fracciones de objetos. Esa solución fraccionaria es siempre mayor o igual a cualquier solución entera.

La cota superior del nodo $N$ es la suma del valor ya acumulado más el valor que obtendríamos si pudiéramos llenar el resto de la capacidad de forma óptima usando fracciones de los objetos que sobran.

Cuando un objeto ya no cabe completo, tomamos solo la parte proporcional que complete la capacidad W. Su valor se calcula multiplicando el valor total del objeto por la fracción de peso que estamos aprovechando.

Branch and Bound puede ser rápido en la práctica, pero su peor caso sigue siendo exponencial.

El tiempo total $T(n)$ depende del número de nodos visitados multiplicado por el costo de las operaciones por nodo: generar hijos ($C_{ramificar}$), calcular la cota ($C_{cota}$) y gestionar la lista de nodos vivos ($C_{LNV}$).

En el peor de los casos, la cota no descarta ninguna rama y visitamos todo el árbol binario de tamaño $2^n$. Sin embargo, una buena cota puede hacer que el número real de nodos sea órdenes de magnitud menor.

Como el cálculo de la cota fraccionaria requiere un recorrido lineal por los objetos restantes, el costo por nodo es $O(n)$, lo que multiplica el costo total del árbol.

Si usamos una cola de prioridad para Max Benefit o Least Cost, insertar y extraer nodos tiene un costo logarítmico respecto al número de nodos vivos en ese momento.