A polyhedral study of the diameter constrained minimum spanning tree problem

Abstract:

 

The diameter constrained minimum spanning tree problem (DMSTP) is defined as follows: Given an edge-weighted graph G, and a diameter limit D, the goal is to identify a minimum cost spanning tree of G whose diameter does not exceed D. The question on how to provide a strong formulation for the DMSTP in the natural space of edge variables (using only one variable associated to each edge) remained open for some time and up to now, only extended formulations for the DMSTP are considered in the literature. Despite providing very tight linear programming (LP) bounds, these formulations involve a large number of variables and are therefore not (directly) suitable to be used for solving the DMSTP on very large graphs.

 

For some time it was not known how to describe inequalities that guarantee the length of the paths using only edge variables. The work by Dahl (1999) has made a significant contribution in this area by proposing the so-called jump constraints to model constrained shortest paths. Jump constraints have been later on also considered in the context of the hop-constrained trees and they can even be adapted in a straightforward way to model the DMSTP. However, this leads to a rather weak integer programming (ILP) model for the DMSTP.

 

In this talk 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.

 

This is a joint work with Luis Gouveia and Markus Leitner.

Date: Mar 06, 2015 at 16:15 h
Venue: Beauchef 851, Sala de Seminarios John Von Neumann CMM, Séptimo Piso.
Speaker: Ivana Ljubic
Affiliation: University of Vienna
Coordinator: Marcos Kiwi
Abstract:
PDF

Posted on Mar 4, 2015 in Discrete Mathematics, Seminars