Rama y límite

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

El algoritmo de ramificación y acotación ( 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 de acotación 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 para la optimización matemática . Un algoritmo de ramificación y acotación consiste en una enumeración sistemática de soluciones candidatas mediante una búsqueda en el espacio de estados : se piensa que el conjunto de soluciones candidatas forma un árbol con raíz con el conjunto completo en la raíz. El algoritmo explora las ramas de este árbol, que representan subconjuntos del conjunto de soluciones. Antes de enumerar las soluciones candidatas de una rama, la rama se verifica con los límites superior e inferior estimados en la solución óptima, y ​​se descarta si no puede producir una mejor solución que la mejor encontrada hasta el momento 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 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 problemas de optimización NP-hard . ^[3] El nombre "ramificación y acotación" apareció por primera vez en el trabajo de Little et al. sobre el problema del viajante de comercio . ^{[4] [5]}

Descripción general

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 un 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 se realiza sin pérdida de generalidad , ya que se puede encontrar el valor máximo de f ( x ) al encontrar el mínimo de g ( x ) = − f ( x ) . Un algoritmo de ramificación y acotación funciona de acuerdo con 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 una enumeración por fuerza bruta de soluciones candidatas y a una prueba de todas ellas. Para mejorar el rendimiento de la búsqueda por fuerza bruta, un algoritmo B&B lleva un registro de los límites del mínimo que intenta encontrar y utiliza estos límites para " podar " el espacio de búsqueda, eliminando las soluciones candidatas que pueda demostrar que no contendrán una solución óptima.

Para convertir estos principios en un algoritmo concreto para un problema de optimización específico se necesita algún tipo de estructura de datos que represente conjuntos de soluciones candidatas. Dicha 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 incluir tres operaciones:

• branch( I ) produce dos o más instancias que representan cada una un subconjunto de S _I . (Normalmente, los subconjuntos son disjuntos para evitar que el algoritmo visite la misma solución candidata dos veces, pero esto no es obligatorio. Sin embargo, una solución óptima entre S _I debe estar contenida en al menos uno de los subconjuntos. ^[6] )
• bound( I ) calcula un límite inferior para el valor de cualquier solución candidata en el espacio representado por I , es decir, bound( I ) ≤ f ( x ) para todo x en S _I .
• solución( I ) determina si I representa una única solución candidata. (Opcionalmente, si no lo hace, la operación puede elegir devolver alguna solución factible entre S _I . ^[6] ) Si solución( I ) devuelve una solución, entonces f (solución( I )) proporciona un límite superior para el valor objetivo óptimo sobre todo el espacio de soluciones factibles.

Mediante 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 ramificación. Al visitar una instancia I , verifica si bound( I ) es igual o mayor que el límite superior actual; si es así, I puede descartarse 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 observado entre todas las instancias examinadas hasta el momento.

Versión genérica

El siguiente es el esqueleto de un algoritmo genérico de ramificación y acotación para minimizar una función objetivo arbitraria f . ^[3] Para obtener un algoritmo real a partir de esto, se requiere una función de acotación bound , 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 presentado aquí es una función de orden superior .

1. Utilizando una heurística , encuentre una solución x _h para el problema de optimización. Almacene su valor, B = f ( x _h ) . (Si no hay ninguna heurística disponible, establezca B en infinito). B indicará la mejor solución encontrada hasta el momento y se utilizará como límite superior de las soluciones candidatas.
2. Inicializar una cola para contener una solución parcial sin ninguna de las variables del problema asignadas.
3. Repetir hasta que la cola esté vacía:
   1. Quitar 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ístrela y establezca B ← f ( x ) .
   3. En caso contrario, se ramifica en N para producir nuevos nodos N _i . Para cada uno de estos:
      1. Si bound( 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 N _i en la cola.

Se pueden utilizar varias estructuras de datos de cola diferentes. Esta implementación basada en cola FIFO produce una búsqueda en amplitud . Una pila (cola LIFO) producirá un algoritmo en profundidad . Se puede obtener un algoritmo de ramificación y acotación de mejor primero utilizando una cola de prioridad que ordena los nodos en su límite inferior. ^[3] Ejemplos de algoritmos de búsqueda de 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 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 ramificación y límite,// suponiendo que se debe minimizar la función objetivo fSolución combinatoria branch_and_bound_solve (  Problema combinatorio ,   ObjetivoFunción función_objetivo /*f*/ ,   Función delimitadora función_límite_inferior /*límite*/ )   { // Paso 1 arriba. doble problema_límite_superior = std :: límites_numéricos < double >:: infinito ; // = B     Solución Combinatoria solución_heurística = solución_heurística ( problema ); // x_h     límite_superior_del_problema = función_objetivo ( solución_heurística ); // B = f(x_h)    Solución Combinatoria current_optimum = solución_heurística ;    // Paso 2 arriba cola < CandidateSolutionTree > cola_de_candidatos ;  // inicialización de cola específica del problema cola_de_candidatos = rellenar_candidatos ( problema );   while ( ! candidate_queue . empty ()) { // Paso 3 anterior    // Paso 3.1 nodo CandidateSolutionTree = candidate_queue . pop ();    // "nodo" representa N arriba if ( nodo . representa_candidato_único ()) { // Paso 3.2    si ( función_objetivo ( nodo . candidato ()) < límite_superior_problema ) {     current_optimum = nodo.candidato ( ) ;   problema_límite_superior = función_objetivo ( óptimo_actual );   } // de lo contrario, el nodo es un único 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 && rama_hija : nodo . nodos_candidatos ) {      si ( función_límite_inferior ( rama_secundaria ) <= límite_superior_problema ) {     candidate_queue . enqueue ( child_branch ); // Paso 3.3.2  } // de lo contrario, bound(N_i) > B por lo que podamos la rama; paso 3.3.1 } } } devuelve actual_optimo ; }

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) 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 y otros tipos de objetos invocables en el lenguaje de programación C++.

Mejoras

Cuando es un vector de , los algoritmos de ramificación y acotación se pueden combinar con el análisis de intervalos ^[8] y técnicas de contratistas 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-hard :

• Programación de números enteros
• 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 del vecino más cercano ^[12] (por Keinosuke Fukunaga )
• Programación de taller de flujo
• Problema de corte de stock
• Filogenética computacional
• Inversión de conjuntos
• Estimación de parámetros
• Problema de la mochila 0/1
• Problema con la cubierta del conjunto
• Selección de características en el aprendizaje automático ^{[13] [14]}
• Predicción estructurada en visión artificial ^{[15] : 267–276}
• Problema de enrutamiento de arco , incluido el problema del cartero chino
• Problema de programación de talentos y organización de escenas de rodaje

La ramificación y acotación también puede ser la base de varias heurísticas . Por ejemplo, se puede querer detener la ramificación cuando la brecha entre los límites superior e inferior se vuelve más pequeña 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 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 et al. presentan una generalización de ramificación y acotación que también incluye los algoritmos de búsqueda A* , B* y alfa-beta . ^[16]

Ejemplo de optimización

Se puede utilizar la ramificación y el límite 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 línea: 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 lineas.

El tercer punto es . Esta es una región de envoltura convexa , por lo que la solución se encuentra en uno de los vértices de la región. Podemos encontrar la intersección mediante la reducción de filas, que es , o con un valor de 276,667. Probamos los otros puntos finales barriendo la región con la línea y descubrimos que este es el máximo sobre los números 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 ramificación y acotación. Nos ramificamos a y obtenemos 276 @ . Hemos alcanzado una solución entera, por lo que nos movemos a la otra rama . Obtenemos 275,75 @ . Tenemos un decimal, por lo que nos ramificamos a y encontramos 274,571 @ . Probamos la otra rama y no hay soluciones factibles. Por lo 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}$

