The Two-Level Diameter Constrained Spanning Tree Problem

In this article, we introduce the two-level diameter constrained spanning tree problem (2-DMSTP), which generalizes the classical DMSTP by considering two sets of nodes with different latency requirements. We first observe that any feasible solution to the 2-DMSTP can be viewed as a DMST that contains a diameter constrained Steiner tree. This observation allows us to prove graph theoretical properties related to the centers of each tree which are then exploited to develop mixed integer programming formulations, valid inequalities, and symmetry breaking constraints. In particular, we propose a novel modeling approach based on a three-dimensional layered graph. In an extensive computational study we show that a branch-and-cut algorithm based on the latter model is highly effective in practice. Link to the article

GOUVEIA, L., LEITNER, M. and LJUBIC, I. (2015). The Two-Level Diameter Constrained Spanning Tree Problem. Mathematical Programming, 150(1), pp. 49-78.