MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3091 6140

E-MAIL cef@ime.usp.br

MAC 330 - Programação Inteira - MAC 5780

Segundo semestre de 2002

Exercício 3 - Entrega: 25 de novembro de 2002

Algoritmo de planos de corte

Considere o seguinte problema.

• Problema de Steiner em Grafos
  Dado um grafo $G=(V,E)$, uma função de custo $c_e \ge 0$ nas arestas de $G$, e um conjunto de vértices $Z \subseteq V$, desejamos encontrar um conjunto de arestas $S \subseteq E$ tal que para todo par de vértices $u,v \in Z$ existe um caminho ligando $u$ a $v$ que só usa arestas de $S$. Além disso, este conjunto de arestas deverá ter custo mínimo.

O objetivo deste exercício-programa é escrever um programa baseado no método dos planos de corte para o problema. Você poderá escolher qualquer formulação que desejar para o problema, e poderá incluir planos de corte de qualquer tipo: cortes de Gomory, cortes faciais, etc. Note que você deverá resolver um problema de programação linear em cada iteração. Para isso, precisará utilizar uma biblioteca de funções como, por exemplo, a biblioteca soplex (feita em C++) recentemente instalada na rede do IME.

Para testar seu programa, assim como ter idéias sobre que formulação ou corte utilizar, acesse à STEINLIB, que é uma biblioteca de instâncias do Problema de Steiner, com vários resultados interessantes a respeito.

http://elib.zib.de/steinlib/steinlib.php

Na biblioteca diferentes tipos de problemas estão presentes. Para vários deles é conhecida a solução ótima, mas para alguns o valor ainda está em aberto. Você também poderá encontrar várias dicas a respeito no capítulo 5 do livro

Combinatória Poliédrica e planos de corte faciais
Carlos E. Ferreira e Yoshiko Wakabayashi
X Escola de Computação, Campinas, 1996.
http://www.ime.usp.br/$\sim$yw/livros/livro-new.ps.gz