stringtranslate.com

Ramificar y cortar

Branch and cut [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] Branch and cut implica ejecutar un algoritmo de ramificación y acotación y usar planos de corte para ajustar las relajaciones de programación lineal. Tenga en cuenta que si los cortes solo se utilizan para ajustar la relajación inicial de LP, el algoritmo se llama cut and branch.

Algoritmo

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

El método resuelve el programa lineal sin la restricción de 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 que es entera, se puede utilizar un algoritmo de plano de corte para encontrar restricciones lineales adicionales que sean satisfechas por todos los puntos enteros factibles pero violadas por la solución fraccionaria actual. Estas desigualdades se pueden agregar al programa lineal, de modo que su resolución produzca una solución diferente que, con suerte, sea "menos fraccionaria".

En este punto, se inicia la parte de ramificación y acotación del algoritmo. El problema se divide en múltiples versiones (normalmente dos). A continuación, los nuevos programas lineales se resuelven utilizando el método símplex y el proceso se repite. Durante el proceso de ramificación y acotación, las soluciones no integrales de las relajaciones de LP sirven como límites superiores y las soluciones integrales sirven como límites inferiores. Se puede podar un nodo si un límite superior es inferior a un límite inferior existente. Además, al resolver las relajaciones de 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 se satisfacen por todas las soluciones que cumplen las restricciones laterales del subárbol de rama y acotación considerado actualmente.

El algoritmo se resume a continuación.

  1. Añade el ILP inicial a , la lista de problemas activos
  2. Establecer y
  3. mientras no esté vacío
    1. Seleccionar y eliminar (quitar de la cola) un problema de
    2. Resuelva la relajación LP del problema.
    3. Si la solución no es factible, retroceda al punto 3 (mientras tanto). En caso contrario, denote la solución con un valor objetivo .
    4. Si , vuelve al paso 3.
    5. Si es entero, establezca y vuelva a 3.
    6. Si lo desea, busque los planos de corte que viole . Si encuentra alguno, agréguelo a la relajación de LP y vuelva a 3.2.
    7. Ramifica para dividir el problema en nuevos problemas con regiones factibles restringidas. Agrega estos problemas y vuelve a 3
  4. devolver

Pseudocódigo

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

// Pseudocódigo de solución de corte y ramificación ILP, asumiendo que se quiere maximizar el objetivoSolución ILP rama_y_corte_ILP ( Programa Lineal Entero problema_inicial ) {    cola lista_activa ; // L, arriba   lista_activa . enqueue ( problema_inicial ); // paso 1  // paso 2 ILP_solution optimal_solution ; // esto mantendrá x* arriba   double best_objective = - std :: numeric_limits < double >:: infinity ; // mantendrá v* por encima     while ( ! active_list . empty ()) { // paso 3 anterior    LinearProgram & curr_prob = active_list . dequeue (); // 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 ( relaxed_prob ); // esto es x arriba     bool planos_de_corte_encontrados = falso ;    si ( ! curr_relaxed_soln . is_feasible ()) { // paso 3.3    continuar ; // probar otra solución; continúa en el paso 3  } doble valor_objetivo_actual = sol_relajada_actual . valor (); // v arriba     si ( valor_objetivo_actual <= mejor_objetivo ) { // paso 3.4      continuar ; // probar otra solución; continúa en el paso 3  } si ( curr_relaxed_soln . is_integer ()) { // paso 3.5    mejor_objetivo = valor_objetivo_actual ;   solución_óptima = convertir_en_solución_ILP ( solución_relajada_actual );   continuar ; // continúa en el paso 3  } // la solución relajada actual no es integral if ( caza_de_planos_de_corte ) { // paso 3.6    planos_de_corte_violados = búsqueda_de_planos_de_corte_violados ( sol_relajada_actual );   if ( ! violated_cutting_planes . empty ()) { // paso 3.6    Cutting_planes_found = true ; // continuará en el paso 3.2    para ( automático y plano de corte : planos de corte violados ) {      lista_activa .enqueue ( 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 ( problema_actual );    para ( auto && rama : problemas_ramificados ) {      active_list . enqueue ( rama ); } continuar ; // continúa en el paso 3  } while ( hunting_for_cutting_planes /* parámetro del algoritmo; ver 3.6 */    && planos_de_corte_encontrados );  // Fin del paso 3.2 del bucle do-while } // Fin del paso 3 del bucle while  devolver solución_óptima ; // paso 4  }

En el pseudocódigo anterior, las funciones LP_relax, LP_solvey branch_partitionllamadas como subrutinas deben proporcionarse según correspondan al problema. Por ejemplo, LP_solvese podría llamar al algoritmo simplex . branch_partitionA continuación se analizan las estrategias de ramificación para .

Estrategias de ramificación

Un paso importante en el algoritmo de ramificación y corte es el paso de ramificación. En este paso, hay una variedad de heurísticas de ramificación que se pueden utilizar. 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 de PL actual y luego agregar las restricciones y

La ramificación más inviable
Esta estrategia de ramificación elige la variable con la parte fraccionaria más cercana a 0,5.
Ramificación de pseudocostos
La idea básica de esta estrategia es hacer un seguimiento de cada variable y del cambio en la función objetivo cuando esta variable se eligió previamente como variable de ramificación. 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 anteriores cuando se eligió como variable de ramificación. Tenga en cuenta que la ramificación de pseudocosto inicialmente no es informativa en la búsqueda, ya que se han ramificado pocas variables.
Fuerte ramificación
La ramificación fuerte implica probar cuál de las variables candidatas ofrece la mejor mejora para la función objetivo antes de realizar la ramificación en ellas. La ramificación fuerte completa prueba todas las variables candidatas y puede ser 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 de PL correspondientes hasta el final.

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

Referencias

  1. ^ Padberg, Manfred; Rinaldi, Giovanni (1991). "Un algoritmo de ramificación y corte para la resolución de problemas de viajante de comercio simétricos a gran escala". SIAM Review . 33 (1): 60–100. doi :10.1137/1033004. ISSN  0036-1445.
  2. ^ John E., Mitchell (2002). "Algoritmos de ramificación y corte para problemas de optimización combinatoria" (PDF) . Manual de optimización aplicada : 65–77.
  3. ^ Achterberg, Tobias; Koch, Thorsten; Martin, Alexander (2005). "Reglas de ramificación revisadas". Operations Research Letters . 33 (1): 42–54. doi :10.1016/j.orl.2004.04.002.

Enlaces externos