Considere o seguinte problema de caminho mínimo com restrição de tempo. Seja G=(V, A) um grafo orientado com peso wa e tempo ta associados a cada arco a in A. Queremos encontrar um caminho de peso mínimo entre dois nós s ed de G, cuja soma dos pesos dos arcos não ultrapasse um tempo limite T. Seja V+(i)=j:(i, j) in A e V-(i)=j:(j, i) in A. O problema pode ser modelado como segue:
& min sum(i, j) in A wi j xi j & sa: sumj in V+(s) xs j=1, sumi in V-(s) xi d=1, sumj in V+(k) xk j=sumi in V-(k) xi k forall k in V backslashs, t & sum(i, j) in A ti j xi j <= T & xi j in B, forall(i, j) in A
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 G=(V,A), onde cada arco (i,j) tem um peso wij e um tempo tij. A modelagem inteira é:
Minimize
sum(i,j)in A wij,xij
sujeito a
1) conservação de fluxo (caminho de s a t),
2) limite de tempo sum tijxij<= T,
3) variáveis binárias xijin0,1.
Conteúdo: decomposição de Dantzig–Wolfe (geração de colunas).
O que vamos usar:
  • A ideia de escrever qualquer solução x que respeita o fluxo como combinação convexa de caminhos simples de s a t.
  • 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 lambdap).
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
P=lxin0,1^A:sumjin V+(s)xsj=1,;sumiin V-(t)xit=1,;sumjin V+(k)xkj=sumiin V-(k)xik;forall kneq s,tr
Teoria: todo vértice extremo de P corresponde exatamente a um caminho simples p de s até t.
Logo, podemos reescrever
x=sumpin Plambdap,x^p, lambdap>=0,;sumplambdap=1,
onde x^p é o vetor indicador do caminho p ( (x^p)ij=1 se o arco (i,j) faz parte de p, e 0 caso contrário).

Passo 3

Agora metemos a restrição de tempo junto nessa representação. Para cada caminho p definimos
wp=sum(i,j)in pwij, tp=sum(i,j)in ptij
A variável lambdap indica quanto “pesamos” esse caminho na solução (no fim ela será 0 ou 1 se quisermos a integralidade).
O problema mestre DW (relaxado para lambda>=0) fica:
Minimize
sumpin Pwp,lambdap
sujeito a
sumpin Ptp,lambdap<= T(pi),, sumpin Plambdap=1(sigma),, lambdap>=0;forall p
Aqui pi e sigma 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
Tpi+sigma
sujeito a
pi,tp+sigma<= wpforall p
Equivalente a: encontrar um p que viole pi,tp+sigma<= wp, isto é, que minimize
wp-pi,tp
e verifique se o valor é menor que ,sigma, (coluna de custo reduzido negativo).
Como wp=sum(i,j)in pwij e tp=sum(i,j)in ptij, o subproblema se reduz a resolver um caminho mínimo de s a t com custo em cada arco (i,j) igual a
cij=wij-pi,tij

Resposta

Problema Mestre DW (relaxado):
Minimize
sumpin Pwp,lambdap
s.a.
sumpin Ptp,lambdap<= T,, sumpin Plambdap=1,, lambdap>=0
Interpretação da variável lambdap: quanto “peso” (ou frequência) damos ao caminho p na solução. No fim, a solução integral fará lambdap=1 para um único caminho viável.
Subproblema de Geração de Colunas:
Dado valor dual pi da restrição de tempo, resolver
minpin P;sum(i,j)in pl(wij-pi,tijr)
(ou seja, caminho mínimo com custo cij=wij-pi tij).
Se o valor mínimo for menor que o dual da convexidade, a coluna (caminho) entra no mestre para melhorar a solução.

Exercícios relacionados