Visualizing proportions and dissimilarities by space-filling maps: a large neighborhood search approach

Visualizing proportions and dissimilarities by Space-filling maps: a Large Neighborhood Search approach∗ Emilio Carrizosa1, Vanesa Guerrero1, and Dolores Romero Morales2 1Instituto de Matem´aticas de la Universidad de Sevilla (IMUS), Seville, Spain {ecarrizosa, vguerrero}@us.es 2Copenhagen Business School, Frederiksberg, Denmark [email protected] Abstract In this paper we address the problem of visualizing a set of individuals, which have attached a statistical value given as a proportion, and a dissimilarity measure. Each individual is represented as a region within the unit square, in such a way that the area of the regions represent the proportions and the distances between them represent the dissimilarities. To enhance the interpretability of the representation, the regions are required to satisfy two properties. First, they must form a partition of the unit square, namely, the portions in which it is divided must cover its area without overlapping. Second, the portions must be made of a connected union of rectangles which verify the so-called box-connectivity constraints, yielding a visualization map called Space-filling Box-connected Map (SBM). The construction of an SBM is formally stated as a mathematical optimization problem, which is solved heuristically by using the Large Neighborhood Search technique. The methodology proposed in this paper is applied to three real-world datasets: the first one concerning financial markets in Europe and Asia, the second one about the letters in the English alphabet, and finally the provinces of The Netherlands as a geographical application. Keywords: Data Visualization, Box-connectivity, Proportions, Dissimilarities, Large Neighborhood Search 1 Introduction Information Visualization has experienced a tremendous development in recent years as a result of the data storage growth, [38,56]. Visualizing data with complex underlying structures has become a crucial task to help analysts to draw conclusions by detecting patterns and behaviours which remain hidden when classic techniques are applied, [9,10,23]. Mathematical Optimization plays an important role in the field of Information Visualization, both developing new tools to adapt existent visualization techniques and creating new ones, [7,24,28,42]. In this paper, Mathematical Optimization is used to build a planar space-filling visualization map, in the sense that the whole region in which the data are visualized is covered. The framework developed ∗This research is funded in part by Projects MTM2015-65915-R (Spain), P11-FQM-7603 and FQM-329 (Andaluc´ıa), all with EU ERD Funds. 1 in this work is able to properly represent statistical values (given as proportions) attached to individuals as well as proximity relationships (given by a dissimilarity matrix). There exist several contexts in which proportions need to be properly visualized. Some straightforward examples are population rates or vote intention rates. Classic representations as pie or fan charts can handle this type of data, [53]. In addition to statistical values, there usually exists a relationship between the individuals in the form of a dissimilarity, such as geographical distances or affinity between political parties. Pie/fan charts and related ones, [19], are very limited to properly depict dissimilarities, since the set of possible locations for the different wedges is reduced to a choice of a permutation. Thus, more sophisticated visualization tools which simultaneously deal with both types of information are needed. For instance, there exist approaches which integrate Graph Drawing techniques, [2], with multivariate statistical approaches like Multidimensional Scaling (MDS), as in [17,33], or Correspondence Analysis, as in [45]. For a comprehensive survey on recent visualization frameworks see [38]. Nevertheless, combining simultaneously the representation of proportions and dissimilarities in a planar visualization map is still a challenging problem to which very specific (ad-hoc) approaches exist. This is the case, for instance, of frameworks developed by Cartography. Cartograms try to reproduce the geographical distances between the regions while they are scaled, and thus deformed, according to a statistical variable, such as the population rates [57]. There are also approaches in which the regions are reshaped, for instance, to rectangles, [29,36], piecewise rectangles, [1,14], or circles [18]. Techniques to build cartograms take advantage of geographical information to properly depict dissimilarities, yielding very specific approaches that usually cannot be extended to more general examples, such as the ones handled in our computational section. Other disciplines which have dealt with the problem of representing simultaneously statistical values and dissimilarities are Facility Layout and Information Visualization. In Facility Layout, the aim is to locate the facilities with a given area according to the flow between facilities, [32,34,51], without necessarily producing space-filling layouts. A wellknown example in Information visualization is the treemap, [4,52], in which the unit square is sequentially subdivided to represent a hierarchy between the individuals satisfying that each region has a desired area. Treemaps are space-filling layouts which represent exactly the statistical values as the area of the rectangles but, in general, they fail to properly represent dissimilarities. Other attempts, such as [6,17,26,27,39,55], either disregard dissimilarities or proportions, or they are not space-filling visualization maps. In [5,20], space-filling rectangular maps are proposed, which take into consideration both dissimilarities and proportions. However, the geometrical shape used to represent each individual (a rectangle) seems to be too rigid to give a good fit in both dissimilarities and proportions. In [36], there is an example illustrating that it may be impossible to represent accurately both types of information in space-filling rectangular maps. In that paper, a dissimilarity matrix representing adjacencies is considered. A partition of a square into rectangles is sought such that the rectangles’ areas depict the proportions and adjacencies between rectangles represent the given adjacency matrix. However, they show in a figure (Figure 2) how the exact representation of the adjacency matrix is not possible when an accurate visualization of the proportions is desired. In this paper, we develop a general optimization-based framework to visualize a set of N individuals, V={v1, . . . , vN}, as Nconnected regions, P= (P1, . . . , PN), on the unit square, Ω = [0,1]×[0,1], with two types of information attached: a statistical value given as a proportion, ω= (ω1, . . . , ωN) such that PN r=1 ωr= 1 and ωr≥0, r= 1, . . . , N, as well as a dissimilarity measure δ= (δrs)r,s=1,...,N , such that δrs ≥0 and δrr = 0. To enhance the interpretability of 2 the representation, the portions in Pare required to satisfy two properties. First, they must form a partition of Ω, namely, the portions in which it is divided must cover its area without overlapping. Second, the portions must be made of a connected union of rectangles which verify the so-called box-connectivity property (to be formally stated later). We refer to such representation hereafter as a Space-filling Box-connected Map (SBM). The remainder of this paper is structured as follows. In Section 2, we first establish the conditions that an SBM must satisfy. After defining the concept of box-connectivity, the problem of constructing an SBM is formally stated as a biobjective Mixed Integer Nonlinear Problem (MINLP) and this is then reformulated into two single-objective Mixed Integer Linear Programs (MILP). Finally, an equivalent formulation to these MILPs is provided, which, although less natural, is shown to be tighter in general. Due to the high computational effort needed to solve such optimization problems, heuristics are to be used. In Section 3, Large Neighborhood Search (LNS), [47,50], is adapted to our problem. Section 4contains the numerical experiments of our methodology on three datasets of different nature. The first one consists of visualizing as an SBM the world market portfolio of financial markets across Europe and Asia, [21], according to their correlation, [3]; the second dataset deals with the representation of the relative frequencies of letters in the English language, [49], and the confusion between acoustic Morse signals, [3]; the last one is a geographical example in which the provinces of The Netherlands are scaled by their population rates, [54], while preserving their geographical location. Section 5includes some remarks and future work. Finally, the Appendix closes the paper with some technical details. 2 The model In this section we first formally state the conditions that a Space-filling Box-connected Map (SBM) must satisfy, namely a visualization map in which the set of individuals Vis represented as a partition into box-connected regions P(referred also as portions) on the unit square Ω. The construction of an SBM is modelled as a Mathematical Optimization problem, for which an equivalent reformulation, which turns out to be tighter in terms of its continuous relaxation, is also presented. 2.1 Problem statement In order to construct an SBM, we consider Ω partitioned into Krows and Lcolumns, called in what follows (K, L)-grid. Pairs of cells forming a (K, L)-grid are considered adjacent if they share one full side, which implies that a cell can have at most four adjacent cells. Grid structures are commonly used in Reserve Network design to arrange a connected union of sites to protect ecosystems and species [31,43,44]. Since the grid layout provides a well-structured and compact representation, it has been also used in visualization map designs as in [26,39,55], and in Facility Layout as a tool to easily measure the area of the facilities [34]. Definition 1. Given two cells (i, j)and (i0, j0)in a (K, L)-grid, we define the box generated by (i, j)and (i0, j0)as B((i, j),(i0, j0)) = {(i00, j00)∈(K, L)-grid : min{i, i0} ≤ i00 ≤max{i, i0}, min{j, j0} ≤ j00 ≤max{j, j0}} . 3 1 2 3 4 1 2 3 4 (a) 1 2 3 4 1 2 3 4 (b) 1234 1 2 3 4 (c) 1 2 3 4 1 2 3 4 (d) 1 2 3 4 1 2 3 4 (e) Figure 1: Shaded cells in (a),(b) and (c) are not box-connected regions, while shaded cells in (d) and (e) are box-connected regions. Definition 2. Let Sbe a subset of cells of a (K, L)-grid and let |S|denote its cardinality. Sis said to be box-connected if one of these conditions holds: 1. |S|= 1. 2. |S|= 2 and its two cells are adjacent. 3. |S| ≥ 3and for all non-adjacent (i, j),(i0, j0)∈S, there exists (i00, j00)∈B((i, j),(i0, j0))∩S such that (i00, j00)6= (i, j)and (i00, j00)6= (i0, j0). Each individual vrmust be depicted in the SBM as a unique box-connected portion Prmade of cells in the (K, L)-grid. Shaded cells in Figures 1 (a) -1 (c) represent portions that are not allowed in our representation, since they do not verify the box-connectivity stated in Definition 2. Regarding Figure 1 (a), there are no shaded cells in the intersection of the set containing the shaded cells and the box B((2,2),(2,4)), except for (2,2) and (2,4). Analogously, in 1 (b) considering B((2,2),(3,3)). Thus, we observe that disconnected portions are obviously not boxconnected. Finally, Figure 1 (c) violates box-connectivity when considering, for instance, the box B((2,4),(4,4)). Possible shapes allowed to represent the individuals in Vare depicted in Figures 1 (d) and 1 (e). The construction of an SBM regards the partition of Ω into Nbox-connected portions, which are made of cells in the (K, L)-grid in which Ω is subdivided, and in such a way that the areas of the portions depict the statistical values, ω, and the distances between the portions are proportional to the dissimilarities, δ. These statements can be summed up in the following conditions: (D1) The portions in P= (P1, . . . , PN) form a partition of Ω = [0,1] ×[0,1], (D2) Pris a box-connected region, made up of a collection of cells of the (K, L)-grid in which Ω is divided, r= 1, . . . , N, (D3) distance(Pr, Ps)∝δrs,r, s = 1, . . . , N,r6=s, 4 (D4) area(Pr) = ωr, namely 1 K×L|Pr|=ωr,∀r= 1, . . . , N, where |Pr|denotes the number of cells in Pr,r= 1, . . . , N. Since the portions in Pare made of connected unions of cells and they form a partition of Ω, the grid structure helps to easily measure the closeness and the area of the portions. In order to measure the distance between portions Prand Psin (D3), those usually used in Cluster Analysis like the single, complete and average linkage, [28], seem suitable for an SBM. 2.2 The Mathematical Optimization model An SBM which satisfies conditions (D1) and (D2) can be obtained straightforwardly by allocating cells belonging to the same portion sequentially until filling Ω. However, including conditions (D3) and (D4) as hard requirements might make the problem unfeasible, [36]. Thus, our model consists of building SBMs in which the errors made by approximating the scaled dissimilarities, through a real positive variable κ, by the distances between the portions, and the statistical values by their areas, both measured in absolute value, are minimized. Our model considers then the violation of conditions (D3) and (D4) as objectives to be minimized, yielding a Biobjective Space-filling Box-Connected Map (BSBM) model, which reads as follows min X r,s=1,...,N r6=s |distance(Pr, Ps)−κδrs| min X r=1,...,N |area(Pr)−ωr| s.t. P= (P1, . . . , PN) satisfying (D1) and (D2) κ≥0. (BSBM) The (BSBM) problem can be reformulated as a parametric problem, parametrized by a real positive number α, in which the error between the distances in the SBM and the scaled dissimilarities is minimized among those maps whose area error is less or equal than α, yielding the single objective problem (α−SBM). (BSBM) can be also parametrized by a real positive number β, in which the error between the areas depicted in the SBM is minimized among those maps whose error between the scaled dissimilarities and the distances in the map is less or equal than β, yielding the single objective problem (β−SBM): min X r,s=1,...,N r6=s |distance(Pr, Ps)−κδrs| s.t. P= (P1,...,PN) satisfying (D1) and (D2) X r=1,...,N |ωr−area(Pr)| ≤ α κ≥0. (α−SBM) min X r=1,...,N |area(Pr)−ωr| s.t. P= (P1,...,PN) satisfying (D1) and (D2) X r,s=1,...,N r6=s |distance(Pr, Ps)−κδrs| ≤ β κ≥0. (β−SBM) In what follows, we formally state the problem (α−SBM) as a Mixed Integer Nonlinear Program (MINLP), and a similar approach can be used for (β−SBM). Let xrij,r= 1, . . . , N,i= 1, . . . , K and j= 1, . . . , L, be binary variables which determine if cell (i, j) belongs to portion Pror not, namely 5 xrij =1 if cell (i, j) belongs to portion Pr 0 otherwise. Thanks to these variables, we express portion Pras Pr(x) = {(i, j) : xrij = 1, i = 1, . . . K, j = 1, . . . , L}. Therefore, (α−SBM) can be stated as follows: min X r,s=1,...,N r6=s |distance(Pr(x), Ps(x)) −κδrs|(1) s.t. X r=1,...,N xrij = 1 i= 1, . . . , K, j = 1,...,L (2) X i=1,...,K j=1,...,L xrij ≥1r= 1,...,N (3) xrij ∈ {0,1}r= 1,...,N, (4) i= 1, . . . , K, j = 1,...,L κ≥0 (5) X (i00,j00)∈B((i,j),(i0,j0)) (i00,j00)6=(i,j) (i00,j00)6=(i0,j0) xri00j00 ≥xrij +xri0j0−1r= 1,...,N, (6) i, i0= 1, . . . , K, j, j0= 1,...,L, such that cells (i, j) and (i0, j0) are non-adjacent X r=1,...,N             1 KL X i=1,...,K j=1,...,L xrij     −ωr         ≤α. (7) Constraint (2) models condition (D1), since it forces that every cell must belong to exactly one portion. In order to have at least one cell assigned to every portion, constraint (3) is considered. Constraints (4) and (5) establish the type of the variables. The box-connectivity in Definition 2, and required in (D2), is enforced through constraint (6). The box-connectivity of Pr(x) is enforced by imposing that the box generated by each pair of non-adjacent cells belonging to Pr(x) (two cells that do not share a common boundary) must contain also cells of Pr(x), namely the intersection between such box (excluding its two generator cells) and the portion must be nonempty. Finally, the error incurred by approximating the statistical values ωby the area of the portions is modeled through constraint (7). The objective in (1) remains to be modeled through the variables stated. Indeed, its expression will depend on the choice of the distance function. With the choices mentioned above related to Cluster Analysis, namely the single linkage (SL), the complete linkage (CL) and the average linkage (AvL), these distances can be easily expressed through the binary variables of our mathematical optimization problem, namely xrij. Firstly, we need to define how to measure the distance between two single cells. Since the grid structure naturally calls for the use of the `1-norm, given two cells (i, j) and (i0, j0), the distance between them is equal to |i−i0|+|j−j0|, where i, i0= 1, . . . , K and j, j0= 1, . . . , L. Thus, the distance between two portions Pr(x) and Ps(x) on an SBM, distance(Pr(x), Ps(x)), can be expressed respectively as SL(Pr(x), Ps(x)), or 6 CL(Pr(x), Ps(x)), or AvL(Pr(x), Ps(x)), defined as SL(Pr(x), Ps(x)) = min i,i0=1,...,K j,j0=1,...,L |i−i0|+|j−j0|:xrij =xsi0j0= 1,(8) CL(Pr(x), Ps(x)) = max i,i0=1,...,K j,j0=1,...,L |i−i0|+|j−j0|:xrij =xsi0j0= 1,(9) AvL(Pr(x), Ps(x)) = 1 |Pr(x)||Ps(x)|X i,i0=1,...,K j,j0=1,...,L (|i−i0|+|j−j0|)·xrij ·xsi0j0,(10) where |Pr(x)|(resp. |Ps(x)|) denotes the number of cells of the portion Pr(x), i.e., |Pr(x)|= X i=1,...,K j=1,...,L xrij. Summing up, the problem (α−SBM) is stated as an MINLP as min {(1) : s.t. (2)−(7)},(α−SBM) where distance(Pr(x), Ps(x)) in (1) is replaced by either SL(Pr(x), Ps(x)), CL(Pr(x), Ps(x)) or AvL(Pr(x), Ps(x)), as in (8)-(10) respectively. One has that, for the SL and CL distances, (α−SBM) can be easily reformulated as a MILP, and as an approximation to an MILP in the case of AvL. These three reformulations of (α−SBM), one for each distance function, are included in the Appendix, and they are called (α−SBM)L SL, (α−SBM)L CL and (α−SBM)L AvL, respectively. Note that the statement of the problem (β−SBM) as an MINLP and its pertinent reformulation as an MILP or an approximation to an MILP, yielding (β−SBM)L SL, (β−SBM)L CL and (β−SBM)L AvL, are straightforward from the work done for (α−SBM). 2.3 A tighter model Problems (α−SBM) and (β−SBM) enforce the box-connectivity of the portions Pin the SBM through constraint (6). There exist several attempts in the literature which deal with the problem of modeling connectivity with integer programming, for instance using graph theory, [31,43], designing the connected portions according to fixed locations, [44], or considering nodecut sets, [8,58]. Definition 3. Let G= (U, E)be a graph, whose nodes Uare the cells of a (K, L)-grid. If two nodes u, u0∈Uare adjacent on the grid, then there exists an edge (u, u0)∈Elinking the two nodes. Given two non-adjacent nodes u, v ∈U, a set of nodes C⊆U\ {u, v}is a node-cut separating uand vif there is no path between uand vin the subgraph G0= (U\C, E \E0), where E0={(w, w0) : w, w0∈C∪ {u, v}}. Figure 2illustrates some possible node-cuts on a (4,4)-grid: a horizontal cut for cells (1,2) and (4,4) in Figure 2 (a), a vertical cut for the same cells in Figure 2 (b) and a diagonal cut in Figure 2 (b) for cells (2,2) and (3,3). 7 1 2 3 4 1 2 3 4 (a) Horizontal node-cut 1 2 3 4 1 2 3 4 (b) Vertical node-cut 1 2 3 4 1 2 3 4 (c) Diagonal node-cut Figure 2: Dashed cells illustrate node-cuts of shaded cells on a (4,4)-grid Thanks to Definition 3, the box-connectivity constraint, namely (6), can be modeled through intersections of node-cuts yielding an equivalent formulation for problems (α−SBM) and (β−SBM). In what follows, we prove that box-connectivity can be equivalently modeled through the following set of constraints: X i<i00<i0 min{j,j0}≤j00≤max{j,j0} xri00j00 ≥xrij +xri0j0−1r= 1,...,N, (6a) i= 1,...,K−2, i0=i+ 2,...,K, j, j0= 1,...,L, X min{i,i0}≤i00≤max{i,i0} j<j00<j0 xri00j00 ≥xrij +xri0j0−1r= 1,...,N, (6b) i, i0= 1,...,K, j= 1,...,L−2, j0=j+ 2,...,L xr,i−1,j +xr,i,j−1≥xrij +xr,i−1,j−1−1r= 1,...,N, (6c) i= 2, . . . , K, j = 2,...,L xr,i−1,j +xr,i,j+1 ≥xrij +xr,i−1,j+1 −1r= 1,...,N, (6d) i= 2, . . . , K, j = 1,...,L−1 xr,i+1,j +xr,i,j−1≥xrij +xr,i+1,j−1−1r= 1,...,N, (6e) i= 1,...,K−1, j = 2,...,L xr,i+1,j +xr,i,j+1 ≥xrij +xr,i+1,j+1 −1r= 1,...,N, (6f) i= 1,...,K−1, j = 1,...,L−1 Constraint (6a) considers bounded horizontal node-cuts, in the sense that it considers that if two cells belong to the same portion and are placed in different and non-contiguous rows, namely there is at least a row in between, then there must exist cells belonging also to that portion in the rows strictly in between them. On the other hand, constraint (6b) addresses bounded vertical node-cuts, which analogous to the horizontal ones but considering columns instead of rows. Finally, constraints (6c)-(6f) model diagonal node-cuts, as this in Figure 2 (c), namely if two cells belong to the same portion and they touch in one corner (shaded cells), then one of the two cells in the diagonal crossing that corner must also belong to such portion (striped cells). Let us consider the problem (α−SBM) stated as (α−SBM)box = min {(1) : s.t. (2)−(7)} 8 and (α−SBM)cut = min {(1) : s.t. (2)−(5),(6a)−(6f),(7)}. Proposition 1. One has that problems (α−SBM)box and (α−SBM)cut are equivalent. Proof. Observe that constraints (2)-(5) and (7) appear in both problems, and thus it remains to prove that constraint (6) is equivalent to constraints (6a)-(6f). Let us prove such statement for a portion Pr(x), denoted Sto simplify. Let us prove that, if Sis box-connected, then (6a)-(6f) hold. Suppose that (6a) fails. Then, the summation on the left-hand-side is equal to zero, which means that there exist two cells (i, j),(i0, j0)∈S, such that i<i0−1 and (i00, j00) : i<i00 < i0,min{j, j0} ≤ j00 ≤max{j, j0}∩S=∅.(11) In particular, (11) is also true when j0=j. This means (i00, j) : i<i00 < i0∩S=∅.(12) On the other hand, Sis box-connected and then, ∃(i00, j)∈B(i, j),(i0, j)∩S, such that i00 6=iand i00 6=i0, which is clearly in contradiction with (12). Using a similar procedure, we can prove that (6b)-(6f) also hold. Conversely, let us prove that, if (6a)-(6f) are satisfied, then Sis box-connected. Let (i, j),(i0, j0)∈Ssuch that i < i0−1. Since (6a) is satisfied, there exists (i00, j00)∈Ssuch that i<i00 < i0and min{j, j0} ≤ j00 ≤max{j, j0}, which implies that (i00, j00)∈B((i, j),(i0, j0))∩ S, and it is different from (i, j) and (i0, j0). This proves the desired result. The case in which j < j0−1, constraint (6b) applies, showing that Sis box-connected. Finally, for pairs of cells belonging to Ssuch that {(i, j),(i−1, j −1)},{(i, j),(i−1, j + 1)}, {(i, j),(i+ 1, j −1)}and {(i, j),(i+ 1, j + 1)}, constraint (6c)-(6f) yield, respectively, the boxconnectivity of S. In order to choose between the (α−SBM)box or the (α−SBM)cut formulations, we study their continuous relaxation tightness. The formulation with the tightest continuous relaxation will be the preferred. Thus, let us consider the continuous relaxations of the MINLP problems (α−SBM)box and (α−SBM)cut, obtained by substituting constraint (4) by 0 ≤xrij ≤1, r= 1, . . . , N, i = 1, . . . , K, j = 1, . . . , L, and denoted as R((α−SBM)box) and R((α−SBM)cut) respectively. We show in what follows that, while the MINLP problems (α−SBM)box and (α−SBM)cut are equivalent, as stated in Proposition 1, it turns out that R((α−SBM)cut), is, in general, tighter than R((α−SBM)box). Let v(R((α−SBM)box)) and v(R((α−SBM)cut)) be the optimal objective values of problems R((α−SBM)box) and R((α−SBM)cut), respectively. Proposition 2. One has that v(R((α−SBM)box)) ≤v(R((α−SBM)cut)).(13) 9 5 Conclusions and future research In this paper, we have formally introduced a mathematical optimization formulation for the problem of visualizing as a space-filling box-connected map a set of individuals which have attached a statistical variable, represented as a proportion, and a dissimilarity measure. This visualization problem is addressed by simultaneously optimizing the error incurred when approximating the statistical values by the area of the portions and the dissimilarities by the distances among them, satisfying the condition that the portions are box-connected and they must form a partition of the unit square. Such approach yields a biobjective optimization problem, which is solved as a single-objective problem that optimizes the fit in distances ensuring a very accurate fit in the sizes of the portions. The Large Neighborhood Search metaheuristic has been proposed to deal with big instances of such problems, due to the fact that the combinatorial structure underlying in the optimization problems makes solving them to optimality too time-demanding. The usefulness of our approach has been illustrated in a variety of data sets, related to market indices, the Morse code and a geographical map. There are several interesting extensions to the methodology proposed in this paper which deserve further study. For instance, considering visualization regions different from the unit square, in which a regular grid cannot be obtained in a straightforward manner, is a challenging problem when modeling portions’ connectivity, [8,58]. Representing simultaneously dissimilarities not only between individuals but also between groups of individuals is a demanding task which deserves further study, [11,30]. This extension can be applied when designing the arrangement of the members of a parliament, since all the members belonging to the same party should be seated close to each other, in the sense that they must form a connected portion and everybody must be as close as possible to everyone in his/her party. In addition, the different parties should be ideally placed in the parliament accordingly to their ideology. There are many contexts in which dissimilarities and the statistical values vary over time, for instance stock markets, or in which individual appear and disappear over time, for instance most used words related to a trending topic in Twitter. Thus, modeling dynamical SBMs which can handle these temporal changes seems to be also a very interesting problem, [13,15,41]. References [1] M.J. Alam, T. Biedl, S. Felsner, M. Kaufmann, S.G. Kobourov, and T. Ueckerdt. Computing cartograms with optimal complexity. Discrete & Computational Geometry, 50(3):784– 810, 2013. [2] G. D. Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph drawing: algorithms for the visualization of graphs. Prentice Hall PTR, 1998. [3] I. Borg and P.J.F. Groenen. Modern Multidimensional Scaling: Theory and Applications. Springer, 2005. [4] K. Buchin, D. Eppstein, M. L¨offler, M. N¨ollenburg, and R. I. Silveira. Adjacency-preserving spatial treemaps. In Algorithms and Data Structures, pages 159–170. Springer, 2011. [5] E. Carrizosa, V. Guerrero, and D. Romero Morales. A multi-objective approach to visualize adjacencies in weighted graphs by rectangular maps. Technical report, Optimization Online, 2015. http://www.optimization-online.org/DB_HTML/2015/12/5226.html. 16 [6] E. Carrizosa, V. Guerrero, and D. Romero Morales. Visualizing data as objects by DC (difference of convex) optimization. Technical report, Optimization Online, 2015. http: //www.optimization-online.org/DB_HTML/2015/12/5227.html. [7] E. Carrizosa and D. Romero Morales. Supervised classification and mathematical optimization. Computers & Operations Research, 40(1):150–165, 2013. [8] R. Carvajal, M. Constantino, M. Goycoolea, J. P. Vielma, and A. Weintraub. Imposing connectivity constraints in forest planning models. Operations Research, 61(4):824–836, 2013. [9] C. P. Chen and C.-Y. Zhang. Data-intensive applications, challenges, techniques and technologies: A survey on big data. Information Sciences, 275:314–347, 2014. [10] J. Choo and H. Park. Customizing computational methods for visual analytics with big data. IEEE Computer Graphics and Applications, 33(4):22–28, 2013. [11] S. Cl´emen¸con, H. De Arazoza, F. Rossi, and V.C. Tran. Hierarchical clustering for graph visualization. In 19th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN 2011), pages 227–232, 2011. [12] IBM ILOG CPLEX. http://www.ilog.com/products/cplex/, 2014. [13] W. Cui, Y. Wu, S. Liu, F. Wei, M. X. Zhou, and H. Qu. Context preserving dynamic word cloud visualization. In IEEE Pacific Visualization Symposium (PacificVis), pages 121–128. IEEE, 2010. [14] M. de Berg, E. Mumford, and B. Speckmann. Optimal BSPs and rectilinear cartograms. International Journal of Computational Geometry & Applications, 20(02):203–222, 2010. [15] R. Dantas de Pinho, M. C. Ferreira de Oliveira, and A. de Andrade Lopes. An incremental space to visualize dynamic data sets. Multimedia Tools and Applications, 50(3):533–562, 2010. [16] E. Demir, T. Bekta¸s, and G. Laporte. An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research, 223(2):346–359, 2012. [17] M. D¨ork, S. Carpendale, and C. Williamson. Visualizing explicit and implicit relations of complex information spaces. Information Visualization, 11(1):5–21, 2012. [18] D. Dorling. Area cartograms: their use and creation. In Concepts and Techniques in Modern Geography series no. 59. University of East Anglia: Environmental Publications, 1996. [19] G. M. Draper, Y. Livnat, and R. F. Riesenfeld. A survey of radial methods for information visualization. IEEE Transactions on Visualization and Computer Graphics, 15(5):759–776, 2009. [20] F. S. Duarte, F. Sikansi, F. M. Fatore, S. G. Fadel, and F. V. Paulovich. Nmap: A novel neighborhood preservation space-filling algorithm. IEEE Transactions on Visualization and Computer Graphics, 20(12):2063–2071, 2014. 17 [21] T. Flavin, M. Hurley, and F. Rousseau. Explaining stock market correlation: A gravity model approach. The Manchester School, 70:87–106, 2002. [22] R. Fortet. Applications de l’alg`ebre de Boole en recherche op´erationelle. Revue Fran¸caise de Recherche Op´erationelle, 4:17–26, 1960. [23] K. Fountoulakis and J. Gondzio. Performance of first- and second-order methods for `1- regularized least square problems. Technical Report ERGO-15-005, 2015. arXiv:1503. 03520. [24] K. Fountoulakis and J. Gondzio. A second-order method for strongly convex `1- regularization problems. Mathematical Programming, 156(1):189–219, 2016. [25] R. Fourer, D. M. Gay, and B. W. Kernighan. AMPL: A Modeling Language for Mathematical Programming. Thomson/Brooks/Cole, 2003. [26] O. Fried, S. DiVerdi, M. Halber, E. Sizikova, and A. Finkelstein. Isomatch: Creating informative grid layouts. In Computer Graphics Forum, volume 34, pages 155–166. Wiley Online Library, 2015. [27] E. G´omez-Nieto, F. San Roman, P. Pagliosa, W. Casaca, E. S. Helou, M. C. F. de Oliveira, and L. G. Nonato. Similarity preserving snippet-based visualization of web search results. IEEE Transactions on Visualization and Computer Graphics, 20(3):457–470, 2014. [28] P. Hansen and B. Jaumard. Cluster analysis and mathematical programming. Mathematical Programming, 79(1-3):191–215, 1997. [29] R. Heilmann, D. A. Keim, C. Panse, and M. Sips. Recmap: Rectangular map approximations. In Proceedings of the IEEE Symposium on Information Visualization, pages 33–40. IEEE Computer Society, 2004. [30] I. Herman, G. Melan¸con, and M.S. Marshall. Graph visualization and navigation in information visualization: A survey. IEEE Transactions on Visualization and Computer Graphics, 6(1):24–43, 2000. [31] N. Jafari and J. Hearne. A new method to solve the fully connected reserve network design problem. European Journal of Operational Research, 231(1):202–209, 2013. [32] I. Jankovits, C. Luo, M. F. Anjos, and A. Vannelli. A convex optimisation framework for the unequal-areas facility layout problem. European Journal of Operational Research, 214(2):199–215, 2011. [33] M. Klimenta and U. Brandes. Graph drawing by classical multidimensional scaling: new perspectives. In Graph Drawing, volume 7704, pages 55–66. Springer, 2013. [34] J. S. Kochhar, B. T. Foster, and S. S. Heragu. HOPE: a genetic algorithm for the unequal area facility layout problem. Computers & Operations Research, 25(7):583–594, 1998. [35] J. E. Korsvik, K. Fagerholt, and G. Laporte. A large neighbourhood search heuristic for ship routing and scheduling with split loads. Computers & Operations Research, 38(2):474–483, 2011. 18 [36] M. van Kreveld and B. Speckmann. On rectangular cartograms. Computational Geometry, 37(3):175–187, 2007. [37] R. E. Lewand. Cryptological Mathematics. The Mathematical Association of America, Washington, D. C., 2000. [38] S. Liu, W. Cui, Y. Wu, and M. Liu. A survey on information visualization: recent advances and challenges. The Visual Computer, 30(12):1373–1393, 2014. [39] X. Liu, Y. Hu, S. North, and H. W. Shen. Correlatedmultiples: Spatially coherent small multiples with constrained multi-dimensional scaling. Computer Graphics Forum, pages 1–12, 2015. [40] A. Lodi, E. Malaguti, N. E. Stier-Moses, and T. Bonino. Design and control of publicservice contracts and an application to public transportation systems. Management Science, 62(4):1165–1187, 2015. [41] D. Mashima, S. G. Kobourov, and Y. Hu. Visualizing dynamic data with maps. IEEE Transactions on Visualization and Computer Graphics, 18(9):1424–1437, 2012. [42] S. Olafsson, X. Li, and S. Wu. Operations research and data mining. European Journal of Operational Research, 187(3):1429–1448, 2008. [43] H. ¨ Onal and R. A. Briers. Optimal selection of a connected reserve network. Operations Research, 54(2):379–388, 2006. [44] H. ¨ Onal, Y. Wang, S. T. M. Dissanayake, and J. D. Westervelt. Optimal design of compact and functionally contiguous conservation management areas. European Journal of Operational Research, 251(3):957–968, 2016. [45] J. Owen-Smith, M. Riccaboni, F. Pammolli, and W.W. Powell. A comparison of U.S. and European university-industry relations in the life sciences. Management Science, 48(1):24– 43, 2002. [46] D. Pacino and P. Van Hentenryck. Large neighborhood search and adaptive randomized decompositions for flexible jobshop scheduling. In International Joint Conference on Artificial Intelligence, 2011. [47] D. Pisinger and S. Ropke. Large neighborhood search. In M. Gendreau and J. Y. Potvin, editors, Handbook of Metaheuristics, volume 146, chapter 13, pages 399–419. Springer US, 2010. [48] G. M. Ribeiro and G. Laporte. An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research, 39(3):728–735, 2012. [49] E. Z. Rothkopf. A measure of stimulus similarity and errors in some paired-associate learning tasks. Journal of Experimental Psychology, 53(2):94, 1957. [50] P. Shaw. Using constraint programming and local search methods to solve vehicle routing problems. In M. Maher and J.F. Puget, editors, Principles and Practice of Constraint Programming - CP98, volume 1520, pages 417–431. Springer, Berlin Heidelberg, 1998. 19 [51] H. D. Sherali, B.M.P. Fraticelli, and R.D. Meller. Enhanced model formulations for optimal facility layout. Operations Research, 51(4):629–644, 2003. [52] B. Shneiderman. Tree visualization with tree-maps: 2-d space-filling approach. ACM Transactions on Graphics, 11(1):92–99, 1992. [53] I. Spence and S. Lewandowsky. Displaying proportions and percentages. Applied Cognitive Psychology, 5(1):61–77, 1991. [54] Statistics Netherlands. Population; gender, age, marital status and region, January 1. www.cbs.nl, 2013. Retrieved on: 2013-10-31. [55] G. Strong and M. Gong. Self-sorting map: An efficient algorithm for presenting multimedia data in structured layouts. IEEE Transactions on Multimedia, 16(4):1045–1058, 2014. [56] J. Thomas and P.C. Wong. Visual analytics. IEEE Computer Graphics and Applications, 24(5):20–21, 2004. [57] W. Tobler. Thirty five years of computer cartograms. Annals of the Association of American Geographers, 94(1):58–73, 2004. [58] Y. Wang, A. Buchanan, and S. Butenko. On imposing connectivity constraints in integer programs. Technical report, Optimization Online, 2015. http://www. optimization-online.org/DB_HTML/2015/02/4768.html. [59] V. Yoghourdjian, T. Dwyer, G. Gange, S. Kieffer, K. Klein, and K. Marriott. High-quality ultra-compact grid layout of grouped networks. IEEE Transactions on Visualization and Computer Graphics, 22(1):339–348, 2016. 20 Appendix In this appendix, the MINLP problem (α−SBM) problem is formally stated as an MILP, when using the Single and the Complete Linkage (SL and CL, respectively), defined in (8) and (9), and as an approximation to an MILP when considering the Average Linkage (AvL), stated in (10). In all the cases, we use the usual techniques to linearize the product of binary variables proposed in [22] and the absolute values both in the objective function and constraint (7). Thus, we consider the following reformulations R1,R2 and R3 stated as follows: R1: let ursiji0j0be defined as ursiji0j0=xrij ·xsi0j0, which implies that ursiji0j0=1 if cell (i, j) belongs to portion Prand the (i0, j0) belongs to portion Ps 0 otherwise. The following set of constraints is also needed to be included in the linear reformulation to properly linearize the product: ursiji0j0≤xrij r, s = 1, . . . N, i, i0= 1, . . . , K, j, j0= 1, . . . , L (14) ursiji0j0≤xsi0j0r, s = 1, . . . N, i, i0= 1, . . . , K, j, j0= 1, . . . , L (15) xrij +xsi0j0≤ursiji0j0+ 1 r, s = 1, . . . N, i, i0= 1, . . . , K, j, j0= 1, . . . , L (16) ursiji0j0∈ {0,1}r, s = 1, . . . N, i, i0= 1, . . . , K, j, j0= 1, . . . , L. (17) R2: The objective function of (α−SBM) is written as a linear objective subject to additional constraints by considering the positive continuous variables ϕrs, ψrs ≥0, r, s = 1, . . . , N,r6=s: min        X r,s=1,...,N r6=s |distance(Pr(x), Ps(x)) −κδrs|: s.t. (2)−(7)        = = min X r,s=1,...,N r6=s (ϕrs +ψrs) s.t.        (2)−(7) distance(Pr(x), Ps(x)) −κδrs =ϕrs −ψrs r, s = 1, . . . , N, r 6=s ϕrs ≥0r, s = 1, . . . , N, r 6=s ψrs ≥0r, s = 1, . . . , N, r 6=s R3: Constraint (7) is written as the following set of linear constraints by adding the positive continuous variables yr,r= 1, . . . , N:     1 KL X i=1,...,K j=1,...,L xrij    −ωr≤yrr= 1, . . . , N (7a)     1 KL X i=1,...,K j=1,...,L xrij    −ωr≥ −yrr= 1, . . . , N (7b) 21 X r=1,...,N yr=α(7c) yr≥0r= 1, . . . , N (7d) Single Linkage Let zrs and ηrsiji0j0be defined as follows: zrs = min i,i0=1,...,K j,j0=1,...,L |i−i0|+|j−j0|:xrij =xsi0j0= 1 ηrsiji0j0=1 if the minimum in SL(Pr(x), Ps(x)) is attained at pair (i, j), (i0, j0) 0 otherwise. Thus, (α−SBM)SL is stated by using these set of variables plus the convenient constraints to ensure that the distances between portions correspond with the Single Linkage. (α−SBM)SL = = min        X r,s=1,...,N r6=s |SL(Pr(x), Ps(x)) −κδrs|: s.t. (2)−(7)        = min X r,s=1,...,N r6=s |zrs −κδrs| s.t.                                            (2)−(7) zrs ≥(|i−i0|+|j−j0|)·ηrsiji0j0r, s = 1, . . . , N, r 6=s i, i0= 1, . . . , K, j, j0= 1,...,L zrs ≤(|i−i0|+|j−j0|) + (K+L−2)(1 −xrij ·xsi0j0)r, s = 1, . . . , N, r 6=s i, i0= 1, . . . , K, j, j0= 1,...,L X r,s=1,...,N r6=s i,i0=1,...,K j,j0=1,...,L ηrsiji0j0≥1 ηrsiji0j0≤xrij ·xsi0j0r, s = 1, . . . , N, r 6=s i, i0= 1, . . . , K, j, j0= 1,...,L ηrsiji0j0∈ {0,1}r, s = 1, . . . , N, r 6=s i, i0= 1, . . . , K, j, j0= 1,...,L. First and second added constraints ensure that variables zrs are well-defined, i.e., if the minimum is achieved in cells (i, j) and (i0, j0), then zrs is equal to the minimum distance between portions Prand Ps. Therefore, these constraints are inactive either if ηrsiji0j0= 0 or if (i, j) or (i0, j0) do not belong to Prand Ps, respectively. Third constraint is to impose that there must exist at least one pair of cells which give the minimum distance, and fourth that each pair must belong to the corresponding portion. Finally, we impose the binary requirement for ηrsiji0j0. Observe that, by applying R1-R3 reformulations, the formulation of (α−SBM)SL as an MILP, namely (α−SBM)L SL, is straightforward. 22 Complete Linkage Similar reasoning applied to Single Linkage leads to the statement of (α−SBM)CL as a MILP. Let zrs and ηrsiji0j0be defined as follows: zrs = max i,i0=1,...,K j,j0=1,...,L |i−i0|+|j−j0|:xrij =xsi0j0= 1 ηrsiji0j0=1 if the maximum in CL(Pr(x), Ps(x)) is attained at pair (i, j), (i0, j0) 0 otherwise. Thus, (α−SBM)CL is stated by using these set of variables plus the convenient constraints to ensure that the distances between portions correspond with the Complete Linkage. (α−SBM)CL = = min        X r,s=1,...,N r6=s |CL(Pr(x), Ps(x)) −κδrs|: s.t. (2)−(7)        = min X r,s=1,...,N r6=s |zrs −κδrs| s.t.                                          (2)−(7) zrs ≥(|i−i0|+|j−j0|)·xrij ·xsi0j0r, s = 1, . . . , N, r 6=s i, i0= 1, . . . , K, j, j0= 1,...,L zrs ≤(|i−i0|+|j−j0|)·ηrsiji0j0+ (K+L−2)(1 −ηrsiji0j0)r, s = 1, . . . , N, r 6=s i, i0= 1, . . . , K, j, j0= 1,...,L X r,s=1,...,N i,i0=1,...,K j,j0=1,...,L ηrsiji0j0≥1 ηrsiji0j0≤xrij ·xsi0j0r, s = 1, . . . , N, r 6=s i, i0= 1, . . . , K, j, j0= 1,...,L ηrsiji0j0∈ {0,1}r, s = 1, . . . , N, r 6=s i, i0= 1, . . . , K, j, j0= 1,...,L First added constraint ensures that for any pair of cells belonging to two different portions, the distance between those portions is greater or equal than the distance between such cells. Second one is to ensure that the distance between two portions is exactly the maximum distance between all possible pairs of cells, since ηrsiji0j0are precisely forcing that. Third constraint is to impose that there must exist at least one pair of cells which give the maximum distance, and fourth that each pair must belong to the corresponding portion. Finally, we impose the binary requirement for ηrsiji0j0. Observe that, by applying R1-R3 reformulations, the formulation of (α−SBM)CL as an MILP, namely (α−SBM)L CL, is straightforward. Average Linkage Since the statistical value associated to portion Pris represented through its area, we consider a surrogate of the expression of the average distance, (10), by approximating the number of cells 23 of Prby |Pr|=ωrKL, yielding the following expression for the Approximated Average Linkage (AvLapp) AvLapp(Pr(x), Ps(x)) = 1 ωrωsK2L2X i,i0=1,...,K j,j0=1,...,L (|i−i0|+|j−j0|)·xrij ·xsi0j0.(18) (α−SBM)AvL = = min       X r,s=1,...,N r6=s |AvLapp(Pr(x), Ps(x)) −κδrs|: s.t. (2)−(7)       By applying R1-R3 reformulations, the formulation of (α−SBM)AvL as an MILP, namely (α−SBM)L AvL, is obtained. 24