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] Ramificar y cortar implica ejecutar un algoritmo de ramificación y encuadernació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 apretar la relajación LP inicial, el algoritmo se llama corte y bifurcación.
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 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 que es entera, se puede usar un algoritmo de plano de corte para encontrar restricciones lineales adicionales que son satisfechas por todos los puntos enteros factibles pero violadas por la solución fraccionaria actual. Estas desigualdades pueden agregarse al programa lineal, de modo que resolverlo producirá una solución diferente que, con suerte, es "menos fraccional".
En este punto, se inicia la rama y la parte acotada del algoritmo. El problema se divide en varias 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 para las relajaciones 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 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 están satisfechos por todas las soluciones que cumplen con las restricciones laterales de la actual rama considerada y subárbol ligado.
El algoritmo se resume a continuación.
- Agregue el ILP inicial a , la lista de problemas activos
- Colocar y
- tiempo no está vacío
- Seleccionar y eliminar (sacar de la cola) un problema de
- Resuelve la relajación LP del problema.
- Si la solución no es factible, vuelva a 3 (mientras). De lo contrario, denote la solución por con valor objetivo .
- Si , vuelve a 3.
- Si es entero, establecido y vuelve a 3.
- Si lo desea, busque planos de corte violados por . Si encuentra alguno, agréguelos a la relajación LP y vuelva a 3.2.
- Ramificación para dividir el problema en nuevos problemas con regiones factibles restringidas. Agregue estos problemas a y vuelve a 3
- regreso
Pseudocódigo
En un pseudocódigo similar a C ++ , esto podría escribirse:
// ILP bifurca y corta el pseudocódigo de la solución, asumiendo que el objetivo debe maximizarseILP_solution branch_and_cut_ILP ( IntegerLinearProgram initial_problem ) { cola lista_activa ; // L, arriba active_list . poner en cola ( problema_inicial ); // paso 1 // paso 2 ILP_solution óptima_solution ; // esto contendrá x * arriba double best_objective = - std :: numeric_limits < doble > :: infinito ; // mantendrá v * arriba while ( ! active_list . empty ()) { // paso 3 anterior LinearProgram & curr_prob = active_list . dequeue (); // paso 3.1 do { // pasos 3.2-3.7 RelaxedLinearProgram & relajado_prob = LP_relax ( curr_prob ); // paso 3.2 LP_solution curr_relaxed_soln = LP_solve ( relajado_prob ); // esto es x arriba bool cutting_planes_found = false ; if ( ! curr_relaxed_soln . is_feasible ()) { // paso 3.3 continuar ; // prueba con otra solución; continúa en el paso 3 } double current_objective_value = curr_relaxed_soln . valor (); // v arriba if ( current_objective_value <= best_objective ) { // paso 3.4 continuar ; // prueba con otra solución; continúa en el paso 3 } if ( curr_relaxed_soln . is_integer ()) { // paso 3.5 best_objective = current_objective_value ; 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 ( hunting_for_cutting_planes ) { // paso 3.6 violated_cutting_planes = search_for_violated_cutting_planes ( curr_relaxed_soln ); if ( ! violated_cutting_planes . empty ()) { // paso 3.6 Cutting_planes_found = true ; // continuará en el paso 3.2 para ( auto && corte_plano : violated_cutting_planes ) { active_list . poner en cola ( LP_relax ( curr_prob , corte_plano )); } continuar ; // continúa en el paso 3.2 } } // paso 3.7: o no se encontraron los planos de corte violados o no los estábamos buscando auto && branched_problems = branch_partition ( curr_prob ); para ( auto && branch : branched_problems ) { active_list . enqueue ( rama ); } continuar ; // continúa en el paso 3 } while ( hunting_for_cutting_planes / * parámetro del algoritmo; ver 3.6 * / && cutting_planes_found ); // finaliza el paso 3.2 bucle do-while } // finaliza el paso 3 while bucle return óptima_solución ; // paso 4}
En el pseudocódigo anterior, las funciones LP_relax
, LP_solve
y branch_partition
denominados como subrutinas deben ser proporcionados como aplicable al problema. Por ejemplo, LP_solve
podría llamar al algoritmo simplex . Las estrategias de ramificación branch_partition
se analizan a continuación.
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. Todas las estrategias de ramificación que se describen a continuación implican lo que se denomina ramificación en una variable. [3] Ramificar en una variable implica elegir una variable,, con un valor fraccionario, , en la solución óptima a la relajación LP actual y luego agregando las restricciones y
- Ramificación más inviable
- Esta estrategia de ramificación elige la variable con la parte fraccionaria más cercana a 0.5.
- Bifurcación de pseudocoste
- La idea básica de esta estrategia es realizar un seguimiento de cada variable el cambio en la función objetivo cuando esta variable fue previamente elegida 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 la variable de ramificación. Tenga en cuenta que la ramificación de pseudocoste 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 a la función objetivo antes de ramificarse en ellas. La ramificación fuerte completa 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 ramificación, como usar una ramificación fuerte al principio cuando la ramificación de pseudocosto es relativamente poco informativa y luego cambiar a ramificaciones de pseudocosto más tarde cuando hay suficiente historial de ramificaciones para que el seudocosto sea informativo.
Referencias
- ^ Padberg, Manfred; Rinaldi, Giovanni (1991). "Un algoritmo de ramificación y corte para la resolución de problemas de viajante viajante simétrico a gran escala". Revisión SIAM . 33 (1): 60–100. doi : 10.1137 / 1033004 . ISSN 0036-1445 .
- ^ John E., Mitchell (2002). "Algoritmos de ramificación y corte para problemas de optimización combinatoria" (PDF) . Manual de optimización aplicada : 65–77.
- ^ Achterberg, Tobias; Koch, Thorsten; Martín, Alexander (2005). "Reglas de ramificación revisadas". Cartas de investigación operativa . 33 (1): 42–54. doi : 10.1016 / j.orl.2004.04.002 .
enlaces externos
- Programación de enteros mixtos
- SCIP : marco para branch-cut-and-price y un solucionador de programación de enteros mixtos
- ABACUS - Un sistema de sucursales y CUt - software de código abierto
- COIN-OR Cbc - software de código abierto en GitHub