New models of the generalized minimum spanning tree problem
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)].
- A new relaxation method for the generalized minimum spanning tree problem
- On the generalized minimum spanning tree problem
- scientific article; zbMATH DE number 1788251
- A note on the complexity of the generalized minimum spanning tree problem
- On some polynomial solvable cases of the generalized minimum spanning tree problem
- Generalized spanning trees
- Generalized Steiner problems and other variants
- A multigraph formulation for the generalized minimum spanning tree problem
- A two-level solution approach for solving the generalized minimum spanning tree problem
- Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
- The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances
- A polyhedral approach to the generalized minimum labeling spanning tree problem
- The prize-collecting generalized minimum spanning tree problem
- On the prize-collecting generalized minimum spanning tree problem
- A new relaxation method for the generalized minimum spanning tree problem
- The generalized minimum spanning tree: polyhedra and branch-and-cut
- A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs
- Relaxation methods for the Generalized Minimum Spanning Tree problem
- Integer programming models and branch-and-cut approaches to generalized \(\{0,1,2\}\)-survivable network design problems
- Improving on branch-and-cut algorithms for generalized minimum spanning trees
- Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
- On some polynomial solvable cases of the generalized minimum spanning tree problem
- Approximation algorithms for generalized MST and TSP in grid clusters
- Solving the generalized minimum spanning tree problem with simulated annealing
- Distributed data possession checking for securing multiple replicas in geographically-dispersed clouds
- The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm
- Generalized network design problems. Modeling and optimization.
- scientific article; zbMATH DE number 1788251 (Why is no real title available?)
- On the generalized minimum spanning tree problem
- Selective generalized travelling salesman problem
- Network optimization on partitioned pairs of points
- A Lagrangian relaxation approach to the generalized minimum spanning tree problem
- A note on the complexity of the generalized minimum spanning tree problem
- An approximation algorithm for the least version of the generalized minimum spanning tree problem
- At least version of the generalized minimum spanning tree problem
- On generalized minimum spanning trees
- A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem
- An efficient mixed integer linear programming model for the minimum spanning tree problem
- Upper and lower bounding strategies for the generalized minimum spanning tree problem
- The geometric generalized minimum spanning tree problem with grid clustering
- Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem
This page was built for publication: New models of the generalized minimum spanning tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q702364)
