Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem. (English) Zbl 1394.90435
Summary: 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.
MSC:
| 90C11 | Mixed integer programming |
| 90C35 | Programming involving graphs or networks |
| 05C05 | Trees |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 90B10 | Deterministic network models in operations research |
Keywords:
mixed integer linear programming; tree realization; topology discovery; routing topology inference; minimum evolution problemReferences:
| [1] | Abdi, H., Additive-tree representations, (Dress, A.; von Haeseler, A., Trees and Hierarchical Structures. Trees and Hierarchical Structures, Lecture Notes in Biomathematics, 84 (1990), Springer Berlin Heidelberg), 43-59 · Zbl 0698.92002 |
| [2] | Bhamidi, S.; Rajagopal, R.; Roch, S., Network delay inference from additive metrics, Random Structures Algorithms, 37, 2, 176-203 (2010) · Zbl 1201.90048 |
| [3] | Buneman, P., A note on the metric properties of trees, Journal of Combinatorial Theory, 17, 48-50 (1974) · Zbl 0286.05102 |
| [4] | 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., Computational Science and Its Applications - ICCSA 2006. Computational Science and Its Applications - ICCSA 2006, Lecture Notes in Computer Science, 3981 (2006), Springer Berlin Heidelberg), 1189-1198 · Zbl 1170.68335 |
| [5] | Catanzaro, D., The minimum evolution problem: overview and classification, Networks, 53, 2, 112-125 (2009) · Zbl 1168.92036 |
| [6] | 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, 753-765 (2015) · Zbl 1346.90210 |
| [7] | 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, 126-140 (2009) · Zbl 1168.92037 |
| [8] | Catanzaro, D.; Labbé, M.; Pesenti, R.; Salazar-Gonzaléz, J.-J., The balanced minimum evolution problem, INFORMS Journal on Computing, 24, 2, 276-294 (2012) · Zbl 1461.92066 |
| [9] | Cavalli-Sforza, L.; Edwards, A., Phylogenetic analysis. Models and estimation procedures, American Journal of Human Genetics, 19, 233-257 (1967) |
| [10] | Chung, F.; Garrett, M.; Graham, R.; Shallcross, D., Distance realization problems with applications to internet tomography, Journal of Computer and System Sciences, 63, 3, 432-448 (2001) · Zbl 1006.68102 |
| [11] | 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, 11-20 (2002) |
| [12] | 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, 192-203 (2003) |
| [13] | Corter, J. E.; Tversky, A., Extended similarity trees, Psychometrika, 51, 3, 429-451 (1986) · Zbl 0603.62070 |
| [14] | Cunningham, J. P., Trees as memory representations for simple visual patterns, Memory & Cognition, 8, 6, 593-605 (1980) |
| [15] | Day, W. H., Computational complexity of inferring phylogenies from dissimilarity matrices, Bulletin of Mathematical Biology, 49, 4, 461-467 (1987) · Zbl 0623.92018 |
| [16] | Dias, Z.; Rocha, A.; Goldenstein, S., Image phylogeny by minimal spanning trees, IEEE Transactions on Information Forensics and Security, 7, 2, 774-788 (2012) |
| [17] | Donnet, B., Internet topology discovery, Data Traffic Monitoring and Analysis: From Measurement, Classification, and Anomaly Detection to Quality of Experience. Data Traffic Monitoring and Analysis: From Measurement, Classification, and Anomaly Detection to Quality of Experience, Lecture Notes in Computer Science, 7754, 44-81 (2013), Springer |
| [18] | Donnet, B.; Friedman, T., Internet topology discovery: a survey, IEEE Communications Surveys, 9, 4, 2-14 (2007) |
| [19] | 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, 2210-2220 (2006) |
| [20] | 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, 321-402 (1984) · Zbl 0562.54041 |
| [21] | 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, 26-45 (2002) · Zbl 1059.94050 |
| [22] | 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, 1636-1645 (2001) |
| [23] | Edelberg, M.; Garey, M.; Graham, R., On the distance matrix of a tree, Discrete Mathematics, 14, 23-39 (1976) · Zbl 0328.05103 |
| [24] | 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, 1-9 (2010) |
| [25] | Farach, M.; Kannan, S.; Warnow, T., A robust model for finding optimal evolutionary trees, Algorithmica, 13, 1, 155-179 (1995) · Zbl 0831.92019 |
| [26] | Felsenstein, J., Distance matrix methods, Inferring Phylogenies, chapter 11, 147-175 (2004), Sinauer Associates, Inc: Sinauer Associates, Inc Sunderland, Massachusetts |
| [27] | Fiorini, S.; Joret, G., Approximating the balanced minimum evolution problem, Operations Research Letters, 40, 1, 31-35 (2012) · Zbl 1242.90275 |
| [28] | Gaschen, B.; Taylor, J.; Yusim, K.; Foley, B.; Gao, F.; Lang, D., Diversity considerations in HIV-1 vaccine selection, Science, 296, 5577, 2354-2360 (2002) |
| [29] | Gilmore, G.; Hersh, H.; Caramazza, A.; Griffin, J., Multidimensional letter similarity derived from recognition errors, Perception & Psychophysics, 25, 5, 425-431 (1979) |
| [30] | Gouveia, L., Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop constraints, Computers and Operations Research, 22, 9, 959-970 (1995) · Zbl 0854.90139 |
| [31] | Gouveia, L., Multicommodity flow models for spanning trees with hop constraints, European Journal of Operational Research, 95, 178-190 (1996) · Zbl 0947.90513 |
| [32] | Govindan, R.; Tangmunarunkit, H., Heuristic for internet map discovery, Proceeding of the 19th annual joint conference of IEEE computer and communications societies, volume 3, 1371-1380 (2000) |
| [33] | Haddadi, H.; Rio, M.; Iannaccone, G.; Moore, A.; Mortier, R., Network topologies: inference, modelling and generation, IEEE Communications Surveys, 10, 2, 48-69 (2008) |
| [34] | Hakimi, S. L.; Patrinos, A., The distance matrix of a graph and its tree realization, Quarterly of Applied Mathematics, 30, 255-269 (1972), 73 · Zbl 0293.05103 |
| [35] | Hakimi, S. L.; Yau, S. S., Distance matrix of a graph and its realizability, Quarterly of Applied Mathematics, 22, 305-317 (1965) · Zbl 0125.11804 |
| [36] | Huson, D.; Scornavacca, C., A survey of combinatorial methods for phylogenetic networks, Genome Biology and Evolution, 3, 23-35 (2011) |
| [37] | Isaev, A., Introduction to Mathematical Methods in Bioinformatics (2006), Springer |
| [38] | Junker, B. H.; Schreiber, F., Analysis of Biological Networks (2008), John Wiley & Sons |
| [39] | Koolen, A. L.J.; Moulton, V., Optimal realizations of generic five-point metric, European Journal of Combinatorics, 30, 1164-1171 (2009) · Zbl 1184.05111 |
| [40] | Magnanti, T. L.; Wolsey, L. A., Optimal trees, (Ball, M.; Magnanti, T. L.; Monma, C.; Nemhauser, G. L., Network Models, Handbooks in Operations Research and Management Science, Vol. 7 (1995), Elsevier Science Publishers: Elsevier Science Publishers North-Holland), 503-615 · Zbl 0839.90135 |
| [41] | Miller, C.; Tucker, A.; Zemlin, R., Integer programming formulations and travelling salesman problems, Journal of the Association for Computing Machinery, 7, 4, 326-329 (1960) · Zbl 0100.15101 |
| [42] | Mount, D., Bioinformatics. Sequence and genome analysis (2001), Cold Spring Harbor Laboratory Press |
| [43] | Nei, M.; Kumar, S., Molecular evolution and phylogenetics (2000), Oxford University Press |
| [44] | Ni, J.; Tatikonda, S., Network tomography based on additive metrics, IEEE Transactions on Information Theory, 57, 12, 7798-7809 (2011) · Zbl 1365.90076 |
| [45] | 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) |
| [47] | 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, 1875-1905 (1996) · Zbl 0967.94005 |
| [48] | Pauplin, Y., Direct calculation of a tree length using a distance matrix, Journal of Molecular Evolution, 51, 41-47 (2000) |
| [49] | Sattath, S.; Tversky, A., Additive similarity trees, Psichometrica, 42, 3, 319-345 (1977) |
| [50] | Shih, M.-F.; Hero, A., Hierarchical inference of unicast network topologies based on end-to-end measurements, IEEE Transactions on Signal Processing, 55, 5, 1708-1718 (2007) · Zbl 1391.94039 |
| [51] | Simões-Pereira, J., A note on distance matrices with unicyclic graph realizations, Discrete Mathematics, 65, 277-287 (1987) · Zbl 0674.05048 |
| [52] | Simões-Pereira, J., An algorithm and its role in the study of optimal graph realizations of distance matrices, Discrete Mathematics, 79, 299-312 (1990) · Zbl 0696.05048 |
| [53] | Simões-Pereira, J.; Zamfirescu, C., Submatrices of non-tree-realizable distance matrices, Linear Algebra and its Applications, 44, 1-17 (1982) · Zbl 0483.05045 |
| [54] | Soete, G. D., A least squares algorithm for fitting additive trees to proximity data, Psychometrika, 48, 4, 621-626 (1983) |
| [56] | Varone, S. C., Trees related to realizations of distance matrices, Discrete Mathematics, 192, 337-346 (1998) · Zbl 0955.05070 |
| [57] | Varone, S. C., A constructive algorithm for realizing a distance matrix, European Journal of Operational Research, 174, 1, 102-111 (2006) · Zbl 1116.90092 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
