Ramificar y enlazar

El método de ramificación y acotación ( BB , B&B o BnB ) es un método para resolver problemas de optimización que consiste en dividirlos en subproblemas más pequeños y utilizar una función de acotación para eliminar los subproblemas que no pueden contener la solución óptima.

Se trata de 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 : el conjunto de soluciones candidatas se concibe como un árbol con raíz , donde se encuentra el conjunto completo.

El algoritmo explora las ramas de este árbol, que representan subconjuntos del conjunto de soluciones. Antes de enumerar las soluciones candidatas de una rama, esta se compara con los límites estimados superior e inferior de la solución óptima y se descarta si no puede generar una solución mejor que la mejor encontrada hasta el momento por el algoritmo.

El algoritmo depende de una estimación eficiente de los límites inferior y superior de las regiones/ramas del espacio de búsqueda. Si no se dispone de límites, el algoritmo se reduce 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 problemas de optimización NP-difíciles . ^{[ 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 ]}

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 real f ( x ) , llamada función objetivo , dentro de 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 asume que se desea minimizar f ( x ) ; esta suposición no implica pérdida de generalidad , ya que se puede encontrar el valor máximo de f ( x ) hallando el mínimo de g ( x ) = −f ( x ) . Un algoritmo de ramificación y acotación opera 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; esta división se llama ramificación .
• La ramificación por sí sola equivaldría a una enumeración por fuerza bruta de las soluciones candidatas y a probarlas todas. Para mejorar el rendimiento de la búsqueda por fuerza bruta, un algoritmo B&B realiza un seguimiento 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 puede demostrar que no contienen una solución óptima.

Para convertir estos principios en un algoritmo concreto para un problema de optimización específico, se requiere 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:

• La rama ( I ) produce dos o más instancias, cada una de las cuales representa 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 una cota inferior sobre 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 .
• solution( I ) determina si I representa una única solución candidata. (Opcionalmente, si no lo hace, la operación puede optar por devolver alguna solución factible de entre S _I . ^{[ 6 ]} ) Si solution( I ) devuelve una solución, entonces f (solution( I )) proporciona una cota superior para el valor óptimo de la función objetivo en todo el espacio de soluciones factibles.

Mediante estas operaciones, un algoritmo B&B realiza una búsqueda recursiva descendente a través del árbol de instancias formado por la operación de ramificación. Al visitar una instancia I , comprueba si bound( I ) es igual o mayor que el límite superior actual; de ser así, I puede descartarse de la búsqueda y la recursión se detiene. Este paso de poda se suele implementar manteniendo una variable global que registra el límite superior mínimo observado entre todas las instancias examinadas hasta el momento.

// Implementación de ramificación y acotación al estilo C++,// suponiendo que la función objetivo f debe minimizarseSolución combinatoria ramificación y acotación (Problema combinatorio ,FunciónObjetivo función_objetivo / *f*/ ,Función de límite inferior función de límite inferior /*límite*/ ){// Paso 1 anterior.double problem_upper_bound = std :: numeric_limits <double> :: infinity ; // = BCombinatorialSolution solución_heurística = solución_heurística ( problema ); // x_hproblem_upper_bound = objective_function ( heuristic_solution ); // B = f(x_h)CombinatorialSolution current_optimum = heuristic_solution ;// Paso 2 anteriorcola < Árbol de soluciones candidatas > cola_candidata ;// Inicialización de cola específica para el problemacola_candidatos = poblar_candidatos ( problema );while ( ! candidate_queue . empty ()) { // Paso 3 anterior// Paso 3.1nodo del árbol de soluciones candidatas = cola_candidata.pop () ;// "nodo" representa N arribaif ( node . representation_single_candidate ()) { // Paso 3.2si ( función_objetivo ( nodo . candidato ()) < límite_superior_problema ) {current_optimum = nodo.candidato ( ) ;problem_upper_bound = objective_function ( current_optimum );}// De lo contrario, el nodo es un único candidato, lo cual no es óptimo.}else { // Paso 3.3: el nodo representa una rama de soluciones candidatas// "child_branch" representa N_i arribapara ( auto && child_branch : node . candidate_nodes ) {si ( lower_bound_function ( child_branch ) <= problem_upper_bound ) {cola_candidato.encola ( rama_hija ) ; // Paso 3.3.2}// De lo contrario, bound(N_i) > B, por lo que podamos la rama; paso 3.3.1}}}devolver current_optimum ;}

Este enfoque se utiliza para varios problemas NP-difíciles :

• Programación entera
• Programación no lineal
• Problema del viajante (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 talleres de flujo
• Problema con el material de corte
• Filogenética computacional
• Inversión de conjuntos
• Estimación de parámetros
• Problema de la mochila 0/1
• Problema de la cubierta del conjunto
• Selección de características en aprendizaje automático ^{[ 13 ] [ 14 ]}
• Predicción estructurada en visión por computadora ^{[ 15 ] : 267–276}
• Problema de enrutamiento de arcos , incluyendo el problema del cartero chino.
• Problema de programación de talentos y organización de escenas de rodaje

El método de ramificación y acotación también puede servir de base para diversas heurísticas . Por ejemplo, se puede optar por detener la ramificación cuando la diferencia 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 considerablemente los cálculos necesarios. Este tipo de solución es especialmente aplicable cuando la función de coste 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 .

Nau et al. presentan una generalización del método de ramificación y acotación que también engloba los algoritmos de búsqueda A* , B* y alfa-beta . ^{[ 16 ]}

El método de ramificación y acotación se puede utilizar para maximizar${\displaystyle Z=5x_{1}+6x_{2}}$con las restricciones

${\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${\displaystyle x_{2}}$son números enteros.

El primer paso es relajar la restricción de enteros. Tenemos dos puntos extremos para la primera ecuación que forman una línea:${\displaystyle {\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}50\\0\end{bmatrix}}}$y${\displaystyle {\begin{bmatrix}0\\50\end{bmatrix}}}$Podemos formar la segunda línea con los puntos vectoriales${\displaystyle {\begin{bmatrix}0\\40\end{bmatrix}}}$y${\displaystyle {\begin{bmatrix}70\\0\end{bmatrix}}}$.

El tercer punto es${\displaystyle {\begin{bmatrix}0\\0\end{bmatrix}}}$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 usando reducción de filas, que es${\displaystyle {\begin{bmatrix}70/3\\80/3\end{bmatrix}}}$con un valor de 276 + 2/3. Probamos los otros extremos recorriendo la línea sobre la región y encontramos que este es el máximo sobre los números reales.

Elegimos la variable con la parte fraccionaria máxima, en este caso${\displaystyle x_{2}}$se convierte en el parámetro para el método de ramificación y acotación. Ramificamos a${\displaystyle x_{2}\leq 26}$y obtener 276 en${\displaystyle \langle 24,26\rangle }$Hemos alcanzado una solución entera, así que pasamos a la otra rama.${\displaystyle x_{2}\geq 27}$. Obtenemos 275.75 en${\displaystyle \langle 22.75,27\rangle }$Tenemos un decimal, así que hacemos una bifurcación.${\displaystyle x_{1}}$a${\displaystyle x_{1}\leq 22}$y encontramos 274.571 en${\displaystyle \langle 22,27.4286\rangle }$Probamos la otra rama.${\displaystyle x_{1}\geq 23}$y no hay soluciones factibles. Por lo tanto, el máximo es 276 con${\displaystyle x_{1}=24}$y${\displaystyle x_{2}=26}$.

• Retroceder
• El método de ramificación y corte es un híbrido entre el método de ramificación y acotación y el método del plano de corte , que se utiliza ampliamente para resolver programas lineales enteros .
• Algoritmo evolutivo
• Poda alfa-beta

• LiPS : programa gratuito con interfaz gráfica de usuario (GUI) fácil de usar, diseñado para resolver problemas de programación lineal, entera y por objetivos.
• Cbc – (Coin-or branch and cut) es un solucionador de programación entera mixta de código abierto escrito en C++.