Programación Entera (IP)

La programación entera (pure IP) es la clase de problemas min c^T x s.a. Ax ≤ b, x ∈ Z^n_+ en forma canónica, donde todas las variables de decisión son enteras. El caso 0-1 (binario) x ∈ {0,1}^n es la formulación natural de la optimización combinatoria: mochila, asignación, cubrimiento de conjuntos, partición de conjuntos, problema del viajante (TSP), emparejamiento y coloreo de grafos. Complejidad: la IP pura aparece como 0-1 IP en la lista de 21 problemas NP-completos de Karp (1972); Lenstra (1983) demostró que la IP es polinómica en dimensión fija (poco práctico cuando la dimensión es parte de la entrada). Imponer la integralidad a la relajación LP puede mover bruscamente el óptimo; la brecha de integralidad es la medida canónica de la fuerza de una formulación. El algoritmo clásico es el método de planos de corte de Gomory (1958): resolver la relajación LP, si el óptimo es fraccional generar un corte de Gomory (con información del tableau simplex) que excluya el óptimo LP actual pero no ningún punto entero factible, añadirlo y resolver de nuevo; converge en un número finito de iteraciones a un óptimo entero (en teoría). En la práctica branch-and-bound de Land y Doig (1960) y posteriormente branch-and-cut (Padberg y Rinaldi 1991) son más rápidos. La teoría poliédrica — Chvátal (1973), Schrijver (1986) — deriva desigualdades válidas (eliminación de subtours, desigualdades de blossom para TSP) que aproximan la relajación a la envoltura convexa de los puntos enteros factibles. Aplicaciones: TSP / enrutamiento de vehículos (Dantzig, Fulkerson y Johnson 1954), asignación, scheduling, flujo en redes, cutting stock (Gilmore y Gomory 1961), bin packing.