Rama y corte

Ramificar y cortar ^[1] es un método de optimización combinatoria para resolver programas lineales enteros (ILP), es decir, problemas de programación lineal (LP) donde algunas o todas las incógnitas están restringidas a valores enteros . ^[2] Bifurcar y cortar implica ejecutar un algoritmo de bifurcación y enlace y utilizar planos de corte para ajustar las relajaciones de la programación lineal. Tenga en cuenta que si los cortes sólo se utilizan para reforzar la relajación LP inicial, el algoritmo se denomina corte y ramificación.

Algoritmo

Esta descripción supone que el ILP es un problema de maximización .

El método resuelve el programa lineal sin la restricción de números enteros utilizando el algoritmo simplex regular . Cuando se obtiene una solución óptima, y ​​esta solución tiene un valor no entero para una variable que se supone es entera, se puede usar un algoritmo de plano de corte para encontrar restricciones lineales adicionales que se satisfacen con todos los puntos enteros factibles pero que se violan con los puntos enteros factibles. solución fraccionaria actual. Estas desigualdades se pueden agregar al programa lineal, de modo que resolverlo producirá una solución diferente que, con suerte, será "menos fraccionaria".

En este punto, se inicia la parte de bifurcación y vinculación del algoritmo. El problema se divide en varias versiones (normalmente dos). Luego los nuevos programas lineales se resuelven utilizando el método simplex y se repite el proceso. Durante el proceso de ramificación y unión, las soluciones no integrales de las relajaciones LP sirven como límites superiores y las soluciones integrales sirven como límites inferiores. Un nodo se puede podar si un límite superior es más bajo que un límite inferior existente. Además, al resolver las relajaciones LP, se pueden generar planos de corte adicionales, que pueden ser cortes globales , es decir, válidos para todas las soluciones enteras factibles, o cortes locales , lo que significa que son satisfechos por todas las soluciones que cumplen las restricciones laterales de la solución actual. considerado rama y subárbol enlazado.

El algoritmo se resume a continuación.

1. Agregue el ILP inicial a la lista de problemas activos ${\displaystyle L}$
2. Establecer y ${\displaystyle x^{*}={\text{null}}}$ ${\displaystyle v^{*}=-\infty }$
3. mientras no esté vacío ${\displaystyle L}$
   1. Seleccionar y eliminar (eliminar de la cola) un problema de ${\displaystyle L}$
   2. Resuelva la relajación LP del problema.
   3. Si la solución no es factible, regrese a 3 (mientras). De lo contrario, denota la solución por con valor objetivo . ${\displaystyle x}$ ${\displaystyle v}$
   4. Si , regrese a 3. ${\displaystyle v\leq v^{*}}$
   5. Si es un número entero, configúrelo y regrese a 3. ${\displaystyle x}$ ${\displaystyle v^{*}\leftarrow v,x^{*}\leftarrow x}$
   6. Si lo desea, busque planos de corte que sean violados por . Si encuentra alguno, agréguelo al resto del LP y regrese a 3.2. ${\displaystyle x}$
   7. Ramificar para dividir el problema en nuevos problemas con regiones factibles restringidas. Agregue estos problemas y regrese a 3 ${\displaystyle L}$
4. devolver ${\displaystyle x^{*}}$

Pseudocódigo

En pseudocódigo similar a C++ , esto podría escribirse:

// Pseudocódigo de solución de rama y corte ILP, asumiendo que el objetivo debe maximizarseSolución_ILP sucursal_y_corte_ILP ( Problema_inicial del programa lineal entero ) {    cola lista_activa ; // L, arriba   lista_activa . poner en cola ( problema_inicial ); // paso 1  // paso 2 solución_ILP solución_óptima ; // esto mantendrá x* arriba   doble mejor_objetivo = - std :: límites_numéricos <doble> :: infinito ;​ // mantendrá v* arriba     while ( ! lista_activa . vacío ()) { // paso 3 arriba    LinearProgram & curr_prob = active_list . quitar la cola (); // paso 3.1     hacer { // pasos 3.2-3.7   ProgramaLinealRelajado & relajado_prob = LP_relax ( curr_prob ); // paso 3.2     LP_solution curr_relaxed_soln = LP_solve ( relajado_prob ); // esto es x arriba     bool planos_de_corte_encontrados = falso ;    if ( ! curr_relaxed_soln . is_factible ()) { // paso 3.3    continuar ; // prueba otra solución; continúa en el paso 3  } doble valor_objetivo_actual = curr_relaxed_soln . valor (); // v arriba     if ( valor_objetivo_actual <= mejor_objetivo ) { // paso 3.4      continuar ; // prueba otra solución; continúa en el paso 3  } if ( curr_relaxed_soln . is_integer ()) { // paso 3.5    mejor_objetivo = valor_objetivo_actual ;   solución_óptima = cast_as_ILP_solution ( curr_relaxed_soln );   continuar ; // continúa en el paso 3  } // la solución relajada actual no es integral if ( caza_de_aviones_de_corte ) { // paso 3.6    planos_de_corte_violados = buscar_planos_de_corte_violados ( curr_relaxed_soln );   if ( ! planos_de_corte_violados . vacío ()) { // paso 3.6    planos_de_corte_encontrados = verdadero ; // continuará en el paso 3.2    para ( auto && plano_de_corte : planos_de_corte_violados ) {      lista_activa . poner en cola ( LP_relax ( curr_prob , plano_de corte ));  } continuar ; // continúa en el paso 3.2  } } // paso 3.7: no se encontraron planos de corte violados o no los estábamos buscando auto && problemas_ramificados = partición_rama ( curr_prob );    para ( auto && rama : problemas_ramificados ) {      lista_activa . poner en cola ( rama ); } continuar ; // continúa en el paso 3  } while ( hunting_for_cutting_planes /* parámetro del algoritmo; ver 3.6 */    && planos_de_corte_encontrados );  // finaliza el paso 3.2 del ciclo do- while } // finaliza el paso 3 mientras bucle  devolver solución_óptima ; // etapa 4  }

