Relajación lineal: cuánto puede mejorar una solución
Aprenda a interpretar límites, gaps y sensibilidad de capacidad sin confundir una solución fraccionaria con una red operativa.
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
Una regla de comparación
Encontrar una solución de coste 900 no dice si es buena: quizá exista otra de 500. La relajación lineal proporciona una referencia al permitir x e y entre cero y uno. Se amplía el conjunto de decisiones permitidas, por lo que el mínimo relajado no puede superar el mínimo entero del mismo problema. Es como calcular un presupuesto con permisos adicionales: si incluso con esas facilidades no se baja de cierto coste, la solución original tampoco podrá hacerlo.
Una apertura de 0,4 o una región dividida entre centros puede tener sentido en la cuenta relajada, pero no satisface la decisión binaria planteada. No redondee sin comprobar asignaciones y capacidad: el redondeo puede crear sobrecarga o aumentar costes. En el proyecto, GLOP calcula esta referencia; SCIP busca decisiones enteras y puede fortalecer su propio límite durante la búsqueda.
Leer el intervalo antes del porcentaje
Llame UB al coste de una solución entera viable y LB al límite inferior válido. El óptimo está entre ambos. Esta serie usa gap = 100 × (UB − LB) / UB, cuando UB es positivo. En la ejecución LNS de semilla 0 para 50×15, UB=885420,59 y el LP da LB=871526,66: el gap es aproximadamente 1,57%. Es una cota de la mejora pendiente respecto a ese UB, no una probabilidad de que la solución sea correcta.
from alocacao_capacitada.analysis.study import tiny_instance
from alocacao_capacitada.solvers.lp_relaxation import solve_lp_relaxation
from alocacao_capacitada.solvers.milp import MilpSolver
from alocacao_capacitada.domain.evaluation import evaluate
inst = tiny_instance()
lp = solve_lp_relaxation(inst)
result = MilpSolver().solve(inst, 5.0)
ub = evaluate(inst, result.solution).total_cost
print(lp.lower_bound, ub)
print(100 * (ub - lp.lower_bound) / ub)
print(lp.y_fraction, lp.capacity_marginal_value)El gap frente al LP y el gap frente al bound del MILP responden a referencias distintas. Por ejemplo, el MILP 100×30 guardado tiene coste 1310952,57 y bound 1305960,58: aproximadamente 0,38% frente a su propio bound, aunque la tabla comparativa muestra 1,66% frente al LP. Además, resultados antiguos del repositorio usan LB como denominador. Escriba la fórmula junto a cada tabla para evitar comparaciones falsas.
Cuánto vale ampliar capacidad
El dual de capacidad requiere cuidado: Q_i multiplica y_i en la restricción, no aparece como un simple término independiente. La sensibilidad local implementada es capacity_dual × y_fraction. Sirve para explorar pequeñas perturbaciones de la relajación. Para decidir una ampliación real, modifique Q_i, mantenga la demanda fija, vuelva a resolver el modelo entero y compare coste, servicio y gasto de expansión. Una apertura nueva puede producir un salto que la derivada local no anticipa.
Fuentes y evidencias
Siguiente: Voraz y búsqueda local: construir rápido y mejorar con criterio