MILP: convertir una decisión logística en un modelo verificable
Variables, restricciones, capacidad y costes: construya el ejemplo de tres centros y compruebe el óptimo.
Serie: de los datos a la decisión logística
- De los pedidos a la red logística: un proyecto de optimización y aprendizaje automático
- MILP: convertir una decisión logística en un modelo verificable
- Relajación lineal: cuánto puede mejorar una solución
- Voraz y búsqueda local: construir rápido y mejorar con criterio
- LNS: reorganizar parte de la red para escapar del óptimo local
- Predecir demanda: de una referencia poblacional a Poisson y boosting
- Previsión poblacional: tendencias, amortiguación y prueba temporal
- K-means: descubrir perfiles municipales sin inventar categorías naturales
- Scoring de candidatos: aprender a filtrar sin perder buenas decisiones
- Escenarios y SAA: decidir antes de conocer la demanda
Qué decisión representa cada variable
Imagine un plano con emplazamientos autorizados y regiones que necesitan servicio. El plano no permite inventar nuevas ubicaciones: la elección ocurre entre los candidatos suministrados. Para cada centro i, y_i vale uno si abre. Para cada región j, x_ij vale uno si queda asignada al centro i. Esta formulación es una variante del problema de localización capacitada con proveedor único, SSCFLP. Una región constituye un bloque indivisible de demanda; eso no significa que todos los pedidos reales deban viajar juntos.
La función objetivo suma apertura, transporte y demanda no atendida. Aquí f_i es el coste fijo, d_j la demanda, c_ij el coste de transportar una unidad y p la penalización por unidad no atendida. Todos deben compartir moneda y horizonte: mezclar alquiler mensual con dos años de pedidos altera la decisión antes de iniciar el solver.
min sum_i f_i*y_i + sum_i,j d_j*c_ij*x_ij
+ p*sum_j d_j*(1 - sum_i x_ij)
sum_i x_ij <= 1 (j)
sum_j d_j*x_ij <= Q_i*y_i (i)
x_ij <= y_i (i,j)
x_ij, y_i in {0,1}La primera restricción admite dejar regiones sin atender. La segunda limita la carga y la tercera vincula asignación y apertura. Por tanto, una solución factible puede tener servicio insuficiente. Si su contrato exige atenderlo todo, necesita igualdad en la primera restricción y verificar que exista capacidad compatible con los bloques. Una penalización alta expresa una preferencia económica, no sustituye una obligación contractual.
Un laboratorio que cabe en una página
En el entorno del proyecto, este programa crea demandas de 4, 8, 8, 4 y 2 unidades, tres capacidades de 14 y costes fijos de 33, 35 y 38. La matriz contiene costes unitarios; la penalización es 50. El evaluador vuelve a calcular la solución por separado del solver: esa separación ayuda a detectar errores de formulación o de extracción.
from alocacao_capacitada.analysis.study import tiny_instance, enumerate_tiny
from alocacao_capacitada.solvers.milp import MilpSolver
from alocacao_capacitada.domain.evaluation import evaluate
instance = tiny_instance()
result = MilpSolver().solve(instance, 5.0)
metrics = evaluate(instance, result.solution)
space = enumerate_tiny(instance)
print(result.status, metrics.total_cost, metrics.feasible)
print(result.solution.assignment.tolist())
print(len(space), space.custo.min())El resultado esperado es OTIMO, coste 203 y asignación [2, 1, 2, 1, 1], usando índices A=0, B=1 y C=2. B atiende R2, R4 y R5, con carga 14; C atiende R1 y R3, con carga 12. Apertura 73 más transporte 130 produce 203. Hay 4⁵=1024 asignaciones posibles al incluir la opción sin servicio; 760 respetan capacidad. Enumerarlas y comparar sus costes demuestra el óptimo de este ejemplo.
Qué certifica el solver
SCIP combina exploración de decisiones enteras, relajaciones y cortes para descartar conjuntos que no pueden mejorar la solución disponible. En instancias grandes puede terminar por tiempo con una solución viable y un límite inferior distinto. Registre ambos, además de servicio, cargas y tiempo. Pregunte qué restricciones faltan: plazos, turnos, inventario y rutas de vehículos no aparecen automáticamente por utilizar MILP. Un mapa de asignaciones tampoco es un plan de reparto.
Fuentes y evidencias
Siguiente: Relajación lineal: cuánto puede mejorar una solución