Ramificar y acotar ( BB , B&B o BnB ) es un paradigma de diseño de algoritmos para problemas de optimización combinatoria y discreta , así como optimización matemática . Un algoritmo de ramificación y acotación consiste en una enumeración sistemática de soluciones candidatas por medio de la búsqueda en el espacio de estado : se piensa que el conjunto de soluciones candidatas forma un árbol enraizado con el conjunto completo en la raíz. El algoritmo explora ramas .de este árbol, que representan subconjuntos del conjunto solución. Antes de enumerar las soluciones candidatas de una rama, la rama se compara con los límites estimados superior e inferior de la solución óptima, y se descarta si no puede producir una solución mejor que la mejor encontrada hasta ahora por el algoritmo.
El algoritmo depende de la estimación eficiente de los límites inferior y superior de las regiones/ramas del espacio de búsqueda. Si no hay límites disponibles, el algoritmo degenera a una búsqueda exhaustiva.
El método fue propuesto por primera vez por Ailsa Land y Alison Doig mientras realizaban una investigación en la London School of Economics patrocinada por British Petroleum en 1960 para programación discreta , [1] [2] y se ha convertido en la herramienta más utilizada para resolver NP-hard problemas de optimización. [3] El nombre "branch and bind" apareció por primera vez en el trabajo de Little et al. sobre el problema del viajante de comercio . [4] [5]
El objetivo de un algoritmo de ramificación y acotación es encontrar un valor x que maximice o minimice el valor de una función de valor real f ( x ) , llamada función objetivo, entre algún conjunto S de soluciones admisibles o candidatas . El conjunto S se denomina espacio de búsqueda o región factible . El resto de esta sección supone que se desea la minimización de f ( x ) ; esta suposición viene sin pérdida de generalidad , ya que uno puede encontrar el valor máximo de f ( x ) encontrando el mínimo de g (X ) = - F ( X ) . Un algoritmo B&B funciona según dos principios:
Convertir estos principios en un algoritmo concreto para un problema de optimización específico requiere algún tipo de estructura de datos que represente conjuntos de soluciones candidatas. Tal representación se llama una instancia del problema. Denote el conjunto de soluciones candidatas de una instancia I por S I . La representación de instancia tiene que venir con tres operaciones:
Usando estas operaciones, un algoritmo B&B realiza una búsqueda recursiva de arriba hacia abajo a través del árbol de instancias formado por la operación de rama. Al visitar una instancia I , verifica si el límite ( I ) es mayor que un límite superior encontrado hasta el momento; si es así, puedo ser descartado de forma segura de la búsqueda y la recursividad se detiene. Este paso de poda generalmente se implementa manteniendo una variable global que registra el límite superior mínimo visto entre todas las instancias examinadas hasta el momento.