Relaxação linear: quanto uma solução ainda pode melhorar
Aprenda a interpretar limites, gaps e sensibilidade de capacidade sem confundir uma solução fracionária com uma rede operacional.
Série: dos dados à decisão logística
- Dos pedidos à rede logística: um projeto de otimização e machine learning
- MILP: transformar uma decisão logística em um modelo verificável
- Relaxação linear: quanto uma solução ainda pode melhorar
- Guloso e busca local: construir rápido e melhorar com critério
- LNS: reorganizar parte da rede para escapar do ótimo local
- Prever demanda: de uma referência populacional a Poisson e boosting
- Previsão populacional: tendências, amortecimento e teste temporal
- K-means: descobrir perfis municipais sem inventar categorias naturais
- Scoring de candidatos: aprender a filtrar sem perder boas decisões
- Cenários e SAA: decidir antes de conhecer a demanda
Uma régua de comparação
Encontrar uma solução de custo 900 não informa se ela é boa: talvez exista outra de 500. A relaxação linear fornece uma referência ao permitir x e y entre zero e um. Amplia-se o conjunto de decisões permitidas, então o mínimo relaxado não pode superar o mínimo inteiro do mesmo problema. É como calcular um orçamento com permissões adicionais: se mesmo com essas facilidades não se consegue ficar abaixo de certo custo, a solução original também não conseguirá.
Uma abertura de 0,4 ou uma região dividida entre centros pode fazer sentido na conta relaxada, mas não satisfaz a decisão binária proposta. Não arredonde sem verificar atribuições e capacidade: o arredondamento pode gerar sobrecarga ou aumentar custos. No projeto, o GLOP calcula essa referência; o SCIP procura decisões inteiras e pode fortalecer seu próprio limite durante a busca.
Ler o intervalo antes da porcentagem
Chame de UB o custo de uma solução inteira viável e de LB o limite inferior válido. O ótimo está entre os dois. Esta série usa gap = 100 × (UB − LB) / UB, quando UB é positivo. Na execução LNS de semente 0 para 50×15, UB=885420,59 e o LP fornece LB=871526,66: o gap é aproximadamente 1,57%. É um limite para a melhoria restante em relação a esse UB, não uma probabilidade de a solução estar correta.
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)O gap em relação ao LP e o gap em relação ao bound do MILP usam referências diferentes. Por exemplo, o MILP 100×30 salvo tem custo 1310952,57 e bound 1305960,58: aproximadamente 0,38% em relação ao próprio bound, embora a tabela comparativa mostre 1,66% em relação ao LP. Além disso, resultados antigos do repositório usam LB como denominador. Escreva a fórmula junto de cada tabela para evitar comparações falsas.
Quanto vale ampliar capacidade
O dual de capacidade exige cuidado: Q_i multiplica y_i na restrição, não aparece como um simples termo independente. A sensibilidade local implementada é capacity_dual × y_fraction. Ela serve para explorar pequenas perturbações da relaxação. Para decidir uma ampliação real, altere Q_i, mantenha a demanda fixa, resolva novamente o modelo inteiro e compare custo, atendimento e investimento na expansão. Uma nova abertura pode produzir um salto que a derivada local não antecipa.
Fontes e evidências
Próximo: Guloso e busca local: construir rápido e melhorar com critério