École Nationale Supérieure de
Techniques Avancées

Abstract

In this internship, we consider the Steiner tree problem. The Steiner tree problem is a very classical problem in graph theory. Given a weighted undirected graph G = (V,E), we note ce the weight of the edge e 2 E, and we consider a subset of nodes T V , that we call terminals. The Steiner tree problem consists in nding a minimum cost tree spanning T. This problem has many applications, especially in the design of telecommunications networks. In this case, the Steiner tree allows to realize at minimal cost the interconnection between N users or terminals sharing information via a multicast service. The Steiner tree problem is NP-hard in general but polynomial when T = V or |T| = 2, or also when the graph G is series-parallel. This problem has already been considerably studied. Some recent papers present mixed-integer formulations of the Steiner tree problem. In this internship, we mostly looked at a paper of Goemans and Muyng [1], which compares dierent formulations by projecting them onto the natural set of variables of the problem, that is the space R|E|, in which a variable xe is associated to each edge. Among the numerous results presented in [1], some show that several formulations are projected onto the same polyhedron Qx in the space R|E|. But there are only a few results concerning the other formulations presented in [1]. In this report, we look at some results of [1], and we also present other formulations and other polyhedrons of R|E|. We also test numerically the dierent formulations, and we compare them on several exemples of the Steinlib.