Programación Lineal Entera Mixta (MILP)

La programación lineal entera mixta (MILP) es la clase de problemas min c^T x + d^T y s.a. Ax + By ≤ b, x ≥ 0, y ∈ Z^p_+ en forma canónica, donde x ∈ R^n son continuas y y ∈ Z^p son variables enteras. La integralidad suele ser binaria y ∈ {0,1}^p y modela decisiones lógicas (invertir/no, abrir/cerrar máquina, usar/no ruta, asignación producto-proveedor-periodo). Costes fijos, lotes discretos, disyunciones y formulaciones big-M fuerzan variables enteras. Complejidad: MILP es NP-difícil (Cook 1971 por reducción de SAT; muchos de los 21 problemas NP-completos de Karp 1972 se expresan como MILP); la relajación LP (eliminando integralidad y dejando y ≥ 0) es polinómica y aporta una cota inferior en minimización. El algoritmo canónico es branch-and-bound de Land y Doig (1960) — resolver la relajación LP, ramificar en una y_i fraccional, podar subárboles cuya cota es peor que la incumbent. Gomory (1958) introdujo cortes fraccionales y Padberg y Rinaldi (1991) consolidaron el marco branch-and-cut; los solucionadores modernos combinan planos de corte (Gomory, lift-and-project, MIR, cover), presolve de nodo, heurísticas primales (feasibility pump, RINS), análisis de conflictos y branch-and-bound paralelo. Los modelos MILP cubren localización de instalaciones (Fixed Charge Facility Location), enrutamiento de vehículos, planificación de producción, asignación, empaquetado, diseño de redes, selección de carteras (restricciones de cardinalidad) y unit commitment energético.