Common-Flow Formulations for the Diameter Constrained Spanning and Steiner Tree Problems

We consider the diameter constrained minimum Steiner tree problem on a graph (DCStTP). Given an edge-weighted undirected graph whose set of nodes is partitioned into a set of terminal and potential Steiner nodes, the objective is to find a minimum-weight subtree that spans all terminal nodes such that the number of hops between any two terminal nodes does not exceed a given diameter D. In this work, we introduce mixed-integer linear programming models for the DCStTP based on the concept of triangles, i.e. diameter constrained Steiner trees induced by terminal subsets of size three. Starting from a formulation that models a D-hop Steiner arborescence rooted at a randomly chosen terminal node, we discuss various possibilities of realizing triangles using multi-commodity, common, or uncommon flows. We analyse the strength of these models both theoretically and empirically, and investigate how their respective Benders reformulations influence the computational performance.