\documentclass[11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{pifont}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}
\setlength{\evensidemargin}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\topmargin}{-30pt}
\pagestyle{empty}

\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}}  \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 3091 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{1cm}

\begin{center}
{\large\bf MAC 330 - Programação Inteira - MAC 5780 }
\end{center}

\begin{center}
{\bf Segundo semestre de 2002}
\end{center}

\begin{center}
{\large  Exercício 3 -- Entrega: {\bf 25 de novembro de 2002}}

\vspace{0.3cm}
Algoritmo de planos de corte
\end{center}

\noindent
Considere o seguinte problema. 
\begin{itemize}
\item \textbf{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. 
\end{itemize} 

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 \texttt{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 à \textsc{Steinlib}, que é uma biblioteca de instâncias do
Problema de Steiner, com vários resultados interessantes a respeito. 

\begin{verbatim}
http://elib.zib.de/steinlib/steinlib.php
\end{verbatim}

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 

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