Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem

Fortz, Bernard; Oliveira, O.; Requejo, C.

doi:10.1016/j.ejor.2016.06.014

Download

Article (Scientific journals)

Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem

Fortz, Bernard; Oliveira, O.; Requejo, C.

2017 • In European Journal of Operational Research, 256 (1), p. 242-251

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/318183

DOI
10.1016/j.ejor.2016.06.014

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

tree_discovery_revision2-2016-06.pdf

Author postprint (468.77 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Mixed integer linear programming; Tree realization; Topology discovery; Routing topology inference; Minimum evolution problem

Abstract :

[en] 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.

Disciplines :

Quantitative methods in economics & management

Author, co-author :

Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt

Oliveira, O.

Requejo, C.

Language :

English

Title :

Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem

Publication date :

2017

Journal title :

European Journal of Operational Research

ISSN :

0377-2217

eISSN :

1872-6860

Volume :

256

Issue :

Pages :

242-251

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.scopus.com/inward/record.uri?eid=2-s2.0-84990232272&doi=10.1016%2fj.ejor.2016.06.014&partnerID=40&md5=0982bfbc0d82f064bb5563dadec62709

Available on ORBi :

since 15 May 2024

Statistics

Number of views

4 (1 by ULiège)

Number of downloads

4 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Abdi, H., Additive-tree representations. Dress, A., von Haeseler, A., (eds.) Trees and Hierarchical Structures Lecture Notes in Biomathematics, 84, 1990, Springer Berlin Heidelberg, 43–59.
Bhamidi, S., Rajagopal, R., Roch, S., Network delay inference from additive metrics. Random Structures Algorithms 37:2 (2010), 176–203.
Buneman, P., A note on the metric properties of trees. Journal of Combinatorial Theory 17 (1974), 48–50.
Byun, S.-S., Yoo, C., Reducing delivery delay in HRM tree. Gavrilova, M., Gervasi, O., Kumar, V., Tan, C., Taniar, D., Laganà, A., Mun, Y., Choo, H., (eds.) Computational Science and Its Applications - ICCSA 2006 Lecture Notes in Computer Science, 3981, 2006, Springer Berlin Heidelberg, 1189–1198.
Catanzaro, D., The minimum evolution problem: overview and classification. Networks 53:2 (2009), 112–125.
Catanzaro, D., Aringhieri, R., Summa, M.D., Pesenti, R., A branch-price-and-cut algorithm for the minimum evolution problem. European Journal of Operational Research 244:3 (2015), 753–765.
Catanzaro, D., Labbé, M., Pesenti, R., Salazar-Gonzaléz, J.-J., Mathematical models to reconstruct phylogenetic trees under the minimum evolution criterion. Networks 53:2 (2009), 126–140.
Catanzaro, D., Labbé, M., Pesenti, R., Salazar-Gonzaléz, J.-J., The balanced minimum evolution problem. INFORMS Journal on Computing 24:2 (2012), 276–294.
Cavalli-Sforza, L., Edwards, A., Phylogenetic analysis. Models and estimation procedures. American Journal of Human Genetics 19 (1967), 233–257.
Chung, F., Garrett, M., Graham, R., Shallcross, D., Distance realization problems with applications to internet tomography. Journal of Computer and System Sciences 63:3 (2001), 432–448.
Coates, M., Castro, R., Nowak, R., Gadhiok, M., King, R., Tsang, Y., Maximum likelihood network topology identification from edge-based unicast measurements. ACM SIGMETRICS performance evaluation review, 30, 2002, 11–20.
Coates, M., Rabbat, M., Nowak, R., Merging logical topologies using end-to-end measurements. Proceedings of the 3rd ACM SIGCOMM conference on internet measurement, IMC ’03, 2003, 192–203.
Corter, J.E., Tversky, A., Extended similarity trees. Psychometrika 51:3 (1986), 429–451.
Cunningham, J.P., Trees as memory representations for simple visual patterns. Memory & Cognition 8:6 (1980), 593–605.
Day, W.H., Computational complexity of inferring phylogenies from dissimilarity matrices. Bulletin of Mathematical Biology 49:4 (1987), 461–467.
Dias, Z., Rocha, A., Goldenstein, S., Image phylogeny by minimal spanning trees. IEEE Transactions on Information Forensics and Security 7:2 (2012), 774–788.
Donnet, B., Internet topology discovery. Data Traffic Monitoring and Analysis: From Measurement, Classification, and Anomaly Detection to Quality of Experience Lecture Notes in Computer Science, 7754, 2013, Springer, 44–81.
Donnet, B., Friedman, T., Internet topology discovery: a survey. IEEE Communications Surveys 9:4 (2007), 2–14.
Donnet, B., Raoult, P., Friedman, T., Crovella, M., Deployment of an algorithm for large-scale topology discovery. IEEE Journal on Selected Areas in Communications 24:12 (2006), 2210–2220.
Dress, A., Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces. Advances in Mathematics 53 (1984), 321–402.
Duffield, N., Horowitz, J., Presti, F.L., Towsley, D., Multicast topology inference from measured end-to-end loss. IEEE Transactions on Information Theory 48:1 (2002), 26–45.
Duffield, N., Horowitz, J., Prestis, F.L., Adaptive multicast topology inference. INFOCOM 2001. twentieth annual joint conference of the IEEE computer and communications societies. proceedings IEEE., volume 3, 2001, 1636–1645.
Edelberg, M., Garey, M., Graham, R., On the distance matrix of a tree. Discrete Mathematics 14 (1976), 23–39.
Eriksson, B., Dasarathy, G., Barford, P., Nowak, R., Toward the practical use of network tomography for internet topology discovery. Proceedings of the INFOCOM 2010, the IEEE conference on computer communications, 2010, 1–9.
Farach, M., Kannan, S., Warnow, T., A robust model for finding optimal evolutionary trees. Algorithmica 13:1 (1995), 155–179.
Felsenstein, J., Distance matrix methods. Inferring Phylogenies, chapter 11, 2004, Sinauer Associates, Inc, Sunderland, Massachusetts, 147–175.
Fiorini, S., Joret, G., Approximating the balanced minimum evolution problem. Operations Research Letters 40:1 (2012), 31–35.
Gaschen, B., Taylor, J., Yusim, K., Foley, B., Gao, F., Lang, D., et al. Diversity considerations in HIV-1 vaccine selection. Science 296:5577 (2002), 2354–2360.
Gilmore, G., Hersh, H., Caramazza, A., Griffin, J., Multidimensional letter similarity derived from recognition errors. Perception & Psychophysics 25:5 (1979), 425–431.
Gouveia, L., Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop constraints. Computers and Operations Research 22:9 (1995), 959–970.
Gouveia, L., Multicommodity flow models for spanning trees with hop constraints. European Journal of Operational Research 95 (1996), 178–190.
Govindan, R., Tangmunarunkit, H., Heuristic for internet map discovery. Proceeding of the 19th annual joint conference of IEEE computer and communications societies, volume 3, 2000, 1371–1380.
Haddadi, H., Rio, M., Iannaccone, G., Moore, A., Mortier, R., Network topologies: inference, modelling and generation. IEEE Communications Surveys 10:2 (2008), 48–69.
Hakimi, S.L., Patrinos, A., The distance matrix of a graph and its tree realization. Quarterly of Applied Mathematics 30 (1972), 255–269 73.
Hakimi, S.L., Yau, S.S., Distance matrix of a graph and its realizability. Quarterly of Applied Mathematics 22 (1965), 305–317.
Huson, D., Scornavacca, C., A survey of combinatorial methods for phylogenetic networks. Genome Biology and Evolution 3 (2011), 23–35.
Isaev, A., Introduction to Mathematical Methods in Bioinformatics, 2006, Springer.
Junker, B.H., Schreiber, F., Analysis of Biological Networks, 2008, John Wiley & Sons.
Koolen, A.L.J., Moulton, V., Optimal realizations of generic five-point metric. European Journal of Combinatorics 30 (2009), 1164–1171.
Magnanti, T.L., Wolsey, L.A., Optimal trees. Ball, M., Magnanti, T.L., Monma, C., Nemhauser, G.L., (eds.) Network Models, Handbooks in Operations Research and Management Science, Vol. 7, 1995, Elsevier Science Publishers, North-Holland, 503–615.
Miller, C., Tucker, A., Zemlin, R., Integer programming formulations and travelling salesman problems. Journal of the Association for Computing Machinery 7:4 (1960), 326–329.
Mount, D., Bioinformatics. Sequence and genome analysis, 2001, Cold Spring Harbor Laboratory Press.
Nei, M., Kumar, S., Molecular evolution and phylogenetics, 2000, Oxford University Press.
Ni, J., Tatikonda, S., Network tomography based on additive metrics. IEEE Transactions on Information Theory 57:12 (2011), 7798–7809.
Ni, J., Xie, H., Tatikonda, S., Yang, Y.R., Network routing topology inference from end-to-end measurements. INFOCOM 2008, the 27th IEEE conference on computer communications, 2008.
Network Simulator NS-3. www.nsnam.org.
Parker, D., Ram, P., The construction of Huffman codes is a submodular (“convex”) optimization problem over a lattice of binary trees. SIAM Journal on Computing 28:5 (1996), 1875–1905.
Pauplin, Y., Direct calculation of a tree length using a distance matrix. Journal of Molecular Evolution 51 (2000), 41–47.
Sattath, S., Tversky, A., Additive similarity trees. Psichometrica 42:3 (1977), 319–345.
Shih, M.-F., Hero, A., Hierarchical inference of unicast network topologies based on end-to-end measurements. IEEE Transactions on Signal Processing 55:5 (2007), 1708–1718.
Simões-Pereira, J., A note on distance matrices with unicyclic graph realizations. Discrete Mathematics 65 (1987), 277–287.
Simões-Pereira, J., An algorithm and its role in the study of optimal graph realizations of distance matrices. Discrete Mathematics 79 (1990), 299–312.
Simões-Pereira, J., Zamfirescu, C., Submatrices of non-tree-realizable distance matrices. Linear Algebra and its Applications 44 (1982), 1–17.
Soete, G.D., A least squares algorithm for fitting additive trees to proximity data. Psychometrika 48:4 (1983), 621–626.
FICO Xpress Optimization Suite. www.fico.com/xpress.
Varone, S.C., Trees related to realizations of distance matrices. Discrete Mathematics 192 (1998), 337–346.
Varone, S.C., A constructive algorithm for realizing a distance matrix. European Journal of Operational Research 174:1 (2006), 102–111.