A polyhedral study of the diameter constrained minimum spanning tree problem

Luis Gouveia; Markus Leitner; Ivana Ljubić

doi:10.1016/j.dam.2020.05.020

A polyhedral study of the diameter constrained minimum spanning tree problem

Luis Gouveia
, Markus Leitner^*
, Ivana Ljubić

^*Corresponding author for this work

Operations Analytics

Research output: Contribution to Journal › Article › Academic › peer-review

315 Downloads (Pure)

Abstract

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.

Original language	English
Pages (from-to)	364-379
Number of pages	16
Journal	Discrete Applied Mathematics
Volume	285
Early online date	20 Jun 2020
DOIs	https://doi.org/10.1016/j.dam.2020.05.020
Publication status	Published - 15 Oct 2020

Funding

Luis Gouveia is supported by National Funding from FCT — Fundação para a Ciência e Tecnologia, Portugal , under the project: PEst-OE/MAT/UI0152. Markus Leitner is supported by the Austrian Science Fund (FWF) under grant I892-N23 . These supports are greatly acknowledged. Luis Gouveia is supported by National Funding from FCT ? Funda??o para a Ci?ncia e Tecnologia, Portugal, under the project: PEst-OE/MAT/UI0152. Markus Leitner is supported by the Austrian Science Fund (FWF) under grant I892-N23. These supports are greatly acknowledged. The authors also thank the anonymous reviewers for their numerous constructive and helpful comments. Incorporating their feedback has helped them to significantly improve the quality and presentation of the final article.

Funders	Funder number
Ci?ncia e Tecnologia
Fundação para a Ciência e Tecnologia	PEst-OE/MAT/UI0152
Fundação para a Ciência e a Tecnologia
Austrian Science Fund	I892-N23

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 10 Reduced Inequalities

Keywords

Diameter constrained trees
Facet
Integer programming

Access to Document

10.1016/j.dam.2020.05.020

A polyhedral study of the diameter constrained minimum spanning tree problemFinal published version, 468 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

@article{0fd99c6ee54048bdaf1a80e0d16c2087,

title = "A polyhedral study of the diameter constrained minimum spanning tree problem",

abstract = "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.",

keywords = "Diameter constrained trees, Facet, Integer programming",

author = "Luis Gouveia and Markus Leitner and Ivana Ljubi{\'c}",

year = "2020",

month = oct,

day = "15",

doi = "10.1016/j.dam.2020.05.020",

language = "English",

volume = "285",

pages = "364--379",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

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 - https://www.scopus.com/pages/publications/85086628470

UR - https://www.scopus.com/pages/publications/85086628470#tab=citedBy

U2 - 10.1016/j.dam.2020.05.020

DO - 10.1016/j.dam.2020.05.020

M3 - Article

AN - SCOPUS:85086628470

SN - 0166-218X

VL - 285

SP - 364

EP - 379

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

A polyhedral study of the diameter constrained minimum spanning tree problem

Abstract

Funding

UN SDGs

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this