Programación entera
La programación entera (PI) optimiza un objetivo lineal sobre variables restringidas a tomar valores enteros o binarios. El requisito de integralidad rompe la convexidad que hace tratable la programación lineal: el conjunto factible es una colección discreta de puntos y el método Simplex ya no se aplica directamente. La mayoría de los problemas combinatorios prácticos, incluyendo planificación, rutas y asignación de recursos, son programas enteros.
Formulación
Un Programa Lineal Entero Mixto (MILP) tiene la forma:
\[\min_{x,y} \mathbf{c}^T x + \mathbf{d}^T y \quad \text{s.a.} \quad \mathbf{A}x + \mathbf{B}y \leq \mathbf{b}, \quad x \geq 0, \quad y \in \mathbb{Z}^p\]
donde \(x\) son variables continuas e \(y\) son variables enteras. Cuando todas las variables son enteras: Programa Lineal Entero (ILP). Cuando todas son binarias (\(y \in \{0,1\}^p\)): Programa Entero Binario (BIP).
Las variables binarias son especialmente expresivas: modelan decisiones sí/no, condiciones lógicas y estructuras combinatorias. Prácticamente cualquier problema de optimización combinatoria puede formularse como un BIP.
Mochila: \(n\) objetos con valores \(v_i\) y pesos \(w_i\). Maximizar el valor total sujeto a capacidad de peso \(W\):
\[\max \sum_i v_i x_i \quad \text{s.a.} \quad \sum_i w_i x_i \leq W, \quad x_i \in \{0,1\}\]
Asignación: asignar \(n\) trabajadores a \(n\) tareas (uno a uno). Minimizar el coste total \(c_{ij}\):
\[\min \sum_{i,j} c_{ij} x_{ij} \quad \text{s.a.} \quad \sum_j x_{ij} = 1 \;\forall i, \quad \sum_i x_{ij} = 1 \;\forall j, \quad x_{ij} \in \{0,1\}\]
Localización de instalaciones con coste fijo: decidir qué instalaciones abrir (\(y_j \in \{0,1\}\)) y cuánto transportar desde cada una (\(x_{ij} \geq 0\)):
\[\min \sum_j f_j y_j + \sum_{i,j} c_{ij} x_{ij} \quad \text{s.a.} \quad \sum_j x_{ij} \geq d_i \;\forall i, \quad x_{ij} \leq M y_j \;\forall i,j\]
Por qué la integralidad hace difícil la optimización
Añadir restricciones de integralidad a un PL cambia el problema fundamentalmente. La región factible del PL es un politopo convexo; la región factible del PI es el conjunto discreto de puntos enteros dentro de ese politopo. Dos consecuencias clave:
Sin gradiente que seguir: el objetivo es lineal y el conjunto factible es discreto. Los métodos basados en gradientes no se aplican. Redondear la solución del PL al punto entero más cercano suele dar una solución infactible o muy subóptima.
NP-dureza: la programación entera es NP-dura en general. El problema de la mochila, el viajante, el empaquetado y la planificación son todos problemas PI NP-duros. No se conoce ningún algoritmo de tiempo polinomial (y no se espera que exista bajo \(P \neq NP\)).
El óptimo de la relajación LP (rombo naranja) es no entero en \((2{,}33, 2{,}33)\) con \(z=11{,}67\). El verdadero óptimo PI (punto rojo) está en \((3,1)\) con \(z=11\). El óptimo LP proporciona una cota superior del objetivo PI (para maximización).
La relajación LP y las cotas
La relajación LP elimina las restricciones de integralidad y resuelve el PL resultante. Para un problema de maximización:
\[z_\text{LP} \geq z_\text{PI}\]
La relajación LP da una cota superior del objetivo PI (cota inferior para minimización). La brecha \(z_\text{LP} - z_\text{PI}\) mide el coste de las restricciones de integralidad.
Si la solución de la relajación LP resulta ser entera, también es el óptimo PI. Para estructuras especiales (matrices de restricciones totalmente unimodulares, por ejemplo, problemas de flujo en red, problemas de asignación), la relajación LP siempre da solución entera: no es necesaria la ramificación y poda.
Ramificación y poda
La ramificación y poda es el algoritmo fundamental para resolver programas enteros. Enumera implícitamente todas las soluciones enteras factibles dividiendo el problema en subproblemas y usando las relajaciones LP para podar subproblemas que no pueden contener la solución óptima.
Algoritmo:
Inicializar: resolver la relajación LP. Si la solución es entera, fin. En caso contrario, el valor óptimo LP es una cota superior \(\bar{z}\) (para maximización). Establecer la mejor solución entera encontrada \(\underline{z} = -\infty\).
Ramificar: seleccionar una variable fraccionaria \(x_j = \bar{x}_j\) (no entera). Crear dos subproblemas hijo añadiendo:
- Rama hacia abajo: \(x_j \leq \lfloor \bar{x}_j \rfloor\)
- Rama hacia arriba: \(x_j \geq \lceil \bar{x}_j \rceil\)
Acotar: resolver la relajación LP de cada hijo. Si el óptimo LP es:
- Infactible: podar (no hay solución entera factible en esta rama).
- Peor que \(\underline{z}\): podar (no puede mejorar la mejor solución conocida).
- Entero: actualizar \(\underline{z}\) si es mejor que el actual.
- Fraccionario y mejor que \(\underline{z}\): añadir a la lista de nodos abiertos.
Repetir hasta que no queden nodos abiertos. La mejor solución entera encontrada es óptima.
El algoritmo encuentra la solución óptima \((x=2, y=3, z=12)\) resolviendo solo 3 relajaciones LP en lugar de enumerar todos los puntos enteros.
Planos de corte
Los planos de corte son desigualdades lineales adicionales que se añaden a la relajación LP para eliminar soluciones fraccionarias sin quitar ningún punto entero factible. Ajustan la relajación LP acercando su óptimo al óptimo PI.
Los planos de corte más importantes:
Cortes de Gomory: derivados algebraicamente del tableau del Simplex. Para una variable básica fraccionaria \(x_j = \bar{x}_j\) con \(\bar{x}_j \notin \mathbb{Z}\), el corte de Gomory elimina la solución LP fraccionaria manteniendo factibles todas las soluciones enteras.
Desigualdades de cobertura (para la mochila): si un subconjunto \(S\) de objetos no cabe todo en la mochila (\(\sum_{i \in S} w_i > W\)), se pueden seleccionar como máximo \(|S|-1\) de ellos: \(\sum_{i \in S} x_i \leq |S|-1\).
Los solvers de PI modernos (Gurobi, CPLEX) combinan ramificación y poda con planos de corte (ramificación y corte): los cortes se generan en cada nodo del árbol para ajustar la relajación LP local.
⚠️ La programación entera es NP-dura: cuidado con el tamaño del problema
Incluso con solvers modernos, los programas enteros pueden ser intratables para instancias grandes:
- Un PI binario con \(n=50\) variables tiene \(2^{50} \approx 10^{15}\) puntos factibles en el peor caso.
- El Problema del Viajante con \(n\) ciudades tiene \((n-1)!/2\) rutas posibles.
- La resolubilidad práctica depende mucho de la estructura del problema. Los PI de flujo en red (totalmente unimodulares) se resuelven como PL. Los PI generales con cotas LP débiles pueden tardar horas o no resolverse.
Antes de formular un problema como PI, verificar: ¿es la relajación LP ajustada? ¿Tiene la matriz de restricciones una estructura especial (unimodularidad total)? ¿Es aceptable una heurística o un algoritmo de aproximación?
Aplicaciones
La programación entera modela una enorme variedad de problemas reales:
- Planificación de vuelos: asignación de aviones y tripulaciones a vuelos, respetando requisitos de descanso y conexiones.
- Cadena de suministro: localización de almacenes, rutas de inventario, planificación de vehículos.
- Telecomunicaciones: diseño de redes, asignación de frecuencias.
- Finanzas: selección de cartera con costes de transacción, restricciones de cardinalidad.
- Sanidad: planificación de turnos de enfermería, programación de quirófanos, distribución de vacunas.
💡 Programación entera en R
library(lpSolve)
# Mochila: 5 objetos, valores y pesos
values <- c(10, 6, 3, 7, 8)
weights <- c(5, 3, 2, 4, 5)
capacity <- 10
obj <- values
mat <- matrix(weights, nrow=1)
rhs <- capacity
dir <- "<="
# PI binario (all.bin=TRUE)
sol <- lp("max", obj, mat, dir, rhs, all.bin=TRUE)
sol$solution # qué objetos tomar
sol$objval # valor óptimo
# Entero mixto con lpSolve
# int.vec especifica qué variables deben ser enteras
sol <- lp("max", obj, mat, dir, rhs, int.vec=1:5)
# Para PI serio: usar el paquete highs (más rápido)
library(highs)
highs_solve(L=obj, lower=rep(0,5), upper=rep(1,5),
A=matrix(weights,1), lhs=-Inf, rhs=capacity,
types=rep("I",5), maximum=TRUE)Para PI de producción en R, highs proporciona el solver HiGHS (solver MIP de código abierto de última generación). Las opciones comerciales (Gurobi, CPLEX) son significativamente más rápidas para instancias grandes.
