Optimización entera y combinatoria
Muchas decisiones son discretas: abrir o cerrar una planta, asignar una tarea, elegir un subconjunto. La optimización entera (IP) y su caso binario agregan a un modelo lineal la condición de que ciertas variables tomen valores enteros. El resultado es una clase de problemas muchísimo más expresiva y, en general, NP-dura.
De la relajación a la cota
Quitar la condición de integridad produce la relajación lineal: su óptimo, para un maximiza, es una cota superior del entero óptimo. Esa cota es el ancla del campo: sin ella no habría forma de saber cuán bueno es una solución factible encontrada por heurística.
Modelar decisiones discretas
- Binarias para sí-no: abrir planta, aceptar pedido, programar tarea.
- Indicadores y big-M: si se abre la planta, entonces puede despachar.
- Semicontinuas: o cero, o dentro de un rango operativo (arranque de máquinas).
- Restricciones lógicas: implicaciones y exclusión mutua entre opciones.
Ramificar y acotar
El algoritmo maestro es ramificar y acotar: resolver el relajado, elegir una variable fraccionaria y ramificar el problema en dos subproblemas con cotas opuestas; podar cuando la cota del subproblema no mejora a la mejor solución entera conocida. La fuerza bruta se convierte en una búsqueda con tijeras: la calidad del relajado y de las heurísticas decide cuántas ramas sobreviven.
Planos de corte y los dos motores
Los planos de corte añaden restricciones válidas que recortan la relajación sin tocar los enteros. Los solucionadores modernos mezclan ramificar-y-acotar con cortes y heurísticas, y por eso reportan gap: la distancia relativa entre mejor cota y mejor solución factible. Un gap de 1.5 por ciento con una solución de mil millones de pesos es un resultado profesional, no un fracaso.
El zoo de modelos clásicos
- Mochila: elegir subconjunto con capacidad limitada.
- Asignación: emparejar agentes y tareas con costo mínimo.
- Rutas de vehículos: flota, capacidad y ventanas de tiempo.
- Localización de instalaciones: dónde abrir para servir a todos.
- Horarios: exámenes, turnos y guardias como coloreo de grafos.
| Concepto | Qué da |
|---|---|
| Relajación lineal | cota del óptimo entero |
| Rama acotada | búsqueda podada por cotas |
| Corte | aprieta la relajación sin excluir enteros |
| Gap | cuánto falta para certificar optimalidad |
Errores frecuentes
- Redondear la solución del relajado y declararla entera: puede ser infactible o muy mala.
- Big-M inflado: numéricamente frágil y afloja la relajación.
- Modelar con variables enteras lo que son conteos y no con binarias: el solucionador sufre.
- Esperar optimalidad certificada en instancias industriales sin explotar estructura ni heurísticas.
Ejemplo resuelto: mochila por ramificación
- Plantear el relajado lineal y resolver: da la cota superior.
- Elegir la variable de decisión fraccionaria y crear dos ramas con cotas opuestas.
- Resolver cada rama; si su cota no supera a la mejor entera, podarla.
- Cuando una rama da una solución entera factible, actualizar la mejor conocida.
- Terminar cuando el gap entre cota global y mejor entera sea aceptable.
¿Para qué sirve en la realidad?
Cada noche, cadenas retail y aerolíneas resuelven modelos enteros con millones de variables para reabastecer, tripular y programar. Los solucionadores (de código abierto o comercial) son infraestructura crítica de la logística moderna.
En un problema de maximización entera, ¿qué papel cumple la relajación lineal?
La mejor solución entera factible encontrada por heurística siempre coincide con el óptimo del relajado lineal.
La distancia relativa entre la mejor cota y la mejor solución entera factible se llama del solucionador.
Clasifica cada pieza según dónde vive en el flujo de un modelo entero.
Modelado
Acotar
Cortar ramas
Une cada problema clásico con su forma.
Vocabulario entero
Optimización entera
# Entero y combinatorio ## Modelos ### mochila ### asignación ### rutas ### localización ## Relajación ### cota superior ### cortes ## Algoritmo ### ramificar ### acotar ### podar ## Práctica ### big-M ### gap y heurísticas
Ramificar y acotar (Wikipedia)
El algoritmo maestro con sus reglas de poda y selección de ramas.
Programación entera (Wikipedia)
Formulación, relajación y resolución de modelos con variables enteras.
Debes programar 60 rutas de reparto con ventanas de tiempo. ¿Qué variables binarias y qué continuidad modelarías, cómo obtendrías una cota inicial sin solucionador comercial y qué gap considerarías aceptable para publicar el plan nocturno?