MIP model-based heuristics for the minimum weighted tree reconstruction problem
- PDF / 1,814,102 Bytes
- 38 Pages / 439.37 x 666.142 pts Page_size
- 61 Downloads / 171 Views
MIP model‑based heuristics for the minimum weighted tree reconstruction problem Olga Fajarda1 · Cristina Requejo2 Received: 16 November 2019 / Revised: 1 August 2020 / Accepted: 14 September 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We consider the minimum weighted tree reconstruction (MWTR) problem and two matheuristic methods to obtain optimal or near-optimal solutions: the Feasibility Pump heuristic and the Local Branching heuristic. These matheuristics are based on a Mixed Integer Programming model used to find feasible solutions. We discuss the applicability and effectiveness of the matheuristics to obtain solutions to the MWTR problem. The purpose of the MWTR problem is to find a minimum weighted tree connecting a set of leaves in such a way that the length of the path between each pair of leaves is greater than or equal to a given distance between the considered pair of leaves. The Feasibility Pump matheuristic starts with the Linear Programming solution, iteratively fixes the values of some variables and solves the corresponding problem until a feasible solution is achieved. The Local Branching matheuristic, in its turn, improves a feasible solution by using a local search. Computational results using two different sets of instances, one from the phylogenetic area and another from the telecommunications area, show that these matheuristics are quite effective in finding feasible solutions and present small gap values. Each matheuristic can be used independently; however, the best results are obtained when used together. For instances of the problem having up to 17 leaves, the feasible solution obtained by the Feasibility Pump heuristic is improved by the Local Branching heuristic. Noticeably, when comparing with existing based models processes that solve instances having up to 15 leaves, this achievement of the matheuristic increases the size of solved instances. Keywords Feasibility pump · Local branching · Mixed integer linear programming · Matheuristics · Tree realization · Topology discovery · Routing topology inference · Minimum evolution problem · Balanced minimum evolution problem
* Cristina Requejo [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
O. Fajarda, C. Requejo
1 Introduction The Minimum Weighted Tree Reconstruction (MWTR) Problem is a combinatorial optimization problem that consists in reconstructing a weighted tree T = (V, E) . The tree reconstruction is obtained by knowing only the pairwise distances dij between all nodes i, j from a set Vt , subset of the set of[ nodes ] V of a graph. More precisely, given a n × n symmetric distance matrix D = dij and a set Vt of n leaves, terminal nodes, the goal of the problem is to simultaneously (i) find an unrooted tree T = (V, E) spanning V = Vt ∪ Va , where Va is a subset of V with additional nodes which are internal nodes, and which wlog we can assume to be of degree three, and Vt ∩ Va = � , (ii) associate edge weights we , e ∈ E , such that the le
Data Loading...
