This paper provides a study of integer linear programming formulations for the diameter constrained spanning tree problem (DMSTP) in the natural space of edge design variables. After presenting a straightforward model based on the well known jump inequalities a new stronger family of circular-jump inequalities is introduced. These inequalities are further generalized in two ways: either by increasing the number of partitions defining a jump, or by combining jumps with cutsets. Most of the proposed new inequalities are shown to define facets of the DMSTP polyhedron under very mild conditions. Currently best known lower bounds for the DMSTP are obtained from an extended formulation on a layered graph using the concept of central nodes/edges. The new families of inequalities are shown not to be implied by this layered graph formulation.
Article
View A polyhedral study of the diameter constrained minimum spanning tree problem