Artigo: The dynamic berth allocation problem for a container port
Akio Imai, Etsuko Nishimura, Stratos Papadimitriou, 1.999
Analisando a formulação relaxada para o
sistema dinâmico de alocação de berços
 A formulação do DBAP é do tipo MIP e não pode ser resolvida em tempo
polinomial. Assim, poderia ser resolvida pela técnica branch-and-bound (uma
das mais utilizadas para encontrar a solução ótima de problemas de
otimização NP-difíceis), porém consome muito tempo computacional;
 Assim, os autores deste artigo desenvolveram uma heurística utilizando a
Relaxação Lagrangeana, com o método de otimização do subgradiente;
 Cujo ganho no tempo computacional para grandes escalas é notável
(LORENA et. al).
Condições de Otimalidade
Relaxações podem ser obtidas por meio:
• da desconsideração de algumas restrições;
• da desconsideração das das restrições de integralidade e da,
• da simplificação do problema.
Relaxação Lagrangeana
• Held & Karp em 1970 utilizaram um método Lagrangeano para resolver o
problema do caixeiro viajante, foram precursores do uso deste método;
• Somente em 1974 Geoffrion firmou o nome perfeito para esta abordagem Relaxação Lagrangeana (Fisher, 1981);
• O problema Lagrangeano consiste na dualização das restrições difíceis, com
o acréscimo destas à função objetivo através de um vetor de multiplicadores,
chamados de multiplicadores de Lagrange, sendo eliminadas em seguida do
conjunto de restrições (www.deps.ufsc.br/~mayerle);
• Uma relaxação Lagrangeana de um dado problema é obtida multiplicando o
conjunto de restrições Ax ≤ b por um vetor u de multiplicadores de Lagrange
de sinal apropriado, adicionando-se o produto à função objetivo (Espejo et.
al.2002);
•A escolha das restrições a serem relaxadas pode afetar tanto o valor da
solução ótima do dual da relaxação quanto o esforço computacional requerido
para avaliar e atualizar a função dual durante o processo de solução do
mesmo (Espejo, 2002).
Exemplificando:
1. Inicia-se com um problema de otimização combinatória formulado como
um problema de programação inteira.
Z= min cx
Sujeito à:
Ax = b,
Dx<=e
x>= 0 e inteiro,
(1)
(2)
(3)
2. Relaxa-se a restrição (1) para tornar o problema mais fácil de ser
resolvido.
ZD(u) = min cx + u(Ax – b)
Sujeito à:
Dx<=e
x>= 0 e inteiro
Onde u = {u1,...,um} é o vetor de multiplicadores de Lagrange
(Fisher, 1981)
• Se a restrição for do tipo Ax <= b, então u >= 0;
• Se for do tipo Ax >= b, então u <= 0;
POR QUÊ?
Para garantir que ZD(u) <= Z , “onde sua solução ótima será um limitante
inferior do valor da solução também ótima, mas do problema original de
minimização” (Bramel et. al, 1997)
• Outro exemplo
(Fisher, 1981)
• O problema crítico no uso efetivo das relaxações é a derivação de um bom
conjunto de multiplicadores para os problemas duais correspondentes
(Espejo, 2002);
• Dentre várias maneiras de se buscar o melhor valor para o multiplicador, o
que mais se destaca é o método do subgradiente, que é uma adaptação do
método do gradiente, no qual os gradientes são substituídos por
subgradientes;
•Dado um valor inicial u0 uma sequência de {uk} é expressa por:
uk+1 = uk + tk(Axk – b)
Onde xk é a solução ótima do problema ZD(u) e tk é um escalar positivo que
indica o tamanho do passo.
• Observa-se que a cada passo desloca-se na direção do gradiente, no
entanto, somente o movimento na direção do subgradiente de u não
assegura o aumento na função Z;
• Conforme sugere Polyak in Bramel (1997) é preciso dispor de passos com
valores (tamanhos) pré-determinados tk que farão com que a sequência
ZD(u)) venha a convergir para a solução ótima;
• De acordo com Fisher (1981), ZD(u)
Z se tk
0 ;
• A escolha do passo tk mais utilizada é:
tk 
k ( Z *  ZD(u k ))
Ax  b
k
2
Onde λk é um escalar que satisfaz 0 < λk <=2 e Z* é uma estimativa de
limite superior por aproximação de ZD que corresponde a melhor solução
obtida nos estágios iniciais de computação;
• Pode-se apontar que a escolha do tamanho do passo é uma área que não
é perfeitamente compreendida na atualidade (www.deps.ufsc.br/~mayerle).
Relaxação Lagrangeana para o DBAP
Minimizar T  k  1 Cij  Si  Aj  xijk   (T  k  1)Yijk
iB jV kO
iB jWi kO




   ijk   (Cil xilm  Yilm )  Yijk  ( Aj  Si ) xijk 
iB jWi kO


 jV mPk

i(1,..., I ) B
j(1,...T ) V
k (1,...T )O
Si
conjunto deberços
conjunto de navios
conjunto deordens de serviços
momentoem queoberçoi setorna disponível para o planejamento de alocação deberços
A
momento dechegada do navio j
j
C
ij
xi
jk
tempo de manipulação gasto pelo navio j noberçoi
1 seo navio j é atendidocomo o kth navio noberçoi
0 emcaso contrário
Pk é o subconjunt o de O talque Pk 
p/p kO
Wi é o subconjunt o de navioscom A j Si
Yijk é o momentodisponível do berço i entre a partidado k  1navioe a chegadado kth navioquando o navio j é atendidocomoo kth navio
Sujeito à:
 x
iB kO
x
jV
i jk
ijk
• Cada navio deve ser atendido por um
berço em uma seqüência de atendimento.
 j V
1
1
 i  B, k  O
xijk 0,1 i  B,
• Cada berço atende um navio por vez.
j V , k  O
Referências Bibliográficas
• BRAMEL, J. & SIMCHI-LEVI, D. in The Logic of logistics: theory, algorithms,
and applications for logistics management, Ed. Springer-Verlag, Nova Iorque,
1997.
• ESPEJO, L. G. A., GALVÃO R. D. O uso das relaxações Lagrangeana e
Surrogate em problemas de programação inteira. Pesquisa Operacional, v.22,
n.3, p.387-402, julho a dezembro de 2002;
• FISHER, M. L. The Lagrangian relaxation method for solving integer
programming problems. Management Science 27, 1-18, 1.981;
• LORENA, L. A. N., SENNE, E. L. F. Improving traditional subgradient scheme
for Lagrangean relaxation: an application to location problems;
•Relaxação Lagrangeana, em www.deps.ufsc.br/~mayerle, acesso em
19/10/2006;