Método de Planos de Corte

El método de planos de corte es una técnica clásica para programación entera (IP) y programación entera mixta (MIP) que aprieta iterativamente la relajación LP con **desigualdades válidas** que eliminan el óptimo fraccional LP sin excluir ningún punto entero factible. Lo introdujo Gomory (1958) para programación entera (corte fraccional de Gomory) y Gomory (1960) para la variante entera mixta (corte mixto-entero de Gomory). El algoritmo opera así: resolver la relajación LP; si la solución es entera, se encontró el óptimo; en caso contrario, generar un corte que excluya el punto fraccional pero preserve todos los puntos enteros factibles, añadirlo al modelo y resolver el LP de nuevo; iterar hasta integralidad. Las familias de cortes son específicas del problema: cortes de cobertura de mochila, cortes de cobertura de flujo, cortes de clique (coloración de grafos/IP), redondeo entero mixto (MIR), cortes Chvátal-Gomory, cortes lift-and-project (Balas, Ceria y Cornuéjols 1993), desigualdades de subtour y comb para TSP (Padberg-Rinaldi 1991). Como los cortes puros de Gomory convergen lento en la práctica, las implementaciones modernas combinan cortes con branch and bound (branch-and-cut, Padberg y Rinaldi 1991) — la arquitectura base de los solvers MIP modernos. La generación de cortes es automática y casi invisible al usuario. Nemhauser y Wolsey (1988), Wolsey (1998) y Cornuéjols (2008) son lecturas de referencia.