Ramificar y enlazar ( BB , B&B o BnB ) es un método para resolver problemas de optimización dividiéndolos en subproblemas más pequeños y utilizando una función delimitadora para eliminar los subproblemas que no pueden contener la solución óptima. Es un paradigma de diseño de algoritmos para problemas de optimización discreta y combinatoria , así como de optimización matemática . Un algoritmo de ramificación y limitación consiste en una enumeración sistemática de soluciones candidatas mediante búsqueda en el espacio de estados : 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 de soluciones. 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 una estimación eficiente de los límites superior e inferior 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 "ramificar y unir" apareció por primera vez en el trabajo de Little et al. sobre el problema del viajante . [4] [5]
El objetivo de un algoritmo de ramificación y limitación es encontrar un valor x que maximice o minimice el valor de una función f ( x ) de valor real , llamada función objetivo, entre algún conjunto S de soluciones candidatas o admisibles . El conjunto S se llama espacio de búsqueda o región factible . El resto de esta sección supone que se desea minimizar f ( x ) ; esta suposición se produce sin pérdida de generalidad , ya que se 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. Esta representación se denomina instancia del problema. Denotemos el conjunto de soluciones candidatas de una instancia I por S I . La representación de la instancia debe venir con tres operaciones:
Utilizando 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 igual o mayor que el límite superior actual; 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 ahora.
El siguiente es el esqueleto de un algoritmo genérico de rama y límite para minimizar una función objetivo arbitraria f . [3] Para obtener un algoritmo real a partir de esto, se requiere una función delimitadora enlazada , que calcule los límites inferiores de f en los nodos del árbol de búsqueda, así como una regla de ramificación específica del problema. Como tal, el algoritmo genérico que se presenta aquí es una función de orden superior .
Se pueden utilizar varias estructuras de datos de cola diferentes. Esta implementación basada en colas FIFO produce una búsqueda en amplitud . Una pila (cola LIFO) producirá un algoritmo de profundidad primero . Se puede obtener un algoritmo de mejor primero rama y límite utilizando una cola de prioridad que ordena los nodos según su límite inferior. [3] Ejemplos de algoritmos de búsqueda "mejor primero" con esta premisa son el algoritmo de Dijkstra y su descendiente A* search . La variante de profundidad primero se recomienda cuando no se dispone de una buena heurística para producir una solución inicial, porque produce rápidamente soluciones completas y, por lo tanto, límites superiores. [7]
Una implementación de pseudocódigo similar a C++ de lo anterior es:
// Implementación similar a C++ de rama y enlace,// asumiendo que la función objetivo f debe minimizarseSolución combinatoria Branch_and_bound_solve ( Problema combinatorio , ObjectiveFunction función_objetivo /*f*/ , BoundingFunction lower_bound_function /*bound*/ ) { // Paso 1 arriba doble problema_superior_limitado = std :: límites_numéricos <doble> :: infinito ; // = B Solución combinatoria solución_heurística = resolución_heurística ( problema ); // x_h problema_superior_bound = función_objetiva ( solución_heurística ); // B = f(x_h) Solución combinatoria current_optimum = solución_heurística ; // Paso 2 arriba cola <CandidateSolutionTree> cola_candidato ; // inicialización de cola específica del problema cola_candidato = poblar_candidatos ( problema ); while ( ! candidato_queue . vacío ()) { // Paso 3 anterior // Paso 3.1 Nodo CandidateSolutionTree = cola_candidato . estallido (); // "nodo" representa N arriba if ( nodo . representa_single_candidate ()) { // Paso 3.2 if ( función_objetivo ( nodo . candidato ()) < problema_superior_bound ) { current_optimum = nodo . candidato (); problema_superior_limitado = función_objetiva ( actual_óptima ); } // de lo contrario, el nodo es un candidato único que no es óptimo } else { // Paso 3.3: el nodo representa una rama de soluciones candidatas // "child_branch" representa N_i arriba para ( auto && rama_hijo : nodo . nodos_candidatos ) { if ( función_límite_inferior ( rama_niño ) <= límite_superior_problema ) { cola_candidato . poner en cola ( child_branch ); // Paso 3.3.2 } // de lo contrario, enlazado(N_i) > B entonces podamos la rama; paso 3.3.1 } } } devolver current_optimum ; }
En el pseudocódigo anterior, las funciones heuristic_solve
y populate_candidates
llamadas como subrutinas deben proporcionarse según corresponda al problema. Las funciones f ( objective_function
) ybound ( ) lower_bound_function
se tratan como objetos de función tal como están escritas y podrían corresponder a expresiones lambda , punteros de función y otros tipos de objetos invocables en el lenguaje de programación C++.
Cuando es un vector de , los algoritmos de rama y límite se pueden combinar con análisis de intervalos [8] y técnicas de contratista para proporcionar recintos garantizados del mínimo global. [9] [10]
Este enfoque se utiliza para una serie de problemas NP-difíciles :
Branch-and-bound también puede ser una base para varias heurísticas . Por ejemplo, es posible que deseemos detener la ramificación cuando la brecha entre los límites superior e inferior sea menor que un cierto umbral. Esto se utiliza cuando la solución es "suficientemente buena para fines prácticos" y puede reducir en gran medida los cálculos necesarios. Este tipo de solución es particularmente aplicable cuando la función de costos utilizada es ruidosa o es el resultado de estimaciones estadísticas y por lo tanto no se conoce con precisión sino que sólo se sabe que se encuentra dentro de un rango de valores con una probabilidad específica . [ cita necesaria ]
Nau et al. presenta una generalización de rama y límite que también incluye los algoritmos de búsqueda A* , B* y alfa-beta . [dieciséis]
Branch andbound se puede utilizar para resolver este problema.
Maximizar con estas restricciones
y son números enteros.
El primer paso es relajar la restricción de números enteros. Tenemos dos puntos extremos para la primera ecuación que forman una recta: y . Podemos formar la segunda línea con los puntos vectoriales y .
El tercer punto es . Esta es una región de casco convexo , por lo que la solución se encuentra en uno de los vértices de la región. Podemos encontrar la intersección usando reducción de filas, que es , o con un valor de 276.667. Probamos los otros puntos finales barriendo la línea sobre la región y encontramos que este es el máximo sobre los reales.
Elegimos la variable con la parte fraccionaria máxima, en este caso se convierte en el parámetro para el método de rama y enlace. Nos ramificamos y obtenemos 276 @ . Hemos llegado a una solución entera así que pasamos a la otra rama . Obtenemos 275,75 @ . Tenemos un decimal, así que nos ramificamos y encontramos 274.571 @ . Probamos con la otra rama y no hay soluciones viables. Por tanto, el máximo es 276 con y .