Formulações e algoritmos sequenciais e paralelos para o problema da árvore geradora de custo mínimo com restrição de grau mínimo

AUTOR(ES)

Leonardo Conegundes Martinez

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

13/02/2012

RESUMO

Dados um grafo G não direcionado valorado nas arestas e um inteiro positivo d, o Problema da Árvore Geradora de Custo Mínimo com Restrição de Grau Mínimo(PAGMGM) consiste em encontrar uma árvore geradora de custo mínimo T de G, tal que o grau de cada vértice em T seja igual a 1 ou maior ou igual a d. O PAGMGM foi proposto recentemente e pertence à classe NP-Difícil para d >= 3. Neste trabalho, introduzimos formulações de Programação Inteira e algoritmos de otimização para o problema. Duas formulações baseadas em um número exponencial de restrições de eliminação de subcircuitos, uma direcionada e outra não direcionada, são apresentadas e comparadas sob uma perspectiva teórica e computacional em relação aos seus limites de Programação Linear. Dois métodos baseados na formulação direcionada foram propostos, um algoritmo Branch-and-cut e um método Local Branching. Este último emprega o algoritmo Branch-and-cut como resolvedor interno. Devido ao fato de a formulação direcionada não ser simétrica em relação aos limites de Programação Linear fornecidos, introduzimos uma reformulação compacta e simétrica para o problema, obtida com a aplicação de uma técnica de reformulação por interseção à formulação direcionada. Apesar da reformulação prover limites de Programação Linear muito mais fortes que aqueles fornecidos pelas demais formulações, a avaliação direta desses limites através de resolvedores de Programação Linear é muito cara computacionalmente. Por isso, introduzimos um algoritmo de Relaxação Lagrangeana para aproximá-los. Com o objetivo de acelerar o cálculo dos limites duais Lagrangeanos, implementamos um Método de Subgradiente paralelo. Introduzimos também uma Heurística Lagrangeana baseada no algoritmo Local Branching. Com os métodos propostos, vários novos certificados de otimalidade e melhores limites inferiores e superiores para o PAGMGM são fornecidos.

ASSUNTO(S)

computação teses.

Documentos Relacionados

• MODELS AND ALGORITHMS FOR THE DIAMETER CONSTRAINED MINIMUM SPANNING TREE PROBLEM
• Algoritmos para o problema da árvore geradora mínima probalística
• Abordagem de refinamento iterativo para o problema da árvore geradora com número mínimo de vértices Branch
• O problema da arvore de custo minimo com k arestas:: reformulações e relaxação lagrangeana
• Algoritmos paralelos para o problema da mochila.