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
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
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.
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.
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.
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.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
