Title :

Compact Mixed Integer Linear Programming models to the Minimum Weighted Tree Reconstruction Problem

Author(s) :

Fortz, Bernard [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Graphes et Optimisation Mathématique [Bruxelles] [GOM]
Oliveira, Olga [Auteur]
Departamento de Matematica [Aveiro]
Requejo, Cristina [Auteur]
Departamento de Matematica [Aveiro]

Journal title :

European Journal of Operational Research

Pages :

242 - 251

Publisher :

Elsevier

Publication date :

2017

ISSN :

0377-2217

HAL domain(s) :

Computer Science [cs]/Operations Research [math.OC]

English abstract : [en]

The Minimum Weighted Tree Reconstruction (MWTR) problem consists of finding a min imum 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 ...
Show more >The Minimum Weighted Tree Reconstruction (MWTR) problem consists of finding a min imum 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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL