A relaxação Lagrangeana/surrogate e o método de geração de colunas: novos
limitantes e novas colunas
1. Introdução
Os recentes avanços em informática, com a construção de equipamentos mais
rápidos e confiáveis, proporcionaram o desenvolvimento de sistemas mais
robustos para Programação Matemática (CPLEX (1999)), permitindo a resolução de
problemas de grande porte. Tais ferramentas permitem que problemas
inerentemente complexos também possam ser resolvidos em tempo computacional
aceitável, através da utilização de técnicas combinadas como, por exemplo, o
Método de Geração de Colunas aplicado a problemas de Programação Inteira.
Baseado no trabalho de Dantzig & Wolfe (1960), a primeira aplicação prática
desta técnica foi na determinação de padrões de corte unidimensionais (Gilmore
& Gomory (1961), (1963)) e, desde então, seu uso difundiu-se de forma
intensa (Cook & Rich (1999), Cordeau et al. (2000), Day & Ryan (1977),
Desrochers & Soumis (1989), Desrochers et al. (1992), Lorena & Senne
(2002), Neame (1999), Savelsbergh (1997), Senne & Lorena (2001), Valério de
Carvalho (1996), Vance (1993) e Vance et al. (1994)).
A técnica de geração de colunas pode ser aplicada a problemas lineares de
grandes dimensões, no caso de não se dispor de todas a colunas a priori, ou
quando se pretende resolver um problema utilizando a decomposição de Dantzig-
Wolfe, onde as colunas correspondem aos pontos extremos do conjunto convexo de
soluções factíveis do problema. Neste caso, o algoritmo para resolução alterna
entre um subproblema e um problema mestre restrito. A partir de um conjunto
inicial de colunas, resolve-se o problema mestre, obtendo-se as variáveis duais
que serão utilizadas pelo subproblema para determinar novas colunas a serem
consideradas no problema mestre.
Abordagens baseadas na técnica de geração de colunas têm aparecido em um grande
número de trabalhos recentes em alternativa aos métodos não lineares baseados
em relaxação Lagrangeana (métodos de subgradientes, bundle) para resolver
problemas inteiros de grande porte (Barnhart et al. (1998)). Uma pesquisa no
Web of Science em 27/11/2001, com o argumento "column generation",
retornou 220 trabalhos, 93 apenas nos últimos 3 anos.
Sabe-se que aplicação direta do método de geração de colunas freqüentemente
produz um número muito grande colunas que não são relevantes para a solução
final, comprometendo assim a convergência para a solução do problema e
produzindo os chamados problemas de estabilização. Nestes casos, observa-se que
as variáveis duais oscilam em torno da solução dual ótima, logo métodos que
previnam tal comportamento podem acelerar a resolução do problema. Dentre estes
merecem destaque: Método Boxstep(Marsten et al. (1975)), que restringe o espaço
de busca de soluções duais a uma região limitada tendo a solução dual atual
como centro; Método Analytic Centre Cutting Plane (du Merle et al. (1998)), que
usa o centro analítico de uma região da função dual como solução, no lugar da
solução ótima, não permitindo assim mudanças muito drásticas entre as soluções
duais de duas iterações consecutivas; Métodos Bundle (Marsten et al. (1975)),
que combinam regiões de confiança e penalizações para que as soluções duais não
variem muito de uma iteração para outra. Outros métodos estão descritos em
Neame (1999).
Neste trabalho pretende-se explorar a equivalência entre o método de geração de
colunas, resultante da Decomposição de Dantzig-Wolfe do problema original, e o
Método de Planos de Corte (Kelley (1960)) para resolver o problema Lagrangeano
associado. Nossa proposta é discutir e sugerir temas de pesquisas decorrentes
da aplicação da relaxação Lagrangeana/surrogate descrita em Narciso &
Lorena (1999) como uma alternativa de estabilização do processo de geração de
colunas, visando obter soluções duais de melhor qualidade, acelerando a
resolução do problema original.
O trabalho está organizado da seguinte forma. Na Seção 2 descrevemos de forma
abreviada o processo de geração de colunas, a decomposição de Dantzig-Wolfe e a
relaxação Lagrangeana, aplicados a um problema de programação linear inteira.
Na Seção 3 descrevemos o uso combinado da relaxação Lagrangeana/surrogate e o
método de geração de colunas. Algumas possíveis aplicações são propostas na
Seção 4 e na Seção 5 são apresentadas algumas questões em aberto sobre o
assunto.
2. Geração de colunas
Problemas de Programação Inteira consideram a otimização de uma função objetivo
sujeita a restrições sobre as variáveis, sendo que algumas ou todas as
variáveis devem assumir valores inteiros. Em particular, pode-se considerar que
a função objetivo e as equações que formam o conjunto de restrições do problema
sejam lineares.
Para facilidade de exposição, considere o seguinte problema de Programação
Inteira:
sendo x o vetor n-dimensional das variáveis inteiras do problema.
O conjunto de restrições x = 
pode ser particionado de forma a obter dois
conjuntos de restrições, onde um deles apresente alguma estrutura que possa ser
explorada de forma vantajosa. Assim, após o particionamento, o problema pode
ser reescrito como:
Definindo W = Zn Ç {x : A'x = b'}, o problema será reformulado como:
Supondo que o conjunto W é finito, ou seja, o poliedro representado por {x :
A'x = b'} é limitado, e {xk : k Î K} é o conjunto dos pontos extremos da
envoltória convexa de W, conv(W), todo ponto x Î W pode ser escrito como a
seguinte combinação linear convexa de um número finito de pontos extremos de W:
2.1 Relaxação Lagrangeana
Sendo l o vetor das variáveis duais associadas às restrições Ax = b, a
relaxação Lagrangeana de (2.2) está dada por:
Considerando o conjunto de todos os pontos extremos de conv(W), e observando
que otimizar zRL(l) é equivalente a maximizar uma função linear sobre W, então
existe um ponto extremo de conv(W) que corresponde ao valor máximo. Assim,
(2.4) pode ser reescrito como:
que é uma função convexa linear por partes em l.
O melhor valor de limitante superior para zLR(l) é obtido resolvendo o problema
dual Lagrangeano:
que pode ser reescrito como:
ou como o seguinte problema de Programação Linear:
Em problemas com um grande número de variáveis (colunas), onde o conjunto K dos
índices dos pontos extremos de conv(W) não é conhecido a priori, Kelley (1960)
propõe utilizar as soluções duais ótimas [/img/revistas/pope/v23n1/
a04img07.gif] e <formula/> de (2.5), obtidas numa
dada iteração l para algum Kl Í K, no seguinte subproblema:
obtendo a solução ótima <formula/>. A diferença
zSP(<formula/>) ' [/img/revistas/pope/v23n1/
a04img11.gif] é chamada custo reduzido, e quando zSP([/img/revistas/pope/v23n1/
a04img10.gif]) < <formula/>, então o conjunto Kl
contém uma base ótima para o problema original, caso contrário, a restrição (ou
corte) c<formula/>'[/img/revistas/pope/v23n1/
a04img10.gif]A<formula/> é incorporada como uma
nova linha ao problema (2.5), faz-se Kl+1 = Kl È {[/img/revistas/pope/v23n1/
a04img12.gif]} e o problema é novamente resolvido. Como proposta para acelerar
a resolução do problema original, qualquer coluna xpsatisfazendo [/img/
revistas/pope/v23n1/a04img11.gif] < cxp - [/img/revistas/pope/v23n1/
a04img10.gif] A xp pode ser incluída ao conjunto Kl.
Este método é equivalente ao processo de geração colunas que será apresentado a
seguir, e resulta do fato que o dual do problema (2.5) equivale ao Problema
Mestre obtido da relaxação de Programação Linear da decomposição de Dantzig-
Wolfe do problema original.
2.2 A Decomposição de Dantzig-Wolfe
Uma outra proposta para resolver (2.1) de forma ótima consiste em utilizar a
representação das soluções como combinação linear dos pontos extremos do espaço
de otimização diretamente na formulação do problema. Nesse sentido,
substituindo a expressão (2.3) na formulação (2.2) tem-se a seguinte
decomposição de Dantzig-Wolfe:
Tomando a relaxação de Programação Linear do problema acima, ou seja,
permitindo que x Î conv(W), tem-se o seguinte problema mestre:
Numa dada iteração l do método de geração de colunas, seja Kl Í K um
subconjunto dos pontos extremos de conv(W), definindo o seguinte problema
mestre restrito:
Sendo <formula/> e [/img/revistas/pope/v23n1/
a04img11.gif] as soluções duais ótimas de (2.8), novas colunas podem ser
calculadas como soluções do subproblema (2.6). As colunas xp que satisfizerem:
cxp ' <formula/>Axp '[/img/revistas/
pope/v23n1/a04img11.gif] > 0
(custos reduzidos positivos) são incluídas em (2.8) e o problema mestre
restrito é novamente resolvido, até que não seja mais possível obter colunas
que melhorem o valor ótimo de (2.7).
O seguinte algoritmo geral pode ser adaptado para resolver problemas através do
método de geração de colunas:
Passo_0: Determine um conjunto inicial K0 de colunas para o problema mestre.
Faça l = 0;
Passo_1: Resolva a relaxação de Programação Linear do problema mestre restrito;
Passo_2: Utilize os valores duais ótimos obtidos no passo anterior e resolva um
subproblema para obter novas colunas <formula/> em
W;
Passo_3: Adicione as colunas <formula/> com custos
reduzidos positivos à formulação do problema mestre restrito. Se não houver
tais colunas, então PARE ® solução ótima.
Passo_4: Caso contrário, faça Kl ¬K È {[/img/revistas/pope/v23n1/
a04img12.gif]}, l ¬l + 1 e vá para o passo 1;
3. A Relaxação Lagrangeana/surrogate e a geração de colunas
3.1 A relaxação Lagrangeana/surrogate
A relaxação Lagrangeana/surrogate combina de forma eficiente as relaxações
Lagrangeana e surrogatede um determinado problema. A relaxação Lagrangeana é
usada após a aplicação de uma relaxação do tipo surrogate em um conjunto de
restrições pré-escolhido, onde as restrições são substituídas por apenas uma,
modificada por um multiplicador multidimensional. Em seguida toma-se a
relaxação Lagrangeana da restrição surrogate obtida. Isto induz a um dual local
Lagrangeano na variável unidimensional, e esta otimização local tende a
corrigir a norma do vetor de subgradientes, evitando fortes oscilações em
métodos de otimização do dual Lagrangeano que usam subgradientes como direção
de busca.
A relaxação Lagrangeana/surrogate foi aplicada com sucesso em diversos
problemas de natureza combinatória (Lorena & Pereira (2002), Lorena &
Senne (2002), Lorena et al. (2001), Narciso & Lorena (1999), Pereira &
Lorena (2001), Senne & Lorena (2000)). A otimização local (dual Lagrangeano
local) não necessita ser exata e uma busca unidimensional do tipo dicotômica é
empregada. Esta otimização também não se mostrou necessária em todos os passos
de métodos subgradientes, bastando encontrar o valor do multiplicador por
algumas iterações iniciais.
Sendo l o multiplicador surrogate associado às restrições Ax = b, e t > 0 o
multiplicador Lagrangeano associado à restrição surrogatelAx = lb, a relaxação
Lagrangeana/surrogate de (2.2) está dada por:
É imediato que para t = 1, zRL (l)1 é a relaxação Lagrangeana usual (2.4). O
multiplicador t é conhecido como multiplicador Lagrangeano/surrogate, e seu
melhor valor t* é obtido fixando-se l e resolvendo-se por busca dicotômica o
dual local:
3.2 Novos limitantes para geração de colunas
O processo de geração de colunas é geralmente instável (du Merle et al.
(1999)). As colunas selecionadas podem melhorar marginalmente o valor da função
objetivo do problema mestre, ou mesmo este valor pode ficar inalterado durante
muitas iterações. Neste caso não se sabe se o processo está convergindo ou
simplesmente está parado em algum ponto. O uso de limitantes superiores pode
dar uma indicação de convergência do método de geração de colunas. Nesta sessão
vamos apresentar o limite Lagrangeano/surrogate derivado diretamente do
processo de geração de colunas, usando a variável dual multidimensional obtida
na solução ótima do problema mestre restrito. Vamos mostrar também que o limite
Lagrangeano e um limite conhecido como Limite de Farley (1990) são derivados
diretamente do limite Lagrangeano/surrogate.
Vamos verificar o que ocorre quando um multiplicador Lagrangeano/surrogate é
usado no custo reduzido. Tem-se:
ou equivalentemente:
CRt > {cx ' tlAx} ' m , "x ÎW, e {cx ' tlAx} < CRt +m , "x
ÎW,
o que indica que (tl, CRt +m) é uma solução viável para o problema (2.5).
Portanto, como (2.8) e (2.5) são problemas primal e dual, tem-se
o que indica que tlb + CRt +m é um limite superior ao valor do problema mestre
restrito.
Reescrevendo tlb + CRt +m, tem-se <formula/>{cx +
tl(b ' Ax)}, que é a relaxação Lagrangeana/surrogate para os multiplicadores l
e t.
Os seguintes casos particulares podem ocorrer:
* para t = 1:
Tem-se zPMR < l b + CR1 + m =<formula/> {cx
+ l (b ' Ax)}, que é o limite Lagrangeano tradicional (2.4);
* para t = t*, solução de (3.2):
Tem-se zPMR < t*lb + CRt* + m = <formula/>
{cx + t*l (b ' Ax)}, que é o melhor limite Lagrangeano/surrogate (3.1); e
* para t0 tal que<formula/> {cx ' t0lAx} = 0:
Tem-se zPMR < t0l b, que é conhecido como limite de Farley para o caso
particular em que c > 0 e x > 0.
É imediato que <formula/> {cx + t*l(b ' Ax)} < [/
img/revistas/pope/v23n1/a04img15.gif] {cx + l(b ' Ax)}, e que [/img/revistas/
pope/v23n1/a04img15.gif] {cx + t*l(b ' Ax)} < t0lb, pois 1 ¹ t0 ¹ t* (em
geral). Portanto o melhor limite Lagrangeano/surrogate supera os limitantes
Lagrangeano e o de Farley (quando este existe).
O limite Lagrangeano/surrogate foi usado nas aplicações de p-medianas (Senne
& Lorena (2001) e Lorena & Senne (2002)) para acelerar o processo de
parada do algoritmo de geração de colunas, apresentado na seção 2.2. O Passo 3
do algoritmo foi substituído por:
Passo_3a: Adicione as colunas <formula/> com
custos reduzidos positivos à formulação do problema mestre restrito. Se não
houver tais colunas ou se [ <formula/>{cx + t*l(b
' Ax)} ' zPMR] < 1, então PARE ® solução ótima.
A Figura_1 mostra um comportamento típico dos limites Lagrangeano e
Lagrangeano/surrogate quando combinados com o processo de geração de colunas,
para um problema de p-medianas com 900 vértices e 300 medianas (Senne &
Lorena (2001)).
3.3 Gerando novas colunas
O subproblema gerador de colunas (2.6) pode ser modificado pelo multiplicador
Lagrangeano/surrogate calculado em (3.2), obtendo-se o novo subproblema
Para t ¹ 1, os problemas (2.6) e (3.4) podem produzir colunas diferentes. Se as
colunas xpobtidas em (3.4) satisfizerem cxp 'l Axp ' m > 0, estas poderão
entrar como novas colunas no problema mestre restrito.
Senne & Lorena (2001) formularam o problema das p-medianas como um problema
de particionamento de conjuntos. Na aplicação da técnica de geração de colunas,
a relaxação Lagrangeana/surrogate demonstrou ser uma excelente alternativa para
estabilização do método, fornecendo colunas mais produtivas que o método
tradicional de geração de colunas, acelerando a solução do problema.
A Tabela_1 mostra um experimento realizado em uma instância do problema de p-
medianas com 200 vértices e 5 medianas (Senne & Lorena (2001)). Foi imposto
um número máximo de colunas através de uma medida limite para o custo reduzido
das colunas presentes no problema mestre restrito. Os números entre parêntesis
representam o método tradicional de geração de colunas enquanto que os outros
resultados referem-se ao uso das colunas obtidas em (3.4) para t = t*, solução
de (3.2).
A Figura_2 ilustra os resultados da Tabela_1. Observe que mesmo quando um
limite pequeno de colunas é admitido ao problema mestre restrito essas colunas
são produtivas quando calculadas pela expressão (3.4). O método tradicional de
geração de colunas permaneceu sem melhora de limites por muitas iterações.
As tabelas_3 e 4 mostram testes computacionais (extraídos de Lorena & Senne
(2002)), onde são consideradas instâncias de larga escala com uma aplicação ao
problema capacitado de p-medianas. Foi considerada a instância Pcb3038, obtida
da TSPLIB (Reinelt (1994)), e modificada para contemplar as capacidades nos nós
da rede. Estas capacidades foram então geradas, como:
e o número máximo de colunas admissíveis no problema mestre foi fixado em
20000. Estas instâncias estão disponíveis em http://www.lac.inpe.br/~lorena/
instancias.html. Como pode-se observar diretamente nas tabelas, a combinação da
relaxação Lagrangeana/surrogate com o processo de geração de colunas foi capaz
de obter resultados computacionais de qualidade na metade do tempo usado pelo
processo tradicional de geração de colunas.
4. Algumas aplicações
A relaxação Lagrangeana/surrogate foi aplicada a diversos problemas de
Otimização Combinatória. O método tradicional de subgradientes foi usado na
otimização do dual. Nesta seção descrevemos algumas possíveis aplicações do uso
combinado de geração de colunas e a relaxação Lagrangeana/surrogate. Algumas
dessas aplicações já estão sendo desenvolvidas no LAC/INPE.
Somente o problema gerador de colunas correspondente a (3.4) será formulado e
examinado para cada aplicação. Uma formulação completa dos problemas pode ser
consultada em outros trabalhos (Cordeau et al. (2000), du Merle et al. (1999),
Galvão (1981), Lorena & Senne (2002), Minoux (1987), Neame (1999),
Savelsbergh (1997), Senne & Lorena (2001), Swain (1974), Valério de
Carvalho (1996), Vance et al. (1994), Wolsey (1998)). Em todas as formulações
que seguem, as variáveis duais l são obtidas da solução do correspondente
problema mestre restrito, e o respectivo multiplicador Lagrangeano/surrogate t
é obtido resolvendo-se o problema (3.2).
4.1 Problema das p-medianas
O problema de p-medianas consiste em decidir onde localizar p centros em uma
rede composta por vértices e arestas, de forma a minimizar a soma de todas as
distâncias de cada vértice ao centro mais próximo. Em alguns casos, quando uma
demanda estiver associada a cada vértice, pode haver restrições na capacidade
de atendimento dos centros (problema de p-medianas com restrições de
capacidade) (Lorena & Senne (2002), Senne & Lorena (2001)).
Para o problema das p-medianas, a decomposição de Dantzig-Wolfe resulta no caso
especial de conjunto ilimitado de pontos extremos, onde as restrições de
convexidade não estarão presentes na formulação do problema mestre restrito.
Entretanto, para problemas de clustering como este, aparecerá uma restrição
adicional no problema mestre restrito. Esta restrição é do tipo
Esta restrição impõe que o número de medianas (clusters) deve ser respeitado.
Neste caso o subproblema gerador de colunas será dado por:
onde [dij]nx n é uma matriz simétrica que representa os custos (distâncias)
entre os pontos i e j. Observe que dii = 0, "i Î N = {1, ..., n}. O
subproblema (4.2) é resolvido por inspeção, verificando-se o sinal dos
coeficientes (dij - tl j)de yj.
Para o caso capacitado, o subproblema gerador de colunas será:
onde Qi é a capacidade do nó i e qj é a demanda do nó j. Este problema é o
conhecido Problema da Mochila, da classe NP-hard, mas bem resolvido para
instâncias grandes por algoritmos tipo branch-and-bound.
Seja g a variável dual do problema mestre restrito correspondente à restrição
(4.1). Se as colunas <formula/> obtidas em (4.2) e
(4.3) satisfizerem <formula/> (dij- pj )yj< | g |,
estas poderão entrar como novas colunas no problema mestre restrito.
A solução dos problemas (4.2) e (4.3) pode ser sensivelmente alterada por
diferentes valores de t. Em Lorena & Senne (2002) e Senne & Lorena
(2001) verificou-se, em testes computacionais, que quando t* (melhor
multiplicador Lagrangeano/surrogate) é usado em (4.2) e (4.3), seus valores
ficaram restritos ao intervalo (0,1] (tendendo a 1 quando o processo converge)
e uma análise simples com estes valores nas expressões (4.2) e (4.3) mostrou
que colunas de menor custo são selecionadas no problema mestre restrito como
conseqüência de um menor numero de centros alocados aos clusters. Ainda estamos
verificando se este comportamento é repetido em outros problemas.
4.2 Problema generalizado de atribuição
O problema generalizado de atribuição consiste em encontrar a maneira mais
vantajosa de distribuir n tarefas a m máquinas de modo que cada tarefa seja
atribuída a uma única máquina que possui capacidade limitada.
Tal como o problema de p-medianas este também é um problema de clustering e as
restrições adicionais ao problema mestre restrito serão da forma:
Após a resolução do respectivo problema mestre restrito, a busca por novas
colunas pode ser realizada resolvendo os seguintes subproblemas da mochila
(para i = 1, ..., m) (Savelsbergh (1997)):
onde:
' wij é um número positivo inteiro que representa o tempo que a
máquina i leva para fazer o trabalho j, quando i está alocada para j;
' ci é um inteiro positivo que representa o tempo total disponível da
máquina i;
' pij é um inteiro positivo que representa o lucro produzido quando a
máquina i está alocada para j.
Seja vi o custo dual ótimo associado à restrição (4.4) correspondente ao agente
i no problema mestre restrito. Se para algum i, [/img/revistas/pope/v23n1/
a04img19.gif] (pij- lj )yij> 0, então a coluna [/img/revistas/pope/v23n1/
a04img20.gif] pode ser adicionada ao problema mestre restrito.
As soluções dos problemas (4.5) podem ser sensivelmente alteradas por
diferentes valores de t. É imediato que valores de t restritos ao intervalo
(0,1] favorecem a escolha de colunas de maior retorno.
4.3 Problema de roteamento de veículos com janelas de tempo
Sejam V o conjunto de veículos (idênticos) e C = {1, ..., n} o conjunto de
clientes a serem atendidos, interligados a um depósito por um grafo direcionado
(Cook & Rich (1999), Cordeau et al. (2000), Desrochers et al. (1992),
Homberger (2001), Kallehauge et al. (2000)). Usando os multiplicadores duais
li, iÎC, os coeficientes que serão utilizados na função objetivo de cada
subproblema k ÎV serão dados por:
O subproblema k Î V será o seguinte problema de caminho mínimo com restrições
de tempo e capacidade (Cordeau et al. (2000)):
Nas restrições (4.6) impõe-se que a demanda total dos clientes atendidos por
cada veículo não deve exceder sua capacidade. Os três conjuntos de restrições a
seguir são restrições de fluxo: as restrições (4.7) impõem que cada veículo
deve deixar o depósito uma única vez; (4.8) especificam que cada cliente
visitado é deixado e (4.9) garantem que todos os veículos devem retornar ao
depósito apenas uma vez. As restrições de precedência (4.10) determinam que um
veículo, partindo do cliente i, não deve chegar ao cliente j antes do instante
sik + tij, onde M é um valor arbitrariamente grande. As restrições (4.11)
garantem que o início de atendimento de cada cliente seja executado dentro do
intervalo especificado pela sua janela de tempo. A natureza binária das
variáveis yijk é dada pelo conjunto de restrições (4.12).
O vetor de multiplicadores duaisl = (l1, ..., l|C|) reflete o custo de
atendimento de cada cliente i ÎC. Por definição, li é irrestrito em sinal e t >
0. Os custos dos arcos para o subproblema são calculados como em (4.6). Se
predominantemente tli > cij, o subproblema tenderá a produzir rotas mais
longas. Caso o predomínio seja de tli < cij, então haverá preferência por rotas
mais curtas. Kohl (1995) observa que a dificuldade de resolução do subproblema
é diretamente proporcional à norma dos multiplicadores envolvidos.
Para valores de t próximos de 0, a norma do vetor lé sempre modificada de forma
que rotas mais curtas sejam produzidas em maiores quantidades (mais colunas são
geradas). À medida que t tende para 1, os valores de li, i Î C, contribuem mais
efetivamente para a determinação do comprimento das melhores rotas.
4.4 Problema simétrico do caixeiro viajante
Considere um Problema do Caixeiro Viajante definido em um grafo G = (V,E), V =
{1, ..., n}, e seja a variável bináriayij igual a 1 se a aresta (i, j) Î E é
usada no caminho ótimo do caixeiro. Define-se ainda a matriz de custos (ou
distâncias) C = [ cij], onde cij= cjipara todo i, j ÎV, que está associada a E
(Reinelt (1994)).
O subproblema será o seguinte (Wolsey (1998)):
onde y é uma solução viável para o problema de 1-árvore geradora de peso
mínimo, que pode ser obtida tomando a arvore geradora de menor custo possuindo
o conjunto de vértices V\{1} e duas arestas distintas de mínimo custo que ligam
esta árvore ao vértice 1.
A matriz de custos de (4.13) é cij - tlk que representa os custos modificados
das arestas do grafo original. É imediato que um valor de t ¹ 1 pode modificar
a solução do problema de 1-árvore geradora de peso mínimo. Em particular, se os
valores de t* ficarem restritos ao intervalo (0,1], colunas de menor custo
seriam selecionadas no problema mestre restrito como conseqüência de uma
redução no custo das 1-árvores que tendem a tours do caixeiro em sua seqüência
de soluções.
4.5 Problema binário de cortes
O problema binário de cortes consiste em determinar o número mínimo de rolos de
comprimento L necessários para atender uma demanda de rolos de comprimentos
menores ai, i = 1, ..., n (Vance (1993), Vance et al. (1994)).
Neste caso, as colunas do problema mestre restrito representam padrões de corte
factíveis para uma peça de comprimento L. Assim, os novos padrões (colunas) são
gerados resolvendo o seguinte subproblema da mochila 0-1:
onde yi = 1 se o item i está presente na nova coluna, ou yi = 0, caso
contrário.
Sabe-se que o limite Lagrangeano/surrogate deve ser um bom limite dual para
este problema. Seja yv uma solução viável para o problema (4.14)-(4.16). A
consideração do melhor valor do multiplicador Lagrangeano/surrogate pode
favorecer a determinação de tais soluções, produzindo colunas distintas da
abordagem tradicional (t = 1). Se o custo reduzido, dado por (1 ' lyv), for
negativo, então a coluna respectiva é candidata a entrar no problema mestre
restrito.
5. Questões em aberto
A complementação da teoria existente poderá ser feita através da formalização
de resultados provenientes da resposta de algumas questões, como por exemplo:
a) Limitantes: Sabe-se que a relaxação Lagrangeana/surrogate fornece
limitantes de melhor qualidade que a relaxação Lagrangeana usual
(Narciso & Lorena (1999)). Pretende-se estabelecer relações entre
os limitantes obtidos com estas relaxações e outros obtidos para esta
classe de problemas, como por exemplo o de Farley (1990), específico
para implementações com geração de colunas;
b) Métodos_de_estabilização: Avaliar a influência da relaxação
Lagrangeana/surrogate e estabelecer relações com outros métodos de
estabilização da técnica de geração de colunas (métodos de
subgradientes, bundle, Boxstep, Analytic Centre Cutting Plane).
Verificar se tais métodos podem se beneficiar ao serem combinados com
a relaxação Lagrangeana/surrogate;
c) Complexidade_do_subproblema_de_geração_de_colunas: A relaxação
Lagrangeana/ surrogate, quando aplicada a problemas com restrições
adicionais de capacidades (mochilas) sofreu adaptações para permitir
o cálculo do multiplicador Lagrangeano/ surrogate (abreviação no
processo de busca de t). Serão conduzidos estudos para avaliar como
essa busca seria afetada no caso combinado com a geração de colunas;
d) Resolução_do_subproblema: Sabe-se que o subproblema gerador de
colunas não precisa ser resolvido na otimalidade para gerar novas
colunas para o problema mestre restrito. Pretende-se explorar a
influência do multiplicador Lagrangeana/surrogate no processo de
geração de colunas, considerando-o na elaboração de novas heurísticas
para o subproblema gerador de colunas;
e) Gerenciamento_do_número_de_colunas: Estudar o gerenciamento do
número de colunas a serem consideradas no problema mestre restrito.
Avaliar o compromisso quantidade ´ qualidade das colunas obtidas dos
subproblemas (em Senne & Lorena (2001), a relaxação Lagrangeana/
surrogate permitiu resolver problema de p-medianas com menos
colunas);
f) Relaxação_Lagrangeana/surrogate_e_o_branch-and-price: o Método
Branch-and-Price (Barnhart et al. (1998)) utiliza a técnica de
geração de colunas em cada nó de uma árvore de busca branch-and-bound
para obtenção de novas variáveis não básicas para o problema. Será
explorada a possibilidade de adaptar a combinação relaxação
Lagrangeana/surrogate e geração de colunas ao branch-and-price e
verificar se há vantagens nessa adaptação.
6. Conclusões
Neste trabalho destacamos o uso da relaxação Lagrangeana/surrogate como um
processo de estabilização do método de geração de colunas. Alguma experiência
computacional foi reproduzida para o problema das p-medianas e outros problemas
foram sugeridos para teste do algoritmo de estabilização.
A combinação da relaxação Lagrangeana/surrogate com o método de geração de
colunas é feita através da teoria de decomposição de Dantig-Wolfe e o método de
Kelley. Na identificação do limite Lagrangeano/surrogate é usado o
multiplicador dual que surge na resolução do problema mestre restrito. A
exploração desses limites ainda está em aberto. Assim como estão abertas várias
questões colocadas no trabalho referentes ao uso eficiente do multiplicador
Lagrangeano/surrogate no processo de geração de colunas.
As aplicações sugeridas são exemplos que estão sendo estudados no LAC/INPE, mas
várias outras aplicações podem ser testadas, incluindo problemas de scheduling
e novos problemas de clustering.
