stringtranslate.com

Rama y límite

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:

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:

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 Bf ( 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]

Aplicaciones

Este enfoque se utiliza para una serie de problemas NP-hard :

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

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 línea: y . Podemos formar la segunda línea con los puntos vectoriales y .

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.

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 .

Véase también

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. ^ abc 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. ^ ab 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. ^ ab 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