Home   |   Structure   |   Research   |   Resources   |   Members   |   Training   |   Activities   |   Contact

EN | PT

BrBRCEEn0101-74382003000100004

BrBRCEEn0101-74382003000100004

National varietyBr
Country of publicationBR
SchoolEx-Tech-Multi Sciences
Great areaEngineering
ISSN0101-7438
Year2003
Issue0001
Article number00004

Javascript seems to be turned off, or there was a communication error. Turn on Javascript for more display options.

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 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 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 i e qj é a demanda do 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 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 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 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.


Download text