Embora tenha sido proposto muito recentemente, o PAGMGM já despertou considerável interesse da comunidade acadêmica. O problema foi introduzido por Almeida et al. [2006], em um estudo que apresentou sua classe de complexidade computacional e algumas de suas propriedades. No mesmo trabalho, foram pro- postas formulações de Programação Inteira (PI), que empregam restrições de balan- ço de fluxo de uma ou de múltiplas mercadorias. Baseado nas formulações, foi tes- tado um algoritmo Branch-and-bound (BB) para a resolução de instâncias de bench- markpara o PAGMG [Narula & Ho, 1980; Krishnamoorthy et al., 2001], definidas em grafos com até 50 vértices. Para várias instâncias testadas, o algoritmo BB não foi capaz de fornecer o certificado de otimalidade após 3 horas de execução.
Além da dificuldade teórica associada ao PAGMGM, os resultados computa- cionais apresentados em [Almeida et al., 2006] indicam que as formulações de fluxo para o PAGMGM fornecem limites de Programação Linear (PL) mais fracos que aqueles dados por formulações equivalentes para o PAGMG. Esse resultado sugere ser mais difícil obter uma boa caracterização da envoltória convexa do PAGMGM que do PAGMG, considerando instâncias de dimensões e classes similares.
Akgún & Tansel [2010] apresentaram uma nova formulação para o PAGMGM baseada nas desigualdades de Miller-Tucker-Zemlin (MTZ) [Miller et al., 1960; Desrochers & Laporte, 1991] para eliminação de subcircuitos. Tais desigualdades foram introduzidas originalmente para o Problema do Caixeiro Viajante [Miller et al., 1960] e garantem, por meio de um número polinomial de restrições, que qual- quer subgrafo viável para o problema é conexo e acíclico.
Em geral, formulações que empregam as desigualdades MTZ fornecem limi- tes de PL mais fracos que os fornecidos por formulações de fluxo com múltiplas mercadorias [Langevin et al., 1990; Padberg & Sung, 1991; Desrochers & Laporte, 1991]. No caso particular do PAGMGM, experimentos computacionais relatados em [Akgún & Tansel, 2010] mostraram que, quando ambas as formulações consideram restrições de acoplamento propostas naquele estudo, entre variáveis de seleção de arestas e variáveis de seleção de vértices centrais, a diferença entre os limites de PL fornecidos por essas formulações é reduzida. Os autores também testaram um algo- ritmo BB utilizando a formulação MTZ que, comparado ao algoritmo BB proposto por Almeida et al. [2006], foi capaz de resolver um conjunto similar de instâncias de teste com menor esforço computacional. Utilizando o mesmo limite de tempo de 3horas, o algoritmo BB baseado na formulação MTZ resolveu todas as instâncias definidas em grafos com até 30 vértices, mas não conseguiu provar a otimalidade
2.2. REVISÃO BIBLIOGRÁFICA 9
para algumas instâncias com 50 vértices.
Pela primeira vez na literatura, Martins & Souza [2009] investigaram a apli- cação de métodos heurísticos para a resolução do PAGMGM. Os autores apresen- taram uma heurística construtiva gulosa, métodos baseados em algoritmos do tipo second order [Karnaugh, 1976; Martins, 2007] e heurísticas baseadas em diferentes implementações da meta-heurística Variable Neighborhood Search (VNS) [Mladenovi´c & Hansen, 1997].
A heurística construtiva gulosa proposta por Martins & Souza [2009] para o PAGMGM é uma adaptação do algoritmo clássico de Kruskal para o PAGM [Kruskal, 1956]. Tal algoritmo itera sobre o conjunto de arestas do grafo em or- dem não decrescente de custos, decidindo a cada iteração se a aresta em avaliação é incluída na solução ótima para o PAGM. A única diferença entre os dois métodos é a forma de avaliação das condições necessárias e suficientes para que uma aresta seja incluída na solução. No algoritmo de Kruskal, uma aresta é selecionada sempre que sua inclusão não forme um ciclo com as arestas já pertencentes à solução. Já na heurística para o PAGMGM, além desta condição, é necessário verificar também se a inclusão da nova aresta não impossibilita a construção de uma árvore geradora em que todos os vértices centrais tenham grau maior ou igual a d. Portanto, a in- clusão da aresta se dá sempre que a mesma não forma um ciclo com as arestas já selecionadas e não elimina a possibilidade da heurística encontrar uma árvore gera- dora viável para o PAGMGM. Caso contrário, a aresta é descartada. Cabe destacar que esta heurística construtiva sempre encontra uma árvore viável para o PAGMGM quando o problema é definido em grafos completos. No entanto, para grafos espar- sos, a heurística pode terminar sem encontrar uma árvore viável, ainda que exista alguma.
Os autores testaram também a aplicação direta para o PAGMGM de um al- goritmo do tipo second order proposto por Karnaugh [1976] e de uma versão apri- morada deste algoritmo (enhanced second order algorithm, ESO) proposta por Martins [2007]. O método ESO foi empregado na fase de melhoria de diferentes implemen- tações da meta-heurística VNS. Além destes, foi testado um método que apenas uti- liza a heurística construtiva para explorar cada vizinhança na meta-heurística VNS. Um total de sete heurísticas foram propostas e avaliadas para o PAGMGM em [Martins & Souza, 2009]. Os resultados computacionais mostraram que os métodos VNS randomizados que empregaram o ESO em suas fases de melhoria obtiveram os melhores limites superiores para o problema. Pela primeira vez na literatura, instân- cias com mais de 50 vértices foram testadas. Os autores aplicaram suas heurísticas em instâncias com até 500 vértices, estabelecendo parâmetros de comparação para
futuros trabalhos relacionados ao PAGMGM. A julgar pela nossa revisão bibliográ- fica, esse é o único trabalho publicado até o momento que aborda a aplicação de heurísticas para o problema.
Capítulo 3
Formulações de Programação Inteira
para o PAGMGM
Neste capítulo, introduzimos três novas formulações de Programação Inteira para o PAGMGM. As formulações são comparadas em relação aos seus limites de Programação Linear, sob uma perspectiva teórica e computacional. As duas for- mulações mais fracas, uma não direcionada e outra direcionada, são baseadas em um número exponencial de restrições de eliminação de subcircuitos, enquanto que a mais forte emprega um número polinomial de variáveis e restrições e resulta da aplicação da técnica de Reformulação por Interseção [Gouveia & Telhada, 2008]. Apresentamos algoritmos de planos de corte empregados para avaliar os limites de Programação Linear das formulações propostas, bem como novas desigualdades li- neares válidas para o problema, não redundantes para as formulações da literatura.
3.1 Introdução
Em geral, problemas de Programação Inteira podem ser formulados a partir de diferentes escolhas para os conjuntos de variáveis e restrições. No caso de pro- blemas de otimização em grafos, cujas soluções são representadas por árvores ge- radoras sujeitas a restrições complicantes adicionais, como limitação no diâmetro da árvore ou no grau dos vértices, é usual definir a formulação a partir de dois conjuntos independentes de restrições, aqui chamados de restrições de topologia de árvore geradora e restrições complicantes adicionais. Esses dois conjuntos de restrições devem garantir, respectivamente, que o subgrafo associado a uma solução viável seja acíclico e conexo e que as restrições complicantes adicionais do problema sejam satisfeitas. Para o caso particular do PAGMGM, o segundo conjunto deve impor as
restrições de grau mínimodos vértices de uma árvore geradora viável.
Várias abordagens podem ser utilizadas para definir o conjunto de restrições de topologia de árvore geradora [Magnanti & Wolsey, 1995]. Para o PAGMGM, foram apresentadas na literatura formulações baseadas em restrições de balanço de fluxo de uma ou de múltiplas mercadorias [Almeida et al., 2006] e em desigualdades de Miller-Tucker-Zemlin [Akgún & Tansel, 2010]. Uma vantagem das formulações baseadas em fluxos em redes e nas restrições MTZ é o fato de serem compactas, isto é, empregarem um número polinomial de variáveis e restrições. No entanto, o tamanho das formulações com múltiplas mercadorias, que envolvem O(nm) va- riáveis e restrições, torna-as proibitivas para a aplicação direta em procedimentos de enumeração como o Branch-and-bound, a menos que algum tratamento algorít- mico adicional seja empregado, por exemplo, o método de Relaxação Lagrangeana [Fischer, 1981; Guignard, 2003]. Por outro lado, formulações baseadas em fluxos de uma única mercadoria ou nas desigualdades MTZ apresentam em geral limites de Programação Linear fracos [Magnanti & Wolsey, 1995].
Introduzimos neste capítulo três formulações para o PAGMGM, duas baseadas em um número exponencial de restrições de eliminação de subcircuitos e outra baseada na técnica de Reformulação por Interseção. Na apresentação das formu- lações a seguir, são empregadas as seguintes notações e definições. Dado um grafo não direcionado G = (V, E) e um conjunto não vazio W ⊆ V , δ(W ) := {{i, j} ∈ E : i ∈ W, j 6∈ W } define o conjunto de arestas no corte induzido por W , ou seja, arestas com uma extremidade em W e a outra extremidade em V \ W, e E(W ) := {{i, j} ∈ E : i, j ∈ W } define o conjunto de arestas com ambas as extremidades em W . Da mesma forma, dado um grafo direcionado D = (V, A) com conjunto de arcos A e os conjuntos não vazios S ⊂ V e W ⊂ V , (S, W ) := {(i, j) ∈ A : i ∈ S, j ∈ W }define o conjunto de arcos que partem de S para W , δ−(W ) := {(i, j) ∈ A : i 6∈ W, j ∈ W }define o conjunto de arcos que inci-
dem em W a partir de V \ W , δ+(W ) := {(i, j) ∈ A : i ∈ W, j 6∈ W }define o conjunto
de arcos que partem de W para V \ W e A(W ) := {(i, j) ∈ A : i ∈ W, j ∈ W } define o conjunto de arcos com ambas as extremidades em W . Para simplificar, quando W = {i}, os conjuntos δ({i}), δ−({i})e δ+({i})são representados respectivamente
por δ(i), δ−(i)e δ+(i).
Dada uma formulação P para o PAGMGM, assuma que w(P ) indique o limite de Programação Linear fornecido por P . Se P é definido em termos de um conjunto estendido de variáveis (x, z), sua projeção no espaço das variáveis z é denotado por P rojz(P ). Considere ainda que B := {0, 1} e que R denote o conjunto dos números
3.2. FORMULAÇÕES COM UM NÚMEROEXPONENCIAL DERESTRIÇÕES DE
ELIMINAÇÃO DESUBCIRCUITOS 13
Qe Q ⊆ Q, defina f(Q) := Pq∈Qfq.