A polyhedral approach to the generalized minimum labeling spanning tree problem

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 L...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	ThiagoGouveiada Silva, Serigne Gueye, Philippe Michelon, LuizSatoru Ochi, LucídiodosAnjosFormiga Cabral
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2019
Materias:	90C27 90C10 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/05898c0ad5c440f29cd7df04ac0054f2
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:05898c0ad5c440f29cd7df04ac0054f2
record_format	dspace
spelling	oai:doaj.org-article:05898c0ad5c440f29cd7df04ac0054f22021-12-02T05:01:10ZA polyhedral approach to the generalized minimum labeling spanning tree problem2192-440610.1007/s13675-018-0099-5https://doaj.org/article/05898c0ad5c440f29cd7df04ac0054f22019-03-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001118https://doaj.org/toc/2192-4406The 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.ThiagoGouveiada SilvaSerigne GueyePhilippe MichelonLuizSatoru OchiLucídiodosAnjosFormiga CabralElsevierarticle90C2790C10Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 7, Iss 1, Pp 47-77 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C27 90C10 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C27 90C10 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 ThiagoGouveiada Silva Serigne Gueye Philippe Michelon LuizSatoru Ochi LucídiodosAnjosFormiga Cabral A polyhedral approach to the generalized minimum labeling spanning tree problem
description	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.
format	article
author	ThiagoGouveiada Silva Serigne Gueye Philippe Michelon LuizSatoru Ochi LucídiodosAnjosFormiga Cabral
author_facet	ThiagoGouveiada Silva Serigne Gueye Philippe Michelon LuizSatoru Ochi LucídiodosAnjosFormiga Cabral
author_sort	ThiagoGouveiada Silva
title	A polyhedral approach to the generalized minimum labeling spanning tree problem
title_short	A polyhedral approach to the generalized minimum labeling spanning tree problem
title_full	A polyhedral approach to the generalized minimum labeling spanning tree problem
title_fullStr	A polyhedral approach to the generalized minimum labeling spanning tree problem
title_full_unstemmed	A polyhedral approach to the generalized minimum labeling spanning tree problem
title_sort	polyhedral approach to the generalized minimum labeling spanning tree problem
publisher	Elsevier
publishDate	2019
url	https://doaj.org/article/05898c0ad5c440f29cd7df04ac0054f2
work_keys_str_mv	AT thiagogouveiadasilva apolyhedralapproachtothegeneralizedminimumlabelingspanningtreeproblem AT serignegueye apolyhedralapproachtothegeneralizedminimumlabelingspanningtreeproblem AT philippemichelon apolyhedralapproachtothegeneralizedminimumlabelingspanningtreeproblem AT luizsatoruochi apolyhedralapproachtothegeneralizedminimumlabelingspanningtreeproblem AT lucidiodosanjosformigacabral apolyhedralapproachtothegeneralizedminimumlabelingspanningtreeproblem AT thiagogouveiadasilva polyhedralapproachtothegeneralizedminimumlabelingspanningtreeproblem AT serignegueye polyhedralapproachtothegeneralizedminimumlabelingspanningtreeproblem AT philippemichelon polyhedralapproachtothegeneralizedminimumlabelingspanningtreeproblem AT luizsatoruochi polyhedralapproachtothegeneralizedminimumlabelingspanningtreeproblem AT lucidiodosanjosformigacabral polyhedralapproachtothegeneralizedminimumlabelingspanningtreeproblem
_version_	1718400810356834304

A polyhedral approach to the generalized minimum labeling spanning tree problem

Ejemplares similares