Véase también

• Retrocediendo
• Ramificación y corte , un híbrido entre los métodos de ramificación y acotación y de plano de corte que se utiliza ampliamente para resolver programas lineales enteros .
• Algoritmo evolutivo
• Poda alfa-beta

Referencias

1. AH Land y AG Doig (1960). "Un método automático para resolver problemas de programación discreta". Econometrica . 28 (3): 497–520. doi :10.2307/1910129. JSTOR  1910129.
2. "Staff News". 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 ramificación y acotació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 .
4. Little, John DC; Murty, Katta G.; Sweeney, Dura W.; Karel, Caroline (1963). "Un algoritmo para el problema del viajante de comercio" (PDF) . 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 acotación para el problema del viajante de comercio (PDF) (Informe). Facultad de 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 ramificación y acotación" (PDF) . En Greenberg, HJ (ed.). Tutoriales sobre metodologías emergentes y aplicaciones en investigación de operaciones . Kluwer Academic Press. Archivado desde el original (PDF) el 2017-08-13 . Consultado el 2015-09-16 .
7. Mehlhorn, Kurt ; Sanders, Peter (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Springer. pág. 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. ; Miller, Louis W. (2003). Teoría de la programación . Courier Dover Publications. págs. 56–61.
12. Fukunaga, Keinosuke; Narendra, Patrenahalli M. (1975). "Un algoritmo de ramificación y acotación para calcular k vecinos más cercanos". IEEE Transactions on Computers (7): 750–753. doi :10.1109/tc.1975.224297. S2CID  5941649.
13. Narendra, Patrenahalli M.; Fukunaga, K. (1977). "Un algoritmo de ramificación y acotación para la selección de subconjuntos de características" (PDF) . IEEE Transactions on Computers . 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 acotación basada en optimización de primer orden". arXiv : 2004.06152 [stat.CO].
15. Nowozin, Sebastian; Lampert, Christoph H. (2011). "Aprendizaje estructurado y predicción en visión artificial". Fundamentos y tendencias en gráficos y visión artificial . 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; Kanal, Laveen (1984). "Rama y límite general, 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 diseñado para resolver problemas de programación lineal, entera y de objetivos.
• Cbc – (Coin-or branch and cut) es un solucionador de programación entera mixta de código abierto escrito en C++.