En el pseudocódigo anterior, las funciones LP_relaxy llamadas LP_solvecomo branch_partitionsubrutinas deben proporcionarse según corresponda al problema. Por ejemplo, LP_solvese podría llamar al algoritmo simplex . Las estrategias de ramificación branch_partitionse analizan a continuación.

Estrategias de ramificación

Un paso importante en el algoritmo de bifurcación y corte es el paso de bifurcación. En este paso, se pueden utilizar diversas heurísticas de ramificación. Todas las estrategias de ramificación que se describen a continuación implican lo que se llama ramificación en una variable. ^[3] La ramificación en una variable implica elegir una variable, con un valor fraccionario, en la solución óptima a la relajación actual de LP y luego sumar las restricciones y ${\displaystyle x_{i}}$ ${\displaystyle x_{i}'}$ ${\displaystyle x_{i}\leq \left\lfloor x_{i}'\right\rfloor }$ ${\displaystyle x_{i}\geq \left\lceil x_{i}'\right\rceil }$

Ramificación más inviable

Esta estrategia de ramificación elige la variable con la parte fraccionaria más cercana a 0,5.

Pseudo ramificación de costos

La idea básica de esta estrategia es realizar un seguimiento para cada variable del cambio en la función objetivo cuando esta variable se eligió previamente como la variable a ramificar. Luego, la estrategia elige la variable que se predice que tendrá el mayor cambio en la función objetivo en función de los cambios pasados ​​cuando se eligió como variable de ramificación. Tenga en cuenta que la ramificación de pseudocostos inicialmente no proporciona información en la búsqueda, ya que se han ramificado pocas variables. ${\displaystyle x_{i}}$

Fuerte ramificación

Una bifurcación fuerte implica probar cuál de las variables candidatas ofrece la mejor mejora a la función objetivo antes de bifurcarse en ellas. La ramificación completa y fuerte prueba todas las variables candidatas y puede resultar costosa desde el punto de vista computacional. El costo computacional se puede reducir considerando solo un subconjunto de las variables candidatas y no resolviendo cada una de las relajaciones LP correspondientes hasta su finalización.

También hay una gran cantidad de variaciones de estas estrategias de bifurcación, como usar una bifurcación fuerte desde el principio, cuando la bifurcación de pseudocosto es relativamente poco informativa y luego cambiar a una bifurcación de pseudocosto más tarde, cuando hay suficiente historial de bifurcación para que el pseudocosto sea informativo.

Referencias

1. Padberg, Manfredo; Rinaldi, Giovanni (1991). "Un algoritmo de rama y corte para la resolución de problemas simétricos a gran escala del viajante de comercio". Revisión SIAM . 33 (1): 60-100. doi :10.1137/1033004. ISSN  0036-1445.
2. John E., Mitchell (2002). "Algoritmos de rama y corte para problemas de optimización combinatoria" (PDF) . Manual de optimización aplicada : 65–77.
3. Achterberg, Tobías; Koch, Thorsten; Martín, Alejandro (2005). "Revisión de las reglas de ramificación". Cartas de investigación operativa . 33 (1): 42–54. doi :10.1016/j.orl.2004.04.002.

enlaces externos

• Programación entera mixta
• SCIP: marco para corte y precio de sucursales y un solucionador de programación entera mixta
• ABACUS – Un sistema de sucursales y cortes – software de código abierto
• COIN-OR Cbc – software de código abierto en GitHub