New models of the generalized minimum spanning tree problem (Q702364)

Given an undirected graph \(G= (V,E)\), whose nodes are partitioned into \(m\) clusters \(V_1,\dots, V_m\), and whose edges (only defined between nodes from different clusters) are assigned nonnegative costs, the Generalized Minimum Spanning Tree Problem (GMST) is to determine a tree of minimum total cost containing exactly one node from each cluster. First, it is shown in this paper that, already on trees, GMST is NP-hard. The second result is a dynamic programming based algorithm for the exact solution of GMST, whose complexity is \(O(m^{m-2}n^2)\). Several (mixed) integer programming formulations are presented in section 4: those involving an exponential number of constraints and those with a polynomial such number (but an additional number of variables). Relationships between the polytopes associated with their linear relaxations are established. The final (and new) model can be formulated as follows: \[ \text{minimize } c_ex_e\text{ subject to }y\in P_{\text{MST}},\, (x,z)\in P_{\text{local}}(Y)\text{ and }y_{lr}\in\{0,1\},\, 1\leq l,\,r\leq m,\tag{P} \] \(P_{\text{MST}}\) representing the spanning tree polytope and \(P_{\text{local}}(y)\) the linear relaxation of a particular 0-1 programming problem. In section 5 a special relaxation of (P) is used to solve problem instances with up to 240 nodes to optimality. These numerical results are finally shown to compare favorably with those obtained by Branch and Cut [\textit{C. Feremans}, Generalized spanning trees and extensions, Ph.D. thesis, Universite Libre de Bruxelles, Belgium] and those reported in [\textit{Y. S. Myung, C. H. Lee}, and \textit{D.-W. Tcha}, Networks 26, 231--241 (1995; Zbl 0856.90117)].