Um Algoritmo Branch-and-Cut para o Problema de
Steiner com Grupos
Fernando Mario de Oliveira Filho
Orientador: Prof. Dr. Carlos Eduardo Ferreira
Supervisora: Profa. Dra. Yoshiko Wakabayashi
Projeto baseado na Iniciação Científica
Resumo
Neste trabalho abordamos o problema de Steiner com grupos, que
consiste em dado um grafo com custos nas arestas e uma coleção de
subconjuntos do conjunto de vértices, encontrar um subgrafo que
conecte pelo menos um vértice de cada conjunto da coleção e que tenha
custo mínimo. O problema é uma generalização do problema de Steiner em
grafos e surge naturalmente no desenvolvimento de circuitos
VLSI. Apresentamos estudos feitos para o desenvolvimento de um
algoritmo seguindo a estratégia branch-and-cut para o
problema. O trabalho se baseia num projeto de iniciação científica que
teve apoio da FAPESP e que foi desenvolvido desde Agosto de 2001 até
Agosto de 2003.
O Programa
O programa foi feito em linguagem C
usando a biblioteca de programação linear GLPK da GNU. Para
instalar o programa descompacte o arquivo e leia instruções no
arquivo README.
O formato de entrada dos arquivos é parecido com o formato da Steinlib.
Disponibilizamos um pacote com
alguns exemplos pegos da Steinlib e convertidos para o novo
formato.
Fernando Mario de Oliveira Filho
<fmario@linux.ime.usp.br>
Segunda, 6 de Dezembro 2003