Optimization Online


A polyhedral study of the diameter constrained minimum spanning tree problem

Luis Gouveia (legouveia***at***fc.ul.pt)
Markus Leitner (markus.leitner***at***univie.ac.at)
Ivana Ljubic (ivana.ljubic***at***univie.ac.at)

Abstract: 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.

Keywords: Integer programming, Diameter constrained trees, Facet defining inequalities

Category 1: Network Optimization

Category 2: Integer Programming (0-1 Programming )

Category 3: Combinatorial Optimization (Polyhedra )


Download: [PDF]

Entry Submitted: 06/23/2014
Entry Accepted: 07/01/2014
Entry Last Modified: 05/13/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society