In this work, we study the metric Steiner Tree problem on graphs focusing on computing lower bounds for the integrality gap of the bi-directed cut (DCUT) formulation and introducing a novel formulation, the Complete Metric (CM) model, specifically designed to address the weakness of the DCUT formulation on metric instances. A key contribution of our work is extending of the Gap problem, previously explored in the context of the Traveling Salesman problems, to the metric Steiner Tree problem. To tackle the Gap problem for Steiner Tree instances, we first establish several structural properties of the CM formulation. We then classify the isomorphism classes of the vertices within the CM polytope, revealing a correspondence between the vertices of the DCUT and CM polytopes. Computationally, we exploit these structural properties to design two complementary heuristics for finding nontrivial small metric Steiner instances with a large integrality gap. We present several vertices for graphs with a number of nodes <=10, which realize the best-known lower bounds on the integrality gap for the CM and the DCUT formulations. We conclude the paper by presenting three new conjectures on the integrality gap of the DCUT and CM formulations for small graphs.
Article
View On the integrality gap of the Complete Metric Steiner Tree Problem via a novel formulation