The consideration of quality-of-service constraints in the design of telecommunication or logistics networks give rise to a rich family of optimization problems. Among other (practically relevant) aspects, a significant body of literature has been devoted to models considering network availability or reliability, as well as transmission delay or signal quality. Previous studies have shown that the latter aspects can often be appropriately addressed by hop-, diameter-, or distance constraints. Resulting models are known to often provide a good trade-off between too simplistic problem variants (that are relatively easy to solve) and those considering all real-world aspects in a very detailed way (that often can only be addressed by simple heuristics). In this work, we consider the diameter constrained spanning tree problem (DMSTP) which is one of the most fundamental problems in this domain. Besides various heuristics, a large number of exact algorithms for the DMSTP that are based on different extended integer linear programming formulations have been proposed in the scientific literature. Despite providing very tight linear programming bounds, these formulations involve a large number or variables and are therefore not (directly) suitable for solving the DMSTP on very large graphs. In this work we provide a first study of formulations for the DMSTP in the natural space of undirected edge design variables. A new family of circular-jump inequalities is introduced and these inequalities are further generalized in two ways. Most of the proposed new inequalities are shown to define facets of the DMSTP polyhedron under very mild conditions. We also prove that most of these new families of inequalities are not implied by any of the extended formulations known from the literature and discuss some observations from computational experiments.
Homepage of Markus Leitner