Repositório Institucional da Universidade de Aveiro > CIDMA - Centro de Investigação e Desenvolvimento em Matemática e Aplicações > CIDMA - Artigos >
 Compact mixed integer linear programming models to the Minimum Weighted Tree Reconstruction problem
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/17238

title: Compact mixed integer linear programming models to the Minimum Weighted Tree Reconstruction problem
authors: Fortz, Bernard
Requejo, Cristina
Oliveira, Olga
keywords: Mixed integer linear programming
Distance matrix
Tree realization
Topology discovery
Routing topology inference
Balanced minimum evolution problem
Minimum evolution problem
issue date: Jan-2017
publisher: Elsevier
abstract: The Minimum Weighted Tree Reconstruction (MWTR) problem consists of finding a minimum length weighted tree connecting a set of terminal nodes in such a way that the length of the path between each pair of terminal nodes is greater than or equal to a given distance between the considered pair of terminal nodes. This problem has applications in several areas, namely, the inference of phylogenetic trees, the modeling of traffic networks and the analysis of internet infrastructures. In this paper, we investigate the MWTR problem and we present two compact mixed-integer linear programming models to solve the problem. Computational results using two different sets of instances, one from the phylogenetic area and another from the telecommunications area, show that the best of the two models is able to solve instances of the problem having up to 15 terminal nodes.
URI: http://hdl.handle.net/10773/17238
ISSN: 0377-2217
publisher version/DOI: http://dx.doi.org/10.1016/j.ejor.2016.06.014
source: European Journal of Operational Research
appears in collectionsCIDMA - Artigos

files in this item

file description sizeformat
tree_discovery_authors_pprint.pdfdocumento510.8 kBAdobe PDFview/open
Restrict Access. You can Request a copy!

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2