MILP: transformar uma decisão logística em um modelo verificável
Variáveis, restrições, capacidade e custos: construa o exemplo de três centros e confira o ótimo.
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
Que decisão cada variável representa
Imagine um mapa com locais autorizados e regiões que precisam de atendimento. O mapa não permite inventar novas localizações: a escolha ocorre entre os candidatos fornecidos. Para cada centro i, y_i vale um se ele abre. Para cada região j, x_ij vale um se ela fica atribuída ao centro i. Essa formulação é uma variante do problema de localização capacitada com fornecedor único, SSCFLP. Uma região constitui um bloco indivisível de demanda; isso não significa que todos os pedidos reais devam viajar juntos.
A função objetivo soma abertura, transporte e demanda não atendida. Aqui f_i é o custo fixo, d_j a demanda, c_ij o custo de transportar uma unidade e p a penalidade por unidade não atendida. Todos devem compartilhar moeda e horizonte: misturar aluguel mensal com dois anos de pedidos altera a decisão antes de iniciar o 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}A primeira restrição permite deixar regiões sem atendimento. A segunda limita a carga e a terceira vincula atribuição e abertura. Portanto, uma solução viável pode ter atendimento insuficiente. Se o contrato exige atender tudo, você precisa de igualdade na primeira restrição e verificar se existe capacidade compatível com os blocos. Uma penalidade alta expressa uma preferência econômica, não substitui uma obrigação contratual.
Um laboratório que cabe em uma página
No ambiente do projeto, este programa cria demandas de 4, 8, 8, 4 e 2 unidades, três capacidades de 14 e custos fixos de 33, 35 e 38. A matriz contém custos unitários; a penalidade é 50. O avaliador recalcula a solução separadamente do solver: essa separação ajuda a detectar erros de formulação ou extração.
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())O resultado esperado é OTIMO, custo 203 e atribuição [2, 1, 2, 1, 1], usando índices A=0, B=1 e C=2. B atende R2, R4 e R5, com carga 14; C atende R1 e R3, com carga 12. Abertura 73 mais transporte 130 produz 203. Há 4⁵=1024 atribuições possíveis ao incluir a opção sem atendimento; 760 respeitam capacidade. Enumerá-las e comparar seus custos prova o ótimo deste exemplo.
O que o solver certifica
O SCIP combina exploração de decisões inteiras, relaxações e cortes para descartar conjuntos que não podem melhorar a solução disponível. Em instâncias grandes pode terminar por tempo com uma solução viável e um limite inferior diferente. Registre ambos, além de atendimento, cargas e tempo. Pergunte quais restrições faltam: prazos, turnos, estoque e rotas de veículos não aparecem automaticamente por utilizar MILP. Um mapa de atribuições também não é um plano de entregas.
Fontes e evidências
Próximo: Relaxação linear: quanto uma solução ainda pode melhorar