Branch and Bound
Branch and bound explora el espacio de soluciones ramificando y poda los subárboles que no pueden contener el óptimo usando cotas; se usa en optimización discreta.
Propósito
Resolver exactamente problemas de optimización combinatoria, acelerando la búsqueda mediante poda.
Mecanismo
Se mantiene una cota global óptima. Ramificar: dividir el problema en subproblemas. Acotar: calcular una cota inferior/superior para cada subproblema y podar si la cota no mejora la mejor actual. Común en programación entera y el TSP.
Casos de uso
- Programación entera
- Resolución del TSP
- Optimización combinatoria