A Multigraph Formulation for the Generalized Minimum Spanning Tree Problem

Ernando Gomes de Sousa (1) , Rafael Castro de Andrade (2) , Andréa Cynthia Santos (3)

1 UERN - Universidade do Estado do Rio Grande do Norte
2 UFC - Universidade Federal do Ceará = Federal University of Ceará
3 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

Given a connected, undirected and m-partite complete graph G=(V1∪V2∪...∪Vm;E), the Generalized Minimum Spanning Tree Problem (GMSTP) consists in finding a tree with exactly m−1 edges, connecting the m clusters V1,V2,...,Vm through the selection of a unique vertex in each cluster. GMSTP finds applications in network design, irrigation agriculture, smart cities, data science, among others. This paper presents a new multigraph mathematical formulation for GMSTP which is compared to existing formulations from the literature. The proposed model proves optimality for well-known GMSTP instances. In addition, this work opens new directions for future research to the development of sophisticated cutting plane and decomposition algorithms for related problems.

Keywords: Generalized Minimum Spanning Tree; Trees of multigraph; Mixed integer linear programming formulations

Domains: Operations Research [cs.RO]

Ernando Gomes de Sousa, Rafael Castro de Andrade, Andréa Cynthia Santos. A Multigraph Formulation for the Generalized Minimum Spanning Tree Problem. ISCO 2018: Combinatorial Optimization, 10856, Springer, pp.133-143, 2018, Lecture Notes in Computer Science, ⟨10.1007/978-3-319-96151-4_12⟩. ⟨hal-02291657⟩