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

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.