Branch and bound ( BB , B&B o BnB ) es un paradigma de diseño de algoritmos para problemas de optimización discreta y combinatoria , así como optimización matemática . Un algoritmo de ramificación y acotación consiste en una enumeración sistemática de soluciones candidatas mediante la 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 ramasde 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 en 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 "rama y límite" apareció por primera vez en el trabajo de Little et al. sobre el problema del viajante . [4] [5]
Descripción general
El objetivo de un algoritmo de ramificación y límite 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 asume 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:
- Divide de forma recursiva el espacio de búsqueda en espacios más pequeños, luego minimiza f ( x ) en estos espacios más pequeños; la división se llama ramificación .
- La ramificación por sí sola equivaldría a una enumeración de fuerza bruta de soluciones candidatas y probarlas todas. Para mejorar el rendimiento de la búsqueda de fuerza bruta, un algoritmo B&B realiza un seguimiento de los límites del mínimo que está tratando de encontrar y usa estos límites para " podar " el espacio de búsqueda, eliminando las soluciones candidatas que puede probar que no contendrán. una solución óptima.
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 denomina instancia del problema. Denotar el conjunto de soluciones candidatas de una instancia que por S I . La representación de la instancia tiene que venir con tres operaciones:
- rama ( I ) produce dos o más instancias que representan cada uno un subconjunto de S I . (Por lo general, los subconjuntos están separados para evitar que el algoritmo visite la misma solución candidata dos veces, pero esto no es necesario. Sin embargo, una solución óptima entre S I debe estar contenida en al menos uno de los subconjuntos. [6] )
- unido ( I ) calcula un límite inferior en el valor de cualquier solución candidato en el espacio representado por I , es decir, unido ( I ) ≤ f ( x ) para todo x en S I .
- solution ( I ) determina si I representa una única solución candidata. (Opcionalmente, si no lo hace, la operación puede elegir volver alguna solución factible de entre S I . [6] ) Si la solución ( I ) devuelve una solución, entonces f (solución ( I )) proporciona un límite superior para el objetivo óptimo valor en todo el espacio de soluciones viables.
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 bifurcación. Al visitar una instancia I , comprueba si el límite ( I ) es mayor que un límite superior encontrado hasta ahora; si es así, puedo ser descartado de forma segura de la búsqueda y la recursión 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.
Versión genérica
El siguiente es el esqueleto de un algoritmo genérico de bifurcación y cota para minimizar una función objetiva arbitraria f . [3] Para obtener un algoritmo real a partir de esto, se requiere un límite de función delimitador , que calcula 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 presentado aquí es una función de orden superior .
- Usando una heurística , encuentre una solución x h al problema de optimización. Almacene su valor, B = f ( x h ) . (Si no hay una heurística disponible, establezca B en infinito). B denotará la mejor solución encontrada hasta ahora y se utilizará como límite superior en las soluciones candidatas.
- Inicialice una cola para contener una solución parcial sin ninguna de las variables del problema asignadas.
- Repita hasta que la cola esté vacía:
- Saque un nodo N de la cola.
- Si N representa una única solución candidato x y f ( x ) < B , entonces x es la mejor solución hasta el momento. Regístrelo y establezca B ← f ( x ) .
- De lo contrario, bifurque en N para producir nuevos nodos N i . Para cada uno de estos:
- Si límite ( N i )> B , no haga nada; dado que el límite inferior de este nodo es mayor que el límite superior del problema, nunca conducirá a la solución óptima y puede descartarse.
- De lo contrario, guarde N i en la cola.
Se pueden utilizar varias estructuras de datos de cola diferentes . Esta implementación basada en la cola FIFO produce una búsqueda en amplitud . Una pila (cola LIFO) producirá un algoritmo de profundidad . Se puede obtener un algoritmo de enlace y bifurcación del mejor primero mediante el uso de una cola de prioridad que ordena los nodos en su límite inferior. [3] Ejemplos de algoritmos de búsqueda del mejor primero con esta premisa son el algoritmo de Dijkstra y su descendiente A * search . La variante de profundidad primero se recomienda cuando no hay una buena heurística disponible para producir una solución inicial, porque rápidamente produce soluciones completas y, por lo tanto, límites superiores. [7]
Pseudocódigo
Una implementación de pseudocódigo similar a C ++ de lo anterior es:
// C ++ - como implementación de bifurcación y enlace, // asumiendo que la función objetivo f debe minimizarse Solución combinatoria branch_and_bound_solve ( Problema de problema combinatorio , ObjectiveFunction función_objetivo / * f * / , BoundingFunction lower_bound_function / * límite * / ) { // Paso 1 arriba double problem_upper_bound = std :: numeric_limits < doble > :: infinito ; // = B CombinatorialSolution heuristic_solution = heuristic_solve ( problema ); // x_h problem_upper_bound = objective_function ( heuristic_solution ); // B = f (x_h) CombinatorialSolution current_optimum = heuristic_solution ; // Paso 2 anterior cola < CandidateSolutionTree > candidato_queue ; // inicialización de la cola específica del problema candidato_queue = poblar_candidatos ( problema ); while ( ! candidato_queue . empty ()) { // Paso 3 anterior // Paso 3.1 Nodo CandidateSolutionTree = candidato_queue . pop (); // "nodo" representa N arriba if ( node . represent_single_candidate ()) { // Paso 3.2 si ( objective_function ( nodo . candidato ()) < problem_upper_bound ) { current_optimum = nodo . candidato (); problem_upper_bound = objective_function ( current_optimum ); } // si no, el nodo es un solo candidato que no es óptimo } else { // Paso 3.3: el nodo representa una rama de soluciones candidatas // "child_branch" representa N_i arriba para ( auto && child_branch : node . candidato_nodes ) { if ( lower_bound_function ( child_branch ) <= problem_upper_bound ) { candidato_queue . enqueue ( child_branch ); // Paso 3.3.2 } // en caso contrario, bound (N_i)> B para podar la rama; paso 3.3.1 } } } return 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
) y bound ( 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 o functores en el lenguaje de programación C ++, entre otros tipos de objetos invocables .
Mejoras
Cuándo es un vector de , los algoritmos de bifurcación y límite se pueden combinar con análisis de intervalo [8] y técnicas de contratista para proporcionar cerramientos garantizados del mínimo global. [9] [10]
Aplicaciones
Este enfoque se utiliza para una serie de problemas NP difíciles :
- Programación de enteros
- Programación no lineal
- Problema del vendedor ambulante (TSP) [4] [11]
- Problema de asignación cuadrática (QAP)
- Problema de satisfacción máxima (MAX-SAT)
- Búsqueda de vecino más cercano [12] (por Keinosuke Fukunaga )
- Programación de Flow Shop
- Problema de stock de corte
- Filogenética computacional
- Establecer inversión
- Estimación de parámetros
- 0/1 problema de mochila
- Establecer problema de portada
- Selección de funciones en el aprendizaje automático [13] [14]
- Predicción estructurada en visión por computadora [15] : 267–276
La ramificación y el límite también pueden ser la base de varias heurísticas . Por ejemplo, es posible que desee dejar de ramificar cuando el espacio entre los límites superior e inferior se vuelve más pequeño que un cierto umbral. 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 costo utilizada es ruidosa o es el resultado de estimaciones estadísticas y, por lo tanto, no se conoce con precisión, sino que solo se sabe que se encuentra dentro de un rango de valores con una probabilidad específica . [ cita requerida ]
Relación con otros algoritmos
Nau y col. presentan una generalización de bifurcación y cota que también subsume los algoritmos de búsqueda A * , B * y alfa-beta . [dieciséis]
Ver también
- Retroceso
- Ramificar y cortar , un híbrido entre los métodos de ramificación y encuadernación y el plano de corte que se utiliza ampliamente para resolver programas lineales enteros .
Referencias
- ^ AH Land y AG Doig (1960). "Un método automático para resolver problemas de programación discretos". Econometrica . 28 (3). págs. 497–520. doi : 10.2307 / 1910129 .
- ^ "Noticias del personal" . www.lse.ac.uk . Consultado el 8 de octubre de 2018 .
- ^ a b c Clausen, Jens (1999). Algoritmos de rama y delimitación: principios y ejemplos (PDF) (Informe técnico). Universidad de Copenhague . Archivado desde el original (PDF) el 23 de septiembre de 2015 . Consultado el 13 de agosto de 2014 .
- ^ a b Little, John DC; Murty, Katta G .; Sweeney, Dura W .; Karel, Caroline (1963). "Un algoritmo para el problema del viajante" (PDF) . Investigación operativa . 11 (6): 972–989. doi : 10.1287 / opre.11.6.972 . hdl : 1721,1 / 46828 .
- ^ Balas, Egon; Toth, Paolo (1983). Métodos de ramificación y encuadernación para el problema del viajante (PDF) (Informe). Escuela de Posgrado en Administración Industrial de la Universidad Carnegie Mellon . Archivado desde el original (PDF) el 20 de octubre de 2012.
- ^ a b Bader, David A .; Hart, William E .; Phillips, Cynthia A. (2004). "Diseño de algoritmos paralelos para rama y límite" (PDF) . En Greenberg, HJ (ed.). Tutoriales sobre metodologías emergentes y aplicaciones en investigación operativa . Prensa académica de Kluwer. Archivado desde el original (PDF) el 13 de agosto de 2017 . Consultado el 16 de septiembre de 2015 .
- ^ Mehlhorn, Kurt ; Sanders, Peter (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Saltador. pag. 249.
- ^ Moore, RE (1966). Análisis de intervalos . Englewood Cliff, Nueva Jersey: Prentice-Hall. ISBN 0-13-476853-1.
- ^ Jaulin, L .; Kieffer, M .; Didrit, O .; Walter, E. (2001). Análisis de intervalo aplicado . Berlín: Springer. ISBN 1-85233-219-0.
- ^ Hansen, ER (1992). Optimización global mediante análisis de intervalos . Nueva York: Marcel Dekker.
- ^ Conway, Richard Walter; Maxwell, William L .; Miller, Louis W. (2003). Teoría de la programación . Publicaciones de Courier Dover. págs. 56–61 .
- ^ Fukunaga, Keinosuke; Narendra, Patrenahalli M. (1975). "Un algoritmo de bifurcación y límite para calcular k -vecinos más cercanos". Transacciones IEEE en computadoras : 750–753. doi : 10.1109 / tc.1975.224297 .
- ^ Narendra, Patrenahalli M .; Fukunaga, K. (1977). "Un algoritmo de ramificación y límite para la selección de subconjuntos de características" (PDF) . Transacciones IEEE en computadoras . C-26 (9): 917–922. doi : 10.1109 / TC.1977.1674939 .
- ^ Hazimeh, Hussein; Mazumder, Rahul; Saab, Ali (2020). "Regresión dispersa a escala: ramificación y límite arraigada en la optimización de primer orden". arXiv : 2004.06152 .
- ^ Nowozin, Sebastian; Lampert, Christoph H. (2011). "Aprendizaje estructurado y predicción en visión artificial". Fundamentos y Tendencias en Computación Gráfica y Visión . 6 (3–4): 185–365. CiteSeerX 10.1.1.636.2651 . doi : 10.1561 / 0600000033 . ISBN 978-1-60198-457-9.
- ^ Nau, Dana S .; Kumar, Vipin; Kanal, Laveen (1984). "Ramificación general y cota, y su relación con A ∗ y AO ∗" (PDF) . Inteligencia artificial . 23 (1): 29–58. doi : 10.1016 / 0004-3702 (84) 90004-3 .
enlaces externos
- LiPS : programa GUI gratuito y fácil de usar destinado a resolver problemas de programación lineal, de enteros y de objetivos.
- Cbc - (Coin-or branch and cut) es un solucionador de programación de enteros mixtos de código abierto escrito en C ++.