Considere o seguinte problema de caminho mínimo com restrição de tempo. Seja
um grafo orientado com peso
e tempo
associados a cada arco
. Queremos encontrar um caminho de peso mínimo entre dois nós s ed de
, cuja soma dos pesos dos arcos não ultrapasse um tempo limite
. Seja
e
.
problema pode ser modelado como segue:
Encontre o problemas mestre e o subproblema de Dantzig-Wolfe obtidos com geração de colunas sobre os pontos definidos por (1) e (3). Interprete ambos os problemas (dê uma interpretação para a variável do mestre).
Passo 1
Beleza, vamos lá. O enunciado fala de um problema de caminho mínimo com restrição de tempo num grafo direcionado
, onde cada arco
tem um peso
e um tempo
. A modelagem inteira é:
Minimize
sujeito a
1) conservação de fluxo (caminho de
2) limite de tempo
3) variáveis binárias
Conteúdo: decomposição de Dantzig–Wolfe (geração de colunas).
O que vamos usar:
O que vamos usar:
- A ideia de escrever qualquer solução
que respeita o fluxo como combinação convexa de caminhos simples de a . - Gerar colunas (caminhos) via um subproblema de caminho mais curto com custos ajustados pelos duais.
- Montar o problema mestre que escolhe quantas vezes cada caminho aparece (variáveis
).
A partir do próximo passo a gente entra de fato na construção da DW.
Passo 2
Definindo o poliedro base (sem a restrição de tempo). Considere
Teoria: todo vértice extremo de
Logo, podemos reescrever
onde
é o vetor indicador do caminho
(
se o arco
faz parte de
, e 0 caso contrário).
Passo 3
Agora metemos a restrição de tempo junto nessa representação. Para cada caminho
definimos
A variável
O problema mestre DW (relaxado para
Minimize
sujeito a
Aqui
e
são os duais da restrição de tempo e da condição de convexidade, respectivamente.
Passo 4
Para gerar colunas (novos caminhos) usamos o subproblema obtido a partir do dual do mestre. O dual é:
Maximize
sujeito a
Equivalente a: encontrar um
que viole
, isto é, que minimize
e verifique se o valor é menor que
Como
Resposta
Problema Mestre DW (relaxado):
Minimize
Minimize
s.a.
Interpretação da variável
: quanto “peso” (ou frequência) damos ao caminho
na solução. No fim, a solução integral fará
para um único caminho viável.
Subproblema de Geração de Colunas:
Dado valor dual da restrição de tempo, resolver
Dado valor dual
(ou seja, caminho mínimo com custo
Se o valor mínimo for menor que o dual da convexidade, a coluna (caminho) entra no mestre para melhorar a solução.