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.
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.
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 .
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
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.
