Combined Column-and-Row-Generation for the Optimal Communication Spanning Tree Problem

Christian Tilk () and Stefan Irnich ()
Additional contact information
Christian Tilk: Johannes Gutenberg-Universitaet Mainz, Germany
Stefan Irnich: Johannes Gutenberg-Universitaet Mainz, Germany

No 1613, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: This paper considers the exact solution of the optimal communication spanning tree problem (OCSTP), which can be described as follows: Given an undirected graph with transportation costs on every edge and communication requirements for all pairs of vertices, the OCSTP seeks a spanning tree that minimizes the sum of the communication costs between all pairs of vertices, where the communication cost of a pair of vertices is de?ned as their communication requirement multiplied by the transportation cost of the unique tree path that connects the two vertices. Two types of compact formulations for OCSTP were presented in the literature. The ?rst one is a four-index model based on a path formulation. The second is a three-index model in which a solution is an intersection of spanning trees, each rooted at a different vertex of the graph and modeled using a ?ow formulation for spanning tree problems. We present Dantzig-Wolfe reformulations for both compact models to be used in a combined column-and-row-generation algorithm. In the path-based reformulation, the pricing problems are simple shortest-path problems, one for each pair of vertices with a positive communication requirement. The pricing problems of the tree-based reformulation are ?xed-cost network ?ow problems, one for each vertex of the graph. We apply di?erent heuristic and exact methods for pricing and present optimal solutions for benchmark instances with up to 40 vertices.

Keywords: optimal communication spanning tree; column generation; row generation; branch-and-price-and-cut (search for similar items in EconPapers)
Pages: 12 pages
Date: 2016-04-12
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1613.pdf First version, 2016 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:1613

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().