A polyhedral approach to the generalized minimum labeling spanning tree problem

Abstract

The minimum labeling spanning tree problem (MLSTP) is a combinatorial optimization problem that consists in finding a spanning tree in a simple graph G, in which each edge has one label, by using a minimum number of labels. It is an NP-hard problem that was introduced by Chang and Leu (Inf Process Lett 63(5):277–282, 1997. https://doi.org/10.1016/S0020-0190(97)00127-0). Chen et al. (Comparison of heuristics for solving the gmlst problem, in: Raghavan, Golden, Wasil (eds) Telecommunications modeling, policy, and technology, Springer, Boston, pp 191–217, 2008) subsequently proposed a generalization of the MLSTP, called the generalized minimum labeling spanning tree problem (GMLSTP), that allows a situation in which multiple labels can be assigned to an edge. Here, we show how the GMLSTP can be expressed as an MLSTP in a multigraph. Both problems have applications in various areas such as computer network design, multimodal transportation network design, and data compression. We propose a new compact binary integer programming model to solve exactly the GMLSTP and analyze the polytope associated with the formulation. The paper introduces new concepts, gives the polytope dimension, and describes five new facet families. The polyhedral comparison results for the studied polytope show that the new model is theoretically superior to current state-of-the-art formulations.

Keywords

• 90C27
• 90C10