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 -