Branch-and-Cut

Branch-and-cut es el marco de resolución exacto para programación entera mixta (MIP) que está bajo todos los solvers MIP comerciales y de código abierto modernos. Combina dos ideas: (a) **branch-and-bound** — dividir el problema entero en subproblemas más pequeños mediante ramificación de variables, resolver la relajación LP en cada nodo y podar subárboles cuya cota LP sea peor que la mejor solución factible actual; (b) **planos de corte** — antes de ramificar, añadir desigualdades válidas (cortes) que se satisfacen para toda solución entera factible pero recortan el óptimo LP fraccional actual, ajustando la relajación y reduciendo la brecha. El enfoque fue introducido por Dantzig, Fulkerson y Johnson (1954) sobre el Travelling Salesman Problem (TSP) — usaron cortes de eliminación de subtours dentro de una búsqueda branch-and-bound y resolvieron una instancia de 49 ciudades al óptimo. Padberg y Rinaldi (1991) generalizaron el marco con rutinas de separación que detectan cortes violados al vuelo. Hoy branch-and-cut es el método exacto por defecto para TSP, VRP, scheduling, localización de instalaciones y decenas de otros problemas de optimización combinatoria; el rendimiento reportado del solver sobre TSP ha cruzado los 85K+ nodos (Applegate, Bixby, Chvátal y Cook 2006). Cortes usados en la práctica: eliminación de subtours, desigualdades de peine (comb), cortes de clique, cortes de Gomory, cortes de redondeo entero mixto, cortes lift-and-project.