×

zbMATH — the first resource for mathematics

On mathematical optimization for the visualization of frequencies and adjacencies as rectangular maps. (English) Zbl 1374.90271
Summary: We address the problem of visualizing a frequency distribution and an adjacency relation attached to a set of individuals. We represent this information using a rectangular map, i.e., a subdivision of a rectangle into rectangular portions so that each portion is associated with one individual, their areas reflect the frequencies, and the adjacencies between portions represent the adjacencies between the individuals. Due to the impossibility of satisfying both area and adjacency requirements, our aim is to fit as well as possible the areas, while representing as many adjacent individuals as adjacent rectangular portions as possible and adding as few false adjacencies, i.e., adjacencies between rectangular portions corresponding to non-adjacent individuals, as possible. We formulate this visualization problem as a Mixed Integer Linear Programming (MILP) model. We propose a matheuristic that has this MILP model at its heart. Our experimental results demonstrate that our matheuristic provides rectangular maps with a good fit in both the frequency distribution and the adjacency relation.
MSC:
90B80 Discrete location and assignment
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abbiw-Jackson, R.; Golden, B.; Raghavan, S.; Wasil, E., A divide-and-conquer local search heuristic for data visualization, Computers & Operations Research, 33, 11, 3070-3087, (2006) · Zbl 1113.90127
[2] Alam, M. J.; Biedl, T.; Felsner, S.; Kaufmann, M.; Kobourov, S. G.; Ueckerdt, T., Computing cartograms with optimal complexity, Discrete & Computational Geometry, 50, 3, 784-810, (2013) · Zbl 1275.68110
[3] Anjos, M. F.; Liers, F., Global approaches for facility layout and VLSI floorplanning, Handbook on semidefinite, conic and polynomial optimization, 849-877, (2012), Springer · Zbl 1334.90096
[4] Anjos, M. F.; Vieira, M. V.C., An improved two-stage optimization-based framework for unequal-areas facility layout, Optimization Letters, 10, 7, 1379-1392, (2016) · Zbl 1355.90096
[5] Baudel, T.; Broeksema, B., Capturing the design space of sequential space-filling layouts, IEEE Transactions on Visualization and Computer Graphics, 18, 12, 2593-2602, (2012)
[6] de Berg, M.; Mumford, E.; Speckmann, B., On rectilinear duals for vertex-weighted plane graphs, Discrete Mathematics, 309, 7, 1794-1812, (2009) · Zbl 1182.05121
[7] de Berg, M.; Mumford, E.; Speckmann, B., Optimal BSPs and rectilinear cartograms, International Journal of Computational Geometry & Applications, 20, 02, 203-222, (2010) · Zbl 1187.62004
[8] Biedl, T. C.; Genç, B., Complexity of octagonal and rectangular cartograms., Proceedings of the seventeenth Canadian conference on computational geometry, 117-120, (2005)
[9] Borg, I.; Groenen, P. J.F., Modern multidimensional scaling: theory and applications, (2005), Springer · Zbl 1085.62079
[10] Buchin, K.; Speckmann, B.; Verdonschot, S., Evolution strategies for optimizing rectangular cartograms, Proceedings of the international conference on geographic information science, 29-42, (2012), Springer
[11] Carrizosa, E.; Guerrero, V.; Romero Morales, D., Visualizing data as objects by DC (difference of convex) optimization, Mathematical Programming, (2017) · Zbl 1390.90616
[12] Carrizosa, E.; Guerrero, V.; Romero Morales, D., Visualizing proportions and dissimilarities by space-filling maps: a large neighborhood search approach, Computers & Operations Research, 78, 369-380, (2017) · Zbl 1391.90050
[13] Carrizosa, E.; Martín-Barragán, B.; Plastria, F.; Romero Morales, D., On the selection of the globally optimal prototype subset for nearest-neighbor classification, INFORMS Journal on Computing, 19, 3, 470-479, (2007) · Zbl 1241.90086
[14] Clémençon, S.; De Arazoza, H.; Rossi, F.; Tran, V. C., Hierarchical clustering for graph visualization, Proceedings of the nineteenth European symposium on artificial neural networks, computational intelligence and machine learning, 227-232, (2011)
[15] CPLEX, I. I. (2014). http://www.ilog.com/products/cplex/.
[16] Destatis, Statistisches Bundesamt (2015). Area and population. www.destatis.de. (Accessed on: 2015-01-14).
[17] Dörk, M.; Carpendale, S.; Williamson, C., Visualizing explicit and implicit relations of complex information spaces, Information Visualization, 11, 1, 5-21, (2012)
[18] Duarte, F. S.; Sikansi, F.; Fatore, F. M.; Fadel, S. G.; Paulovich, F. V., Nmap: A novel neighborhood preservation space-filling algorithm, IEEE Transactions on Visualization and Computer Graphics, 20, 12, 2063-2071, (2014)
[19] Eppstein, D.; van Kreveld, M.; Speckmann, B.; Staals, F., Improved grid map layout by point set matching, International Journal of Computational Geometry & Applications, 25, 02, 101-122, (2015) · Zbl 1343.68261
[20] Eppstein, D.; Mumford, E.; Speckmann, B.; Verbeek, K., Area-universal rectangular layouts, Proceedings of the twenty-fifth annual symposium on computational geometry, 267-276, (2009), ACM · Zbl 1380.68394
[21] Fortunato, S., Community detection in graphs, Physics Reports, 486, 3, 75-174, (2010)
[22] Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPL: A modeling language for mathematical programming, (2002), Duxbury Press, Brooks/Cole Publishing Company Stamford
[23] Fried, O.; DiVerdi, S.; Halber, M.; Sizikova, E.; Finkelstein, A., Isomatch: creating informative grid layouts, Computer Graphics Forum, 34, 2, 155-166, (2015)
[24] Gómez-Nieto, E.; San Roman, F.; Pagliosa, P.; Casaca, W.; Helou, E. S.; de Oliveira, M. C.F.; Nonato, L. G., Similarity preserving snippet-based visualization of web search results, IEEE Transactions on Visualization and Computer Graphics, 20, 3, 457-470, (2014)
[25] Hahsler, M., An experimental comparison of seriation methods for one-mode two-way data, European Journal of Operational Research, 257, 1, 133-143, (2017) · Zbl 1394.90482
[26] Heilmann, R.; Keim, D. A.; Panse, C.; Sips, M., Recmap: rectangular map approximations, Proceedings of the IEEE symposium on information visualization, 33-40, (2004), IEEE Computer Society
[27] Herman, I.; Melançon, G.; Marshall, M. S., Graph visualization and navigation in information visualization: A survey, IEEE Transactions on Visualization and Computer Graphics, 6, 1, 24-43, (2000)
[28] Hubert, L.; Arabie, P.; Hesson-Mcinnis, M., Multidimensional scaling in the city-block metric: A combinatorial approach, Journal of Classification, 9, 2, 211-236, (1992)
[29] Jankovits, I.; Luo, C.; Anjos, M. F.; Vannelli, A., A convex optimisation framework for the unequal-areas facility layout problem, European Journal of Operational Research, 214, 2, 199-215, (2011) · Zbl 1218.90102
[30] Keim, D.; Andrienko, G.; Fekete, J. D.; Görg, C.; Kohlhammer, J.; Melançon, G., Visual analytics: definition, process, and challenges, Information visualization, 154-175, (2008), Springer
[31] Klimenta, M.; Brandes, U., Graph drawing by classical multidimensional scaling: new perspectives, Graph drawing, 7704, 55-66, (2013), Springer · Zbl 1377.68179
[32] Koźmiński, K.; Kinnen, E., Rectangular duals of planar graphs, Networks, 15, 2, 145-157, (1985) · Zbl 0585.05029
[33] Kreveld, M.; Speckmann, B., On rectangular cartograms, Computational Geometry, 37, 3, 175-187, (2007) · Zbl 1118.68172
[34] Kruskal, J. B.; Wish, M., Multidimensional scaling, 11, (1978), Sage
[35] Leung, P. L.; Lau, K., Estimating the city-block two-dimensional scaling model with simulated annealing, European Journal of Operational Research, 158, 2, 518-524, (2004) · Zbl 1067.90130
[36] Liu, S.; Cui, W.; Wu, Y.; Liu, M., A survey on information visualization: recent advances and challenges, The Visual Computer, 30, 12, 1373-1393, (2014)
[37] Liu, X.; Hu, Y.; North, S.; Shen, H., Compactmap: A mental map preserving visual interface for streaming text data, Proceedings of the IEEE international conference on big data, 48-55, (2013)
[38] Liu, X.; Hu, Y.; North, S.; Shen, H. W., Correlatedmultiples: spatially coherent small multiples with constrained multi-dimensional scaling, Computer Graphics Forum, 1-12, (2015)
[39] McCormick, G. P., Computability of global solutions to factorable nonconvex programs: part I - convex underestimating problems, Mathematical Programming, 10, 1, 147-175, (1976) · Zbl 0349.90100
[40] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers & Operations Research, 24, 11, 1097-1100, (1997) · Zbl 0889.90119
[41] Mortenson, M. J.; Doherty, N. F.; Robinson, S., Operational research from taylorism to terabytes: A research agenda for the analytics age, European Journal of Operational Research, 241, 3, 583-595, (2015) · Zbl 1339.90007
[42] Nusrat, S.; Kobourov, S., The state of the art in cartograms, Computer Graphics Forum, 35, 3, 619-642, (2016)
[43] Olafsson, S.; Li, X.; Wu, S., Operations research and data mining, European Journal of Operational Research, 187, 3, 1429-1448, (2008) · Zbl 1137.90776
[44] Owen-Smith, J.; Riccaboni, M.; Pammolli, F.; Powell, W. W., A comparison of U.S. and European university-industry relations in the life sciences, Management Science, 48, 1, 24-43, (2002)
[45] Panse, C. (2016). Rectangular Statistical Cartograms in R: The recmap package. arXiv:1606.00464.
[46] Raisz, E., The rectangular statistical cartogram, Geographical Review, 24, 2, 292-296, (1934)
[47] Sherali, H. D.; Fraticelli, B. M.P.; Meller, R. D., Enhanced model formulations for optimal facility layout, Operations Research, 51, 4, 629-644, (2003) · Zbl 1165.90545
[48] Shneiderman, B.; Dunne, C., Interactive network exploration to derive insights: filtering, clustering, grouping, and simplification, Graph drawing, 7704, 2-18, (2013), Springer
[49] Spence, I.; Lewandowsky, S., Displaying proportions and percentages, Applied Cognitive Psychology, 5, 1, 61-77, (1991)
[50] Stanford Blood Center (2014). Blood type in U.S. http://bloodcenter.stanford.edu/. (Accessed on: 2014-11-19).
[51] Statistics Netherlands (2013). Population; gender, age, marital status and region, January 1. www.cbs.nl. (Accessed on: 2013-10-31).
[52] Strong, G.; Gong, M., Self-sorting map: an efficient algorithm for presenting multimedia data in structured layouts, IEEE Transactions on Multimedia, 16, 4, 1045-1058, (2014)
[53] (Tamassia, R., Handbook of graph drawing and visualization, (2013), CRC Press) · Zbl 1275.68033
[54] Tani, K.; Tsukiyama, S.; Shinoda, S.; Shirakawa, I., On area-efficient drawings of rectangular duals for VLSI floor-plan, Mathematical Programming, 52, 1-3, 29-43, (1991) · Zbl 0726.68061
[55] Tobler, W., Thirty five years of computer cartograms, Annals of the Association of American Geographers, 94, 1, 58-73, (2004)
[56] Wächter, A.; Biegler, L. T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming, 106, 1, 25-57, (2006) · Zbl 1134.90542
[57] Wood, J.; Dykes, J., Spatially ordered treemaps, IEEE Transactions on Visualization and Computer Graphics, 14, 6, 1348-1355, (2008)
[58] Žilinskas, A.; Žilinskas, J., Branch and bound algorithm for multidimensional scaling with city-block metric, Journal of Global Optimization, 43, 2, 357-372, (2009) · Zbl 1179.90250
[59] Žilinskas, J., Parallel branch and bound for multidimensional scaling with city-block distances, Journal of Global Optimization, 54, 2, 261-274, (2012) · Zbl 1259.90126
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.