TY - JOUR
T1 - A polyhedral study of the diameter constrained minimum spanning tree problem
AU - Gouveia, Luis
AU - Leitner, Markus
AU - Ljubić, Ivana
PY - 2020/10/15
Y1 - 2020/10/15
N2 - This paper provides a first polyhedral study of the diameter constrained minimum spanning tree problem (DMSTP). We introduce a new set of inequalities, the circular-jump inequalities which strengthen the well-known jump inequalities. 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 polytope 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. A subset of the new families of inequalities is shown to be not implied by this layered graph formulation.
AB - This paper provides a first polyhedral study of the diameter constrained minimum spanning tree problem (DMSTP). We introduce a new set of inequalities, the circular-jump inequalities which strengthen the well-known jump inequalities. 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 polytope 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. A subset of the new families of inequalities is shown to be not implied by this layered graph formulation.
KW - Diameter constrained trees
KW - Facet
KW - Integer programming
UR - http://www.scopus.com/inward/record.url?scp=85086628470&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85086628470&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2020.05.020
DO - 10.1016/j.dam.2020.05.020
M3 - Article
AN - SCOPUS:85086628470
VL - 285
SP - 364
EP - 379
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
ER -