The first part of this thesis addresses the Packing of Two Steiner Trees Problem,
which is NP-hard and has applications on VLSI layout.
We present a new formulation and a theoretical investigation on the corresponding polyhedra.
New families of valid inequalities, including proven facets, are identified.
We also discuss branch-and-cut implementation issues. The resulting code has a good
practical performance and can solve some instances with up to 10,000 vertices in minutes.
The second part of the thesis addresses the Steiner Problem in Graphs, which is also NP-hard.
VLSI layout applications yield Steiner instances considered hard to be solved by current methods.
In particular, preprocessing techniques developed for Steiner problems over general graphs are not likely
to reduce significantly such instances. We propose a new preprocessing procedure effective for VLSI problems.
Testing this procedure over real-world instances available on the web,
significant reductions were obtained within reasonable computational times.
Finally, we study the exact solution of the Steiner Problem in Graphs. We analyze a well-known
dual heuristic for this problem and propose three new dual heuristics to improve its performance.
These heuristics lead to two exact algorithms, a branch-and-bound without linear programming and
a branch-and-cut. The algorithms were tested over instances from the literature and obtained
good results, solving several instances for the first time.