  In this work, we compute the lower bound of the integrality gap of the Metric
Steiner Tree Problem (MSTP) on a graph for some small values of number of nodes
and terminals. After debating about some limitations of the most used
formulation for the Steiner Tree Problem, namely the Bidirected Cut
Formulation, we introduce a novel formulation, that we named Complete Metric
formulation, tailored for the metric case. We prove some interesting properties
of this formulation and characterize some types of vertices. Finally, we define
a linear program (LP) by adapting a method already used in the context of the
Travelling Salesman Problem. This LP takes as input a vertex of the polytope of
the CM relaxation and provides an MSTP instance such that (a) the optimal
solution is precisely that vertex and (b) among all of the instances having
that vertex as its optimal solution, the selected instance is the one having
the highest integrality gap. We propose two heuristics for generating vertices
to provide inputs for our procedure. In conclusion, we raise several
conjectures and open questions.
