Rama y atado

Optimización mediante la eliminación de soluciones no óptimas a subproblemas.

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]}

Descripción general

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:

• Divide recursivamente el espacio de búsqueda en espacios más pequeños y 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 enumerar por fuerza bruta las soluciones candidatas y probarlas todas. Para mejorar el rendimiento de la búsqueda de fuerza bruta, un algoritmo de B&B realiza un seguimiento de los límites mínimos que intenta encontrar y utiliza estos límites para " podar " el espacio de búsqueda, eliminando soluciones candidatas que puede demostrar 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. 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:

• Branch( I ) produce dos o más instancias y cada una representa un subconjunto de S _I . (Por lo general, los subconjuntos son disjuntos 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] )
• límite( I ) calcula un límite inferior en el valor de cualquier solución candidata en el espacio representado por I , es decir, límite( I ) ≤ f ( x ) para todo x en S _I .
• solución( I ) determina si I representa una única solución candidata. (Opcionalmente, si no es así, la operación puede optar por devolver alguna solución factible 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 factibles.

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.

Versión genérica

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 .

1. 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 heurística disponible, establezca B en infinito). B denotará la mejor solución encontrada hasta el momento y se utilizará como límite superior en las soluciones candidatas.
2. Inicialice una cola para contener una solución parcial sin ninguna de las variables del problema asignada.
3. Repita hasta que la cola esté vacía:
   1. Saque un nodo N de la cola.
   2. Si N representa una única solución candidata x y f ( x ) < B , entonces x es la mejor solución hasta el momento. Regístrelo y establezca B ← f ( x ) .
   3. _{De lo} contrario, bifurquese en N para producir nuevos nodos Ni . Para cada uno de estos:
      1. Si está enlazado ( 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.
      2. _{De lo contrario} , almacene Ni en la cola.

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]

Pseudocódigo

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_solvey populate_candidatesllamadas como subrutinas deben proporcionarse según corresponda al problema. Las funciones f ( objective_function) ybound ( ) lower_bound_functionse 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++.

Mejoras

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]} ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbb {R} ^{n}}$

Aplicaciones

Este enfoque se utiliza para una serie de problemas NP-difíciles :

• programación entera
• Programación no lineal
• Problema del viajante de comercio (TSP) ^{[4] [11]}
• Problema de asignación cuadrática (QAP)
• Problema de máxima satisfacibilidad (MAX-SAT)
• Búsqueda de vecino más cercano ^[12] (por Keinosuke Fukunaga )
• Programación de taller de flujo
• Problema de corte de stock
• 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 aprendizaje automático ^{[13] [14]}
• Predicción estructurada en visión por computadora ^{[15] : 267–276}
• Problema de enrutamiento de arco , incluido el problema del cartero chino
• Programación de talentos , problema de disposición de rodaje de escenas.

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 ]}

Relación con otros algoritmos

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]

Ejemplo de optimización

Branch andbound se puede utilizar para resolver este problema.

Maximizar con estas restricciones ${\displaystyle Z=5x_{1}+6x_{2}}$

${\displaystyle x_{1}+x_{2}\leq 50}$

${\displaystyle 4x_{1}+7x_{2}\leq 280}$

${\displaystyle x_{1},x_{2}\geq 0}$

${\displaystyle x_{1}}$y son números enteros. ${\displaystyle x_{2}}$

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 . ${\displaystyle {\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}50\\0\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}0\\50\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}0\\40\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}70\\0\end{bmatrix}}}$

las dos líneas.

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. ${\displaystyle {\begin{bmatrix}0\\0\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}70/3\\80/3\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}23.333\\26.667\end{bmatrix}}}$

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 . ${\displaystyle x_{2}}$ ${\displaystyle x_{2}\leq 26}$ ${\displaystyle \langle 24,26\rangle }$ ${\displaystyle x_{2}\geq 27}$ ${\displaystyle \langle 22.75,27\rangle }$ ${\displaystyle x_{1}}$ ${\displaystyle x_{1}\leq 22}$ ${\displaystyle \langle 22,27.4286\rangle }$ ${\displaystyle x_{1}\geq 23}$ ${\displaystyle x_{1}\longmapsto 24}$ ${\displaystyle x_{2}\longmapsto 26}$

Ver también

• Retroceder
• Ramificar y cortar , un híbrido entre los métodos de ramificar y enlazar y del plano de corte que se utiliza ampliamente para resolver programas lineales enteros .
• Algoritmos evolutivos
• Poda alfa-beta

Referencias

1. AH Land y AG Doig (1960). "Un método automático para resolver problemas de programación discreta". Econométrica . 28 (3): 497–520. doi :10.2307/1910129. JSTOR  1910129.
2. "Noticias del personal". www.lse.ac.uk.​ Archivado desde el original el 24 de febrero de 2021 . Consultado el 8 de octubre de 2018 .
3. Clausen, Jens (1999). Algoritmos de rama y enlace: principios y ejemplos (PDF) (Reporte técnico). Universidad de Copenhague . Archivado desde el original (PDF) el 23 de septiembre de 2015 . Consultado el 13 de agosto de 2014 .
4. Pequeño, John DC; Murty, Katta G.; Sweeney, Dura W.; Karel, Carolina (1963). "Un algoritmo para el problema del viajante" (PDF) . La investigación de operaciones . 11 (6): 972–989. doi :10.1287/opre.11.6.972. hdl : 1721.1/46828 .
5. Balas, Egon; Toth, Paolo (1983). Métodos de ramificación y encuadernación para el problema del viajante (PDF) (Reporte). Escuela de Graduados en Administración Industrial de la Universidad Carnegie Mellon . Archivado (PDF) desde el original el 20 de octubre de 2012.
6. Bader, David A.; Hart, William E.; Phillips, Cynthia A. (2004). "Diseño de algoritmos paralelos para bifurcación y enlace" (PDF) . En Greenberg, HJ (ed.). Tutoriales sobre metodologías y aplicaciones emergentes en investigación de operaciones . Prensa académica de Kluwer. Archivado desde el original (PDF) el 13 de agosto de 2017 . Consultado el 16 de septiembre de 2015 .
7. Mehlhorn, Kurt ; Lijadoras, Peter (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Saltador. pag. 249.
8. Moore, RE (1966). Análisis de intervalos . Englewood Cliff, Nueva Jersey: Prentice-Hall. ISBN 0-13-476853-1.
9. Jaulín, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001). Análisis de intervalos aplicado . Berlín: Springer. ISBN 1-85233-219-0.
10. Hansen, ER (1992). Optimización global mediante análisis de intervalos . Nueva York: Marcel Dekker.
11. Conway, Richard Walter ; Maxwell, William L .; Molinero, Louis W. (2003). Teoría de la Programación . Publicaciones de Courier Dover. págs. 56–61.
12. Fukunaga, Keinosuke; Narendra, Patrenahalli M. (1975). "Un algoritmo de rama y límite para calcular k vecinos más cercanos". Transacciones IEEE en computadoras (7): 750–753. doi :10.1109/tc.1975.224297. S2CID  5941649.
13. Narendra, Patrenahalli M.; Fukunaga, K. (1977). "Un algoritmo de bifurcación y vinculación para la selección de subconjuntos de funciones" (PDF) . Transacciones IEEE en computadoras . C-26 (9): 917–922. doi :10.1109/TC.1977.1674939. S2CID  26204315.
14. Hazimeh, Hussein; Mazumder, Rahul; Saab, Ali (2020). "Regresión dispersa a escala: ramificación y límite basada en la optimización de primer orden". arXiv : 2004.06152 [estad.CO].
15. Nowozin, Sebastián; Lampert, Christoph H. (2011). "Aprendizaje estructurado y predicción en visión por computadora". Fundamentos y Tendencias en Visión y Gráfica por Computadora . 6 (3–4): 185–365. CiteSeerX 10.1.1.636.2651 . doi :10.1561/0600000033. ISBN  978-1-60198-457-9.
16. Nau, Dana S.; Kumar, VIPIN; Canal, Laveen (1984). "Rama general y encuadernado, 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, entera y por objetivos.
• Cbc – (Moneda o rama y corte) es un solucionador de programación entera mixta de código abierto escrito en C++.