Vertex Separation Problem

Duarte A., F. Escudero L., Martí R., Mladenovic N., Pantrigo J.J. and Sánchez-Oro J. (2012)
Optsicom project, University of Valencia (Spain)

Problem Description

Let G(V,E) be an undirected graph where V (n = |V|) and E (m = |E|) are the sets of vertices and edges, respectively. A linear layout φ of the vertices of G is a bijection or mapping φ : V → {1, 2, . . . , n} in which each vertex receives a unique and different integer between 1 and n. For vertex u, let φ(u) denote its position or label in layout φ. Let L(p,φ,G) be the set of vertices in V with a position in the layout φ lower than or equal to position p. Symmetrically, let R(p,φ,G) be the set of vertices with a position in the layout φ larger than position p. In mathematical terms,

Since layouts are usually represented in a straight line, where the vertex in position 1 comes first, L(p,φ,G) can be simply called the set of left vertices with respect to position p and, R(p,φ,G) the set of the right vertices w.r.t. p.

The Cut-value at position p of layout φ, Cut(p,φ,G), is defined as the number of vertices in L(p,φ,G) with one or more adjacent vertices in R(p,φ,G), then,

where N(u) = {v ∈ V : (u, v) ∈ E}. The Vertex Separation value (VS) of layout φ is the maximum of the Cut-value among all positions in layout φ: VS(φ,G) = maxp Cut(p,φ,G).

Figure 1.a shows an illustrative example of an undirected graph G with 7 vertices and 9 edges. Figure 1.b depicts a solution (layout) φ of this graph and the Cut-value of each position p, Cut(p,φ,G). For example, Cut(1,φ,G) = 1 because L(1,φ,G) = {D} and R(1,φ,G) = {A, F, G, E, B, C} and there is one vertex in Lhaving an adjacent vertex in R. Similarly, Cut(3,φ,G) = 2 where L(3,φ,G) = {D, A, F} and R(3,φ,G) = {G, E, B, C}. The objective function value, computed as the maximum of these cut values, is VS(G,φ) = 3 whose related position is p = 4.


State of the Art Methods

The decisional version of the VSP was proved to be NP-complete for general graphs (Lengauer, 1981). It is also known that the problem remains NP-complete for planar graphs with maximum degree of three (Monien and Sudborough, 1988), as well as for chordal graphs (Gustedt, 1993), bipartite graphs (Goldberg et al. 1995), grid graphs and unit disk graphs (Diaz et al. 2001).

We can find many different graph problems that, although stated in different terms, are equivalent to the VSP in the sense that a solution to one problem provides a solution to the other one. Some of them are the Path-Width problem (Kinnersley 1992), the Interval Thickness problem (Kirousis and Papadimitriou 1985), the Node Search Number (Kirousis and Papadimitriou 1986} and the Gate Matrix Layout (Kinnersley and Langston 1994). The equivalence between these problems is a consequence of the results presented in (Fellows and Langston, 1994, Kinnersley 1992 and Kirousis and Papadimitriou 1986). For any graph G let VS(G)PW(G)IT(G)SN(G) and GML(G) be the objective function value of the optimal solution for the Vertex Separation, Path-Width, Interval Thickness, Node Search Number and Gate Matrix Layout problems, respectively. These values verify the following relations:

VS(G) = PW(G) = IT(G) = SN(G) – 1 = GML(G) + 1.

The VSP appears in the context of finding “good separators” for graphs (Lipton and Tarjan 1979) where a separator is a set of vertices or edges whose removal separates the graph into disconnected subgraphs. This optimization problem has applications in VLSI design for partitioning circuits into smaller subsystems, with a small number of components on the boundary between the subsystems (Leiserson, 1980). The decisional version of the VSP consists of finding a vertex separation value larger than a given threshold. It has applications on computer language compiler design and exponential algorithms. In compiler design, the code to be compiled can be represented as a directed acyclic graph (DAG) where the vertices represent the input values to the code as well as the values computed by the operations within the code. An edge from node u to node v in this DAG represents the fact that value u is one of the inputs to operation v. A topological ordering of the vertices of this DAG represents a valid reordering of the code, and the number of registers needed to evaluate the code in a given ordering is precisely the vertex separation number of the ordering (Bodlaender et al., 1998). The decisional version of VSP has also applications in graph theory (Fomin and Hie, 2006). Specifically, if a graph has a vertex separation value, say w, then it is possible to find the maximum independent set of G in time O(2w n). Other practical applications include Graph Drawing and Natural Language Processing (Dujmovic et al., 2008, Miller, 1956).


Instances (VSPLIB)

We have experimented with three sets of instances, totalizing 173 instances:

  • HB: We derived 73 instances from the Harwell-Boeing Sparse Matrix Collection. This collection consists of a set of standard test matrices M = Muv arising from problems in linear systems, least squares, and eigenvalue calculations from a wide variety of scientific and engineering disciplines. The graphs are derived from these matrices by considering an edge (u, v) for every element Muv = 0. From the original set we have selected the 73 graphs with n ≤ 1000. The number of vertices and edges range from 24 to 960 and from 34 to 3721, respectively.
  • Grids: This set consists of 50 matrices constructed as the Cartesian product of two paths (Raspaud et al., 2009). They are also called two dimensional meshes and the optimal solution of the VSP for squared grids is known by construction, see [7]. Specifically, the vertex separation value of a square grid of size λ × λ is λ. For this set, the vertices are arranged on a square grid with a dimension λ × λ for 5 ≤ λ ≤ 54. The number of vertices and edges range from 5 × 5 = 25 to 54 × 54 = 2916 and from 40 to 5724, respectively.
  • Trees: Let T(λ) be set of trees with minimum number of nodes and vertex separation equal to λ. As it is stated in Ellis et al. (1994), there is just one tree in T(1), namely the tree with a single edge, and another one in T(2), the tree constructed with a new node acting as root of three subtrees that belong to T(1). In general, to construct a tree with vertex separation λ + 1 it is necessary to select any three members from T(λ) and link any one node from each of these to a new node acting as the root of the new tree. The number of nodes, n(λ), of a tree in T(λ) can be obtained using the recurrence relation n(λ) = 3n(λ – 1 ) + 1 where and n(1) = 2 (see Ellis et al. (1994) for additional details). We consider 50 different trees: 15 trees in T(3), 15 trees in T(4) and 20 trees in T(5). The number of vertices and edges range from 22 to 202 and from 21 to 201, respectively.

The VSPLIB contains 173 instances:

Download Vertex Separation Instances (VSPLIB).


Computational Experience

All the algorithms were implemented in Java SE 6 and the experiments were conducted on an Intel Core i7 2600 CPU (3.4 GHz) and 4 GB RAM. We have considered the VSPLIB instances described above. The individual results for each instance can be downloaded here in Excel format.

Vertex Separation results


References

  • Bodlaender HL, Gustedt J, Telle JA. Linear-time register allocation for a fixed number of registers. Proc. of teh Symposium on Discrete Algorithms, 1998; 574–583.
  • Díaz J., Penrose M.D., Petit J., Serna M. Approximating layout problems on random geometric graphs. Algorithms 2001; 39(1):78–116.
  • Dujmovic V, Fellows MR, Kitching M, Liotta G, Mccartin K, Nishimura N, Ragde P, Rosamond FA, Whitesides S, Wood DR. On the Parameterized Complexity of Layered Graph Drawing. Algorithmica2008; 52(2):267–292.
  • Ellis J.A., Sudborough I.H., Turner J.S.. The vertex separation and search number of a graph. Journal Information and Computation, 1994; 113:50–79.
  • Fellows MR, Langston MA. On search, decision and the efficiency of polynomial-time algorithms. Journal of Computing Systems Sciences 1994; 49(3):769–779
  • Fomin FV, Hie K. Pathwidth of cubic graphs and exact algorithms. Information Processing Letters 2006; 97:191–196.
  • Goldberg P.W., Golumbic M.C., Kaplan H., Shamir R. Four strikes against physical mapping of DNA. Journal of Computing Biology 1995; 12(1):139–152.
  • Gustedt J. On the pathwidth of chordal graphs. Discrete Applied Mathemastics 1993; 45(3):233–248.
  • Kinnersley N.G. The vertex separation number of a graph equals its path-width. Information Processing Letters 1992; 42(6):345–50.
  • Kinnersley NG, Langston MA. Obstruction set isolation for the gate matrix layout problem. Discrete Applied Mathematics 1994; 54(2-3):169–213.
  • Kirousis M, Papadimitriou C.H. Interval graphs and searching. Discrete Mathematics 1985; 55(2):181–184.
  • Kirousis M, Papadimitriou C.H. Searching and pebbling. Theory of Computation Sciences 1986; 47(2):205–218.
  • Leiserson CE. Area-Efficient Graph Layouts (for VLSI). Proc. of IEEE Symposium on Foundations of Computer Science, 1980; 270–281.
  • Lengauer T. Black-White Pebbles and Graph Separation. Acta Informatica 1981; 16:465–475.
  • Lipton RJ, Tarjan RE. A separator theorem for planar graphs. SIAM Journal of Applied Mathematics1979; 36:177–189.
  • Miller GA. The Magical Number Seven, Plus or Minus Two. SIAM Journal of Applied Mathematics 1956; 13:81–97.
  • Monien B., Sudborough I.H. Min Cut is NP-Complete for Edge Weighted Treees. Theory of Computatiuon Sciences 1988;58:209–229.
  • Raspaud A., Schröder H., Sýkora O., Török L., and Vrt’o I. Antibandwidth and cyclic antibandwidth of meshes and hypercubes. Discrete Mathematics, 2009; 309:3541–3552.

Linear Ordering Problem

Martí, Reinelt and Duarte (2009)
University of Valencia (Spain), University of Heidelberg (Germany) and University Rey Juan Carlos (Spain)

Problem Description

Let Dn = (VnAn) denote the complete digraph on n nodes, where Vn is the set of nodes and An the set of arcs. A tournament T in An consists of a subset of arcs containing for every pair of nodes i and j either arc (ij) or arc (ji), but not both. T is an acyclic tournament if it does not contain any directed cycle. Obviously, an acyclic tournament induces an ordering < vi1vi2,…,vin > of the nodes (and vice versa). Node vi1 is the one with no entering arcs in Tvi2 has exactly one entering arc, etc., and vin is the node with no outgoing arc. Given arc weights wij for every pair ij in Vn, the linear ordering problem (lop) consists of finding an acyclic tournament T in An such that the sum of the weights of arcs in T is maximal, or in other words, of finding an ordering of the nodes such that the sum of the weights of the arcs compatible with this ordering is maximal.

Given an (nn) matrix C = (cij) the triangulation problem is to determine a simultaneous permutation of the rows and columns of C such that the sum of superdiagonal entries becomes as large as possible (or equivalently, the sum of subdiagonal entries is as small as possible). Note, that it does not matter if diagonal entries are taken into account or not. Obviously, by setting arc weights wij = cij for the complete digraph Dn, the triangulation problem forC can be solved as linear ordering problem Dn. Conversely,a linear odering problem for Dn can be transformed to a triangulation problem for an (nn) matrix C by setting cij = wij and the diagonal entries cii = 0 (or to arbitrary values).

The LOP can be formulated as 0/1 linear integer programming problem as follows. We use 0/1 variables xij, for (ij) inAn, stating whether arc (ij) is present in the tournament or not. Taking into account that a tournament is acyclic if and only if it does not contain any dicycle of length 3, it is easily seen that the LOP can be formulated as the 0/1-IP.


State of the Art Methods

The most relevant metaheuristics developed to solve this problem are:

  • TS: Tabu Search. Laguna et al (1999)
  • MA: Memetic Algorithm. Schiavinotto and Stützle (2004)
  • VNS: Variable Neighbourhood Search. García et al (2006)
  • SA: Simulated Annealing. Charon and Hudry (2007)
  • SS: Scatter Search. Campos et al (2001)
  • GRASP: Greedy ramdomized adaptive search procedure. Campos et al (2001)

Instances (LOLIB)

We have compiled a comprehensive set of benchmark problems including all problem instances which have so far been used for conducting computational experiments for the \lop. Furthermore we have included new instances. In their original definition, some problem instances are not in normal form. For the computations documented here, all problems have been transformed to normal form. We give a brief description of the origin and the characteristics of the groups of problems.

  • Input/Output matrices: This is a well-known set of instances that contains 50 real-world linear ordering problems generated from input-output tables from various sources (Grötschel et al 1984). They are comparatively easy for nowadays metaheuristics and are thus more of interest for economists than for the assessment of approximate methods for hard problems. The original entries in these tables were not necessarily integral, but for \LOLIB\ they were scaled to integral values. Download.
  • SGB instances: These instances are taken from the Stanford GraphBase and consist of input-output tables from sectors of the economy of the United States (Knuth 1993). The set has a total of 25 instances with 75 sectors. Download.
  • Random instances of type A: This is a set with 175 random problems that has been widely used for experiments. Problems of type I (called RandomAI), are generated from a [0,100] uniform distribution. This type of problems was proposed in Reinetl (1985) and generated in Campos et al (2001). Problems were originally generated from a [0, 25000] uniform distribution in Laguna et al (1999) and modified afterwards, sampling from a significatively narrow range ([0,100]) to make them harder to solve. Sizes are n = 100, 150 and 200 and there are 25 instances in each set giving a total of 75. We have extended this set including 25 additional instances with sizen = 500. Download. Problems of type II, which we call RandomAII, are generated by counting the number of times a sector appears in a higher position than another in a set of randomly generated permutations. This type of problems was proposed in Chanas and Kobylanski (1996) and generated in Campos el al (2001). For a problem of size nn/2 permutations are generated. There are 25 instances with sizes 100, 150 and 200, respectively. Download.
  • Random instances of type B: For these random problems, the superdiagonal entries are drawn uniformly distributed from the interval [0,U1] and the subdiagonal entries from [0,U2], where U1 >=e U2Download.
  • Instances of Mitchell and Borchers: These instances have been used by Mitchell and Borchers for their computational experiments (Mitchell and Borchers, 2000). They are random matrices where the subdiagonal entries are uniformly distributed in [0,99] and the superdiagonal entries are drawn uniformly from [0,39]. Furthermore a certain percentage of the entries was zeroed out. Download.
  • Instances of Schiavinotto and Stützle: Some further benchmark instances have been created and used by Schiavinotto and Stützle (2004). These instances were generated from the real-world input-output tables by replicating them to obtain larger problems. Thus, the distribution of numbers in these instances somehow reflects real input-output tables, but otherwise they behave more like random problems. Tha data set has been called XLOLIB, instances with n = 150 and n = 250 are available. For each original input-output instance, two instances, one of size n =150 and another one of size n = 250 were generated. Therefore this set contains 98 instances (49 with size 150 and 49 with size 250). We have removed 20 of these instances because there entries were so large that the sum of entries was not representable as 4-byte integer. Therefore, this set finally has 78 instances. Download.
  • Further special instances: We added some further problem instances that were used for experiments in some publications. EX instances were used in particular in Christof (1997) and in Christof and Reinelt (1996).econ instances were generated from the matrix usa79. They turned out not to be solvable as linear program using only 3-dicycle inequalities. atp instances were created from the results of ATP tennis tournaments in 1993/1994. Nodes correspond to a selection of players and the weight of an arc (ij) is the number of victories of player i against player j. Paley graphs have been used in Goemans and Hall (1996) to prove results about the acyclic subdigraph polytope. They are a special class of tournaments where adjacency comes from an algebraic definition. They are constructed from the members of a suitable finite field by connecting pairs of elements that differ in a quadratic residue. Download.

Computational Experience

We have performed an intensive experimentation with the best know methods (run for 2 hours) to compute the best known values for the instances. We have also reviewed related literature searching for better values than these. The final best known values for the instances can be downloaded here.

We performed a computational comparison of the state of the art methods on the instances. We have considered two different time limits in our comparative: 10 seconds (to measure the aggressiveness) and 10 minutes (to measure the robustness). Both experiments were performed in a Dual Intel Xeon at 3.06 GHz with 3.2 GiB of RAM. It can be downloaded in Excel.


References

  • Campos, V., Glover, F. Laguna, M. and Martí, R.: An experimental evaluation of a scatter search for the linear ordering problem, Journal of Global Optimizationz 21 (2001), 397–414
  • Chanas, S. and Kobylanski, P.: A new heuristic algorithm solving the linear ordering problem, Computational Optimization and Applications 6 (1996), 191–205
  • Charon, I. and Hudry, O.: A survey on the linear ordering problem for weighted or unweighted tournaments, 4OR 5 (2007), 5–60.
  • Christof, T.: Low-dimensional 0/1-polytopes and branch-and-cut, Combinatorial Optimization,Shaker, 1997
  • Christof, T. and Reinelt, G.: Combinatorial optimization and small polytopes, Top 4 (1996), 1-64
  • García, C.G., Pérez-Brito, D., Campos, V. and Martí, R.: Variable neighborhood search for the linear ordering problem, Computers and Operations Research 33 (2006),3549–3565
  • Goemans, M.X.and Hall, L.A.: The strongest facets of the acyclic subgraph polytope are unknown,Proc. of the 5th Int. IPCO Conference, LNCS 1084, Springer, 1996, 415-429
  • Grötschel, M., Jünger, M. and Reinelt, G.: A cutting plane algorithm for the linear ordering problem, Operations Research 32 (1984), 1195–1220.
  • Knuth, D.E.: The Stanford GraphBase: a platform for combinatorial computing, Addison-Wesley, 1993.
  • Laguna, M., Martí R. and Campos, V.: Intensification and diversification with elite tabu search solutions for the linear ordering problem, Computers and Operations Research 26 (1999), 1217–1230.
  • Mitchell, J.E., Borchers, B: Solving linear ordering problems, in: Frenk, H., Roos, K., Terlaky, T.Zhang, s. (eds.), High Performance Optimization, Applied Optimization Vol. 33) Kluwer, 2000, 340–366
  • Reinelt, G.: The linear ordering problem: algorithms and applications, research and exposition in mathematics 8, Heldermann, 1985.
  • Schiavinotto, T. and Stützle, T.: The linear ordering problem: Instances, search space analysis and algorithms, Journal of Mathematical Modelling and algorithms 3 2004, 367–402.

Cutwidth Minimization Problem

Martí R., Pantrigo J.J., Duarte A. and Pardo E.G. (2010)
Optsicom project, University of Valencia (Spain)

Problem Description

The Cutwidth Minimization Problem (CMP) is an NP-hard problem (Gavril 1977) and consists of finding a linear layout of a graph so that the maximum linear cut of edges (i.e., the number of edges that cut a line between consecutive vertices) is minimized. The cutwidth minimization problem can be easily described in mathematical terms. Given a graph G=(V,E) with n=|V| and m=|E|, a labeling or linear arrangement f of G assigns the integers {1,2,…,n} to the vertices in V, where each vertex receives a different label. The cutwidth of a vertex v with respect to fCWf(v), is the number of edges (u,w) ∈ Esatisfying f(u)≤f(v)<f(w). The cutwidth of the graph, CWf(G), is the maximum of the cutwidth of its vertices:

Figure 1.a shows an example of an undirected graph with 6 vertices and 7 edges. Figure 1.b shows a labeling, f, of the graph in Figure 1.a, setting the vertices in a line with the order of the labeling, as commonly represented in the CMP. In this way, since f(C)=1, vertex C comes first, followed by vertex A(f(A)=2) and so on. We represent f with the ordering (C, A, D, E, B, F) meaning that vertex C is located in the first position (label 1), vertex A is located in the second position (label 2) and so on. In Figure 1.b, the cutwidth of each vertex is represented as a dashed line with its corresponding value. For example, the cutwidth of vertex C is CWf(C) = 1, because the edge (C,B) has and endpoint in C labeled with 1 and the other endpoint in a vertex labeled with a value larger than 1. In a similar way, we can compute the cutwidth of vertex ACWf(A)=4, by counting the appropriate number of edges ((C,B), (A,B), (A,E), and (A,D)). Then, since the cutwidth of the graph GCWf(G), is the maximum of the cutwidth of all vertices in V, in this particular example we obtain CWf(G)=CWf(D)=5.

The CMP can be formulated as 0/1 linear integer programming problem as follows (Luttamaguzi et al., 2005):

where xik is a decision binary variable whose indices are i, k ∈ {1,2,…,n}. This variable specifies whether i is placed in position k in the ordering. In other words, for all xik (i, k={1, 2,…,n})they take on value 1 if and only if i occupies the position k in the ordering; otherwise xik takes on value 0. Constraints (3) and (4) ensure that each vertex is only assigned to one position and one position is only assigned to one vertex respectively. Consequently, contraints (1), (2), (3) and (4) together implies that a solution of the problem is an ordering.

The decision binary variable yikjl is defined as xik ∧ xjl, where i, j ∈ {1,2,…,n}, (vivj) ∈ E and k, l ∈ {1,2,…,n} the labels associated to vertex vi and vj respectively. In the linear formulation above this conjunction is computed with constraints (5), (6) and (7).

Constraint (8) computes for each position c in the ordering, the number of edges whose origin is placed in any position k (1 ≤ k < c) and destination in any position l (c < l ≤ n). The cutwidth problem consists of minimizing the maximum number of cutting edges in any position, c ∈{1,…,n – 1} of the labeling. Therefore, the objective function b must be larger than or equal to this quantity.


State of the Art Methods

The most relevant heuristic methods developed to solve this problem are:

  • GRASP+Path Relinking: Hybrid method that combines GRASP methodology with Path-Relinking. Andrade and Resende (2007a).
    • GRASP+Evolutionary Path Relinking: Hybrid method that combines GRASP methodology with Evolutionary Path-Relinking. Andrade and Resende (2007b).
    • Simulated Annealing : Simulated Annealing based on different constructive methods and local search procedures. Cohoon and Sahni (1987)
    • Scatter Search : Scatter Search method based on a GRASP constructive algorithm, a local search strategy based on insertion moves and voting-based combination methods. Pantrigo et al. (2012).
    • Tabu Search : A Tabu Search method used to help a Branch-and-bound algorithm. Palubeckis and Rubliauskas (2012).
    • Variable Neighbourhood Search : A new variant of the Variable Neighbourhood Search framework called Variable Formulation Search for the Cutwidth Minimization Problem. Pardo et al. (2013). (Results)

Instances (CMPLIB)

We have compiled three sets of instances for our experimentation, totalizing 252 instances. The first one, Small, was introduced in Martí et al. (2008), the second one, Grids, was introduced in Rolim et al. (1995) and the third one, Harwell-Boeing, is a subset of the public-domain Matrix Market library (available at http://math.nist.gov/MatrixMarket/data/Harwell-Boeing/). Next, it can be found a brief description of the origin and characteristics of the sets of instances:

  • Small: This data set consists of 84 graphs introduced in the context of the bandwidth reduction problem. The number of vertices ranges from 16 to 24, and the number of edges ranges from 18 to 49.
  • Grids: This data set consists of 81 matrices constructed as the Cartesian product of two paths (Raspaud et al., 2009). They are also called two dimensional meshes and, as documented in Raspaud et al. (2009), the optimal solution of the cutwidth problem for these types of instances is known by construction. For this set of instances, the vertices are arranged on a grid with a dimension width x height where width, height are selected from the set {3, 6, 9, 12, 15, 18, 21, 24, 27}.
  • Harwell-Boeing: We derived 87 instances from the Harwell-Boeing Sparse Matrix Collection. This collection consists of a set of standard test matrices M = (Mij) arising from problems in linear systems, least squares, and eigenvalue calculations from a wide variety of scientific and engineering disciplines. Graphs are derived from these matrices by considering an edge (i,j) for every element Mij ≠ 0. From the original set we have selected the 87 graphs with n ≤ 700. Their number of vertices ranges from 30 to 700 and the number of edges from 46 to 41686.

The CMPLIB contains 252 instances:

Download Cutwidth Instances (CMPLIB).


Computational Experience

We have performed an intensive experimentation with the best know methods to compute the best known values for the instances. In addition, we have performed a computational comparison of the state of the art methods on the reported instances. The experiment was performed in a Intel Core 2 Quad CPU Q 8300 with 6 GiB of RAM and Ubuntu 9.04 64 bits OS. Results and best known values for instances can be reviewed in Pantrigo et al. (2010) and Martí et al. (2010) and can be downloaded here.


References

  • Andrade, D.V. and M.G.C. Resende. GRASP with path-relinking for network migration scheduling. Proceedings of International Network Optimization Conference, 2007a.
  • Andrade, D.V. and M.G.C. Resende. GRASP with evolutionary path-relinking.Proceedings of Seventh Metaheuristics International Conference (MIC), 2007b.
  • Cohoon, J. and S. Sahni. Heuristics for the Board Permutation Problem.Journal of VLSI and Computer Systems, 2, 37- 61, 1987.
  • Gavril, F. Some NP-complete problems on graphs. In Proceedings of the 11th conference on information Sciences and Systems, 91-95, 1977.
  • Luttamaguzi, J., M. Pelsmajer, Z. Shen and B. Yang. Integer Programming Solutions for Several Optimization Problems in Graph Theory. Technical report, DIMACS, 2005.
  • Martí, R., V. Campos and E. Piñana, Branch and Bound for the Matrix Bandwidth Minimization. European Journal of Operational Research, 186:513-528, 2008.
  • Martí, R., J.J. Pantrigo, A. Duarte and E.G. Pardo. Branch and Bound for Cutwidth Minimization Problem. Computers & Operations Research. Volume 40, Issue 1, Pages 137–149, 2013
  • Palubeckis, G., D. Rubliauskas. A branch-and-bound algorithm for the minimum cut linear arrangement problem. Journal of Combinatorial Optimization. Volume 24, Issue 4, Pages 540-563, 2012
  • Pantrigo, J.J., R. Martí, A. Duarte and E.G. Pardo. Scatter Search for the Cutwidth Minimization Problem Annals of Operations Research. Volume 199, Issue 1, Pages 285-304, 2012.
  • Pardo, E.G., Mladenovic N., Pantrigo, J.J., Duarte A. Variable Formulation Search for the Cutwidth Minimization Problem. Applied Soft Computing. Volume 13, Issue 5, Pages 2242–2252, 2013.
  • Raspaud, A., H. Schröder, O. Sýkora, L. Török, and I. Vrt’o. Antibandwidth and cyclic antibandwidth of meshes and hypercubes. Discrete Mathematics. 309:3541-3552, 2009.
  • Rolim, J., O. Sýkora and I. Vrt’o. Cutwidth of the de Bruijn graph. RAIRO Informatique Théorique et Applications, 29(6):509-514, 1995.

Bandwidth Coloring Problem

Martí, Gortázar and Duarte (2009)
Optsicom project, University of Valencia (Spain)

Problem Description

The bandwidth coloring problem consists of assigning a color to each vertex of a graph, so that the absolute value of the difference between the colors of adjacent vertices is at least the value of the weight of the associated edge. This problem generalizes the classical vertex coloring problem.

Let G=(V,E) be a graph with a vertex set V (|V| = n) and an edge set E (|E|= m) with a strictly positive integer weight dij associated to each edge (ij) ∈ E. A k-coloring c of G labels each vertex i ∈ V with an integer c(i) ∈ {1, 2, …, k} (called color) in such a way that |c(i) – c(j)| ≥ dij for all (ij) ∈ E. The bandwidth coloring problem (BCP) consists of finding a k coloring with the smallest value of k. In mathematical terms:

The classical vertex coloring problem (VCP) is a particular case of the BCP in which dij=1 for all (ij) ∈ E. The BCP is therefore NP-hard since it generalizes the VCP (Garey and Johnson 1979).


State of the Art Methods

The most relevant approximated methods developed to solve this problem are:

  • FCNS: Constructive method that performs forward checking to avoid forbidden colorings. Combines a local search with a constraint propagation algorithm. Prestwich (2002)
  • Multistart: A multi-start method that first generates a sequence of nodes and then produces a solution of the BCP with a greedy algorithm. Then, it tries to improve this solution by reducing the number of colors used by one unit below the number of colors in the best solution known so far. Lim et al. (2005)
  • DSATUR+T1: A combination of evolutionary and tabu search methodologies. Malaguti and Toth (2008)
  • AMP: GRASP algorithm with an ejection chain improvement method that uses memory structures. Martí, Gortázar and Duarte (2009)

Instances (BCPLIB)

The instance set GEOM contains the instances reported in most of the previous BCP papers. GEOM consists of 33 geometric graphs generated by Michael Trick. In these graphs, points are generated in a 10,000 by 10,000 grid and are connected by an edge if they are close enough together. Edge weights are inversely proportional to the distance between nodes. This set contains three types of graphs. The GEOMn instances are sparse, the GEOMna and GEOMnb instances are denser.

These instances can be downloaded in a bundle.


Computational Experience

We performed a computational comparison of the state of the art methods. We have implemented the methods in Java SE 6 and the experiment was conducted on a Pentium 4 computer at 3 GHz with 2 GB of RAM. It can be downloaded in Excel.


References (Best Methods)

  • Garey, M.R. and D.S. Johnson (1979) Computers and Intractability. A guide to the theory of completeness, W. H. Freeman and Company, New York.
  • Prestwich, S. (2002) “Constrained bandwidth multicoloration neighborhoods” Computational symposium on graph coloring and its generalizations, Ithaca, NY, 126-133.
  • Lim, A., Y. Zhu, Q. Lou and B. Rodrigues (2005) “Heuristic Methods for Graph Coloring Problems,” The 20th Annual ACM Symposium on Applied Computing (SAC 2005, Santa Fe, New Mexico) March 13-17.
  • Malaguti, E. and P. Toth (2008) “An evolutionary approach for bandwidth multicoloring problems”,European Journal of Operational Research 189, 638-651.
  • Martí, R., F. Gortázar and A. Duarte (2009) “Heuristics for the Bandwidth Coloring Problem”,International Journal of Metaheuristics, to be published.

Vertex Bisection Problem

Herrán A., Colmenar J. M., Duarte A. (2018)
Optsicom project, University of Valencia (Spain)

Problem Description

The Vertex Bisection Problem (VBP) belongs to the family of well-known graph partitioning problems, where the main goal is to find a partition of the vertices maximizing or minimizing a given objective function. In particular, VBP consists of dividing a graph into two parts B and B’ with the same number of vertices, or differing in one if the number of vertices is odd, such as the vertex width (VW), defined as the number of vertices in B with at least one adjacent in B’, is minimized. As example, Figure (a) shows a connected undirected graph with 10 vertices and 13 edges. Figures (b) and (c) show two feasible solutions for the VBP with a vertex width of 2 and 3 respectively.

More formally, given a graph G = (V,E) where V is the set of vertices, |V| = n, and E is the set of edges, a feasible solution of the VBP is defined by two subsets of nodes B and B’ (with B ∩ B’ = ∅ and B ∪ B’ = V) where the size of each subset verifies that B = ⌊n/2⌋ and B’ = n – ⌊n/2⌋, respectively. Hence, given a solution S = (B, B’), its vertex width is computed as:

Let 𝒮 be the whole set of feasible partitions of V according to the aforementioned constraints. Therefore, the VBP consists of finding the solution S* ∈ 𝒮 that minimizes the vertex width.


State of the Art Methods

This problem has been dealt with from both, exact and heuristic perspectives. Among the exact methods, the most relevant works are:

  • B&B: Branch & Bound algorithm for the two proposed integer-linear programming models. Fraire (2014).
  • QCQP: Quadratically constrained quadratic program for a different integer-linear programming model than the proposed in (Fraire, 2014). Jain (2016a).
  • B&B: Branch & Bound algorithm that incorporates a greedy heuristic to produce an upper bound for the cost of the solutions. Jain (2016b).

The most relevant heuristic methods developed to solve this problem are:

  • CH: Different constructive heuristics. Castillo-Garcia (2015).
  • GA: Genetic algorithm. Huacuja (2016).
  • MA: Memetic algorithm. Pallavi (2016).

Instances

Our experimental experience is developed on several sets of instances with different number of vertices, edges, and densities. These sets contain Small-Full (84), Trees (15), Grids (5) and HB (4) instances used in Fraire (2014), and the Small (23), Harwell-Boeing (36) and Hypercubes (8) instances used in (Pallavi, 2016).

We stored the resulting 175 instances as a library that we called VBP_LIB:

Download VBP_LIB instances.


Computational Experience

All the algorithms were implemented in C++ and the experiments were conducted on an Intel i7 6500U processor running at 2.5 GHz with 8 Gb of RAM using Windows 10. We have considered the VBP_LIB instances described above. The individual results for each instance can be downloaded here in Excel format.

Vertex Bisection problem results


References

  • H. Fraire, J. Terán-Villanueva, N.C. García, J. Gonzalez-Barbosa, E.R. del Angel, Y. Gómez-Rojas. Exact Methods for the Vertex Bisection Problem. Springer International Publishing (2014), pp. 567–577.
  • P. Jain, G. Saran, K. Srivastava. A new integer linear programming and quadratically constrained quadratic programming formulation for vertex bisection minimization problem. J. Autom. Mobile Rob. Intell. Syst. 10(1) (2016a), pp. 69–73.
  • P. Jain, G. Saran, K. Srivastava. Branch and bound algorithm for vertex bisection minimization problem. In: R.K. Choudhary, J.K. Mandal, N. Auluck, H.A. Nagarajaram (Eds.), Advanced Computing and Communication Technologies, Proceedings of the 9th ICACCT (2015), Springer Singapore, Singapore (2016b), pp. 17–23.
  • N. Castillo-García, H.J.F. Huacuja, J.A.M. Flores, R.A.P. Rangel, J.J.G. Barbosa, J.M.C. Valadez. Comparative Study on Constructive Heuristics for the Vertex Separation Problem. Springer International Publishing, Cham (2015), pp. 465–474.
  • H.J.F. Huacuja, N. Castillo-García. Optimization of the vertex separation problem with genetic algorithms. IGI Global (2016), pp. 13–31.
  • J. Pallavi, G. Saran, K. Srivastava. On minimizing vertex bisection using a memetic algorithm. Inf. Sci. 369 (2016), pp. 765–787.

Maximally Diverse Grouping Problem

Gallego, Laguna, Martí and Duarte (2011)
Optsicom project, University of Valencia (Spain)

Problem Description

The maximally diverse grouping problem (MDGP) consists of grouping a set of M elements into Gmutually disjoint groups in such a way that the diversity among the elements in each group is maximized. The diversity among the elements in a group is calculated as the sum of the individual distance between each pair of elements, where the notion of distance depends on the specific application context. The objective of the problem is to maximize the overall diversity, i.e., the sum of the diversity of all groups. Feo and Khellaf (1990) proved that the MDGP is NP-hard.

In order to formulate the MDGP in mathematical terms, we assume that each element can be represented by a set of attributes. Let sik be the state or value of the kth attribute element, where k= 1,…,K and i=1,…,M. Then, the distance dij between element i and j may be simply defined by the Eucliden calculation:

We have identified two variants of the MDGP. The first one (MDGP1) is the better known and forces all groups to have the same number of elements, with S=M/G. The second variant (MDGP2) allows the size Sg of each group g to be in the interval [ag,bg], where ag <= bg for g = 1,…,G. Clearly, MDGP1 is a special case of the MDGP2 for which ag = bg for all g.

Both variants can be formulated as quadratic integer programs with binary variables xig that take the value of 1 if element i is in group g and 0 otherwise. A quadratic integer programming formulation of the MDGP1 is:

The objective function adds the distance of all pairs of elements that belong to the same group. The first set of constraints forces the assignment of each element to a group. The second set of constraints forces the size of all groups to be equal to S. In the more general case, MDGP2, the second set of constraints is replaced with:

State of the Art Methods

The most relevant approximated methods developed to solve this problem are:

  • LCW: Multistart algorithm composed by a random constructive and an improvement method. The improvement method is developed as a modified version of LC method due to Lofti and Cerveny (1991). Weitz and Lakshminarayanan (1998)
  • LSGA: Hybrid genetic algorithm that combines a genetic algorithm and a local search procedure. The genetic aspect of LSGA is based on the encoding scheme for grouping problems proposed by Falkenauer (1998). The local search within LSGA implements a best improvement strategy based on exchanging elements between groups. Fan et al. (2011)
  • T‐LCW: Multistart algorithm composed by a greedy constructive (GC) and T-LCW, a tabu version of LCW improvement method. Gallego et al. (2011)
  • SO: Multistart algorithm composed by a greedy constructive (GC) and strategic oscillation improvement based on T-LCW. Gallego et al. (2011)

A Java 6 implementation of all state of the art methods is available for download as binary. For usage instructions execute .jar file with the command:

java -jar mdgp_jors_2011.jar

Please make sure that you have Java 6 SE installed in your system.

Instances (MDGPLIB)

We have compiled a comprehensive set of 480 benchmark instances representative of the collections previously used for computational experiments in the MDGP. We call this benchmark MDPGLIB. Furthermore we have included new hard instances. A brief description of the origin and the characteristics of the set of instances follows:

  • RanReal: This set consists of 160 M x M matrices in which the distance values dij are real numbers generated using a Uniform distribution U(0,100). The number of elements M, the number of groups Gand the limits of each group ag and bg are shown in Table 1. There are 20 instances for each combination of parameters (i.e., each row in Table 1), 10 for instances with equal group size (EGS) and 10 for instances with different group size (DGS). For the 10 instances in EGS, the group size is equal for all instances and is calculated as ag = ag = M / G. For the 10 instances in DGS, the limits of each group (ag and bg) for each instance are generated randomly in the predefined interval. That is, the value of ag is generated in the interval [agmin,agmax] and the value of bg is generated in the interval [bgmin,bgmax]. This data set was introduced by Fan et al. (2011) with M ranging from 10 to 240. The larger instances with M=480 and M=960 had been generated for inclusion in MDGPLIB.

Table 1. Summary of parameters to generate problem instances

  • RanInt: This set has the same structure and size as RanReal (shown in Table 1) but distances are generated with an integer Uniform distribution.
  • Geo: This set follows the same structure and size as the previous two, however, values are calculated as Euclidean distances between pair of points with coordinates randomly generated in [0,10]. The number of coordinates for each point is generated randomly in the 2 to 21 range.

Download MDGPLIB. The format of the instances is described here

Computational Experience

We have performed a computational comparison of the state of the art methods on 240 instances (5 EGS instances and 5 DGS instances for M=10 to 960). All methods were stopped using the same time limit, which varied according to problem size, as specified in Table 2.

Table 2. CPU time limits

In this experiment we compute for each instance and each method the relative deviation Dev (in percent) between the best solution value, Value, obtained with the method and the best known value of this instance, BestValue. For each method, we also report the number of instances #Best for which the method obtains the best value.

All algorithms were implemented in Java 6 and the experiment was performed in a Intel Core 2 Quad CPU Q 8300 with 6 GiB of RAM and Ubuntu 9.04 64 bits OS.

Download the raw data used to calculate this table.

References

  • Fan, Z. P., Y. Chen, J. Ma and S. Zeng (2011) “A hybrid genetic algorithmic approach to the maximally diverse grouping problem”, Journal of the Operational Research Society, vol. 62, pp. 92‐99.
  • Feo, T. and M. Khellaf (1990) “A class of bounded approximation algorithms for graph partitioning”, Networks, vol. 20, pp. 181‐195.
  • Lotfi V. and R. Cerveny (1991) “A final exam scheduling package”, Journal of the Operational Research Society, vol. 42, pp. 205‐216.
  • Weitz, R. R. and S. Lakshminarayanan (1998) “An empirical comparison of heuristic methods for creating maximally diverse groups”, Journal of the Operational Research Society, vol. 49, no. 6, pp. 635‐646.
  • Gallego, M., Laguna, M., Martí, R. and Duarte, A. (2011) “Tabu Search with Strategic Oscillation for the Maximally Diverse Grouping Problem”, Journal of the Operational Research Society. Accepted. Download.

Maximum Diversity Problem

Martí, Gallego and Duarte (2010)
Optsicom project, University of Valencia (Spain)

Problem Description

The maximum diversity problem (MDP) consists of selecting a subset of m elements from a set of nelements in such a way that the sum of the distances between the chosen elements is maximized. The definition of distance between elements is customized to specific applications. In most applications, it is assumed that each element can be represented by a set of attributes. Let sik be the state or value of the kth attribute of element i, where k = 1, …, K. Then the distance between elements i and j may be defined as:

In this case, dij is simply the Euclidean distance between i and j. The distance values are then used to formulate the MDP as a quadratic binary problem, where variable xi takes the value 1 if element i is selected and 0 otherwise, i = 1, …, n:

Kuo, Glover and Dhir (1993) use this formulation to show that the clique problem (which is known to be NP-complete) is reducible to the MDP.


State of the Art Methods

The most relevant approximated methods developed to solve this problem, categorized by methodology, are:

  • GRASP based methdos
    • GRASP_D2+I_LS: Constructive method coupled with a first-improvement local search. Duarte and Martí (2007).
    • GRASP+PR: Hybrid method that combines GRASP methodology with Path-Relinking. Silva et al. (2007).
  • Local search based methods
    • ITS: Iterated Tabu Search that alternates tabu search with perturbation procedures. Palubeckis (2007).
    • A_VNS: Variable neighborhood search method with a basic tabu search improvement method. Aringhieri and Cordone (2006).
  • Population based methods
    • G_SS: Scatter Search algorithm with memory structures. Gallego et al. (2009).
    • MA: Memetic Algorithm that combines a population based approach with a local search approach. Katayama and Narihisa (2005).

Instances (MDPLIB)

We have compiled a comprehensive set of benchmark instances representative of the collections previously used for computational experiments in the MDP. We call this benchmark MDPLIB. Furthermore we have included new hard instances. A brief description of the origin and the characteristics of the set of instances follows:

  • SOM: This data set consists of 70 matrices with random numbers between 0 and 9 generated from an integer uniform distribution.
    • SOM-a: These 50 instances were generated by Martí et al. (2010) with a generator developed by Silva et al. (2004). The instance sizes are such that for n = 25, m = 2 and 7; for n = 50, m = 5 and 15; for n = 100, m = 10 and 30; for n = 125, m = 12 and 37; and for n = 150, m = 15 and 45.
    • SOM-b: These 20 instances were generated by Silva et al. (2004) and used in most of the previous papers (see for example Aringhieri et al. 2008). The instance sizes are such that for n = 100, m = 10, 20, 30 and 40; for n = 200, m = 20, 40, 60 and 80; for n = 300, m = 30, 60, 90 and 120; for n= 400, m = 40, 80, 120, and 160; and for n = 500, m = 50, 100, 150 and 200.
  • GKD: This data set consists of 145 matrices for which the values were calculated as the Euclidean distances from randomly generated points with coordinates in the 0 to 10 range.
    • GKD-a: Glover et al. (1998) introduced these 75 instances in which the number of coordinates for each point is generated randomly in the 2 to 21 range. The instance sizes are such that for n = 10, m = 2, 3, 4, 6 and 8; for n = 15, m = 3, 4, 6, 9 and 12; and for n = 30, m = 6, 9, 12, 18 and 24.
    • GKD-b: Martí et al. (2010) generated these 50 matrices for which the number of coordinates for each point is generated randomly in the 2 to 21 range and the instance sizes are such that for n = 25, m = 2 and 7; for n = 50, m = 5 and 15; for n = 100, m = 10 and 30; for n = 125, m = 12 and 37; and for n = 150, m = 15 and 45.
    • GKD-c: Duarte and Martí (2007) generated these 20 matrices with 10 coordinates for each point and n = 500 and m = 50.
  • MDG: This data set consists of 100 matrices with real numbers randomly selected between 0 and 10 from a uniform distribution.
    • MDG-a: Duarte and Martí (2007) generated these 40 matrices, 20 of them with n = 500 and m = 50 and the other 20 with n = 2000 and m = 200. These instances were used in Palubeckis (2007).
    • MDG-b: This data set consists of 40 matrices generated by Duarte and Martí (2007). 20 of them have n = 500 and m = 50, and the other 20 have n = 2000 and m = 200. These instances were used in Gallego et al. (2009) and Palubeckis (2007).
    • MDG-c: This is a new data set with 20 matrices with n = 3000 and m ∈ {300, 400, 500, 600}. These are the largest instances reported of the MDPLIB. They are similar to those used in Palubeckis (2007).

The MDPLIB contains 315 instances and the best known values for the largest ones (SOM-b, GKD-c, MDG-a, MDG-b and MDG-c). They have been obtained by running G_SS and ITS for 2 hours of CPU time (in each instance) in a workstation Intel Core 2 Quad CPU Q 8300 with 6 GiB of RAM and Ubuntu 9.04 64 bits OS.

Download MDPLIB.


Computational Experience

We have performed a computational comparison of the state of the art methods on several of these the instances. We have considered a time limit in our comparative of 10 minutes per instance. In this experiment we compute for each instance and each method the relative deviation Dev (in percent) between the best solution value, Value, obtained with the method and the best known value of this instance, BestValue. For each method, we also report the number of instances #Best for which the method obtains the best value.

The experiment was performed in a Intel Core 2 Quad CPU Q 8300 with 6 GiB of RAM and Ubuntu 9.04 64 bits OS.


References

  • R. Aringhieri, R. Cordone, and Y. Melzani. Tabu search vs. grasp for the maximum diversity problem. 4OR: A Quarterly Journal of Operations Research, 6(1):45–60, 2008.
  • R. Aringhieri and R. Cordone. Better and faster solutions for the maximum diversity problem. Technical report, Universit degli Studi di Milano, Polo Didattico e di Ricerca di Crema, 2006.
  • A. Duarte and R. Martí. Tabu search and grasp for the maximum diversity problem. European Journal of Operational Research, 178:71–84, 2007.
  • M. Gallego, A. Duarte, M. Laguna, and R. Martí. Hybrid heuristics for the maximum diversity problem. Computational Optimization and Applications, 44(3):411, 2009.
  • F. Glover, C.C. Kuo and K.S. Dhir. Heuristic algorithms for the maximum diversity problem. Journal of Information and Optimization Sciences, 19(1):109–132, 1998.
  • K. Katayama and H. Narihisa. An evolutionary approach for the maximum diversity problem. In W. Hart, N. Krasnogor, and J.E. Smith, editors, Recent advances in memetic algorithms, volume 166, pages 31–47. Springer, Berlin, 2005.
  • C.C. Kuo, F. Glover, and K. S. Dhir. Analyzing and Modeling the Maximum Diversity Problem by Zero-One programming. Decision Sciences, 24(6):1171–1185, 1993.
  • R. Martí, M. Gallego, and A. Duarte. A branch and bound algorithm for the maximum diversity problem. European Journal of Operational Research, 200(1):36–44, 2010.
  • G. Palubeckis. Iterated tabu search for the maximum diversity problem. Applied Mathematics and Computation, 189:371383, 2007.
  • G.C. Silva, L.S. Ochi, and S.L. Martins. Experimental Comparison of Greedy Randomized Adaptive Search Procedures for the Maximum Diversity Problem. In Experimental and Efficient Algorithms, volume 3059 of Lecture Notes in Computer Science, pages 498–512. Springer Berlin / Heidelberg, 2004.
  • G.C. Silva, M.R.Q. Andrade, L.S. Ochi, S.L. Martins, and A. Plastino. New heuristics for the maximum diversity problem. Journal of Heuristics, 13(4):315–336, 2007.

Min-Max Arc Crossing

T. Pastore, A. Martinez-Gavara, A. Napoletano, P. Festa, and R. Martí (2018)
Optsicom project, University of Valencia (Spain)

Problem Description

The crossing minimization problem in hierarchical digraphs has received a lot of attention. Even the problem in bipartite graphs has been extensively studied for more than 40 years, beginning with the Relative Degree Algorithm introduced in Carpano [6]. Early heuristics were based on simple ordering rules, reflecting the goal of researchers and practitioners of quickly obtaining solutions of reasonable quality. However, the field of optimization has recently evolved introducing complex methods, both in exact and heuristic domains. The crossing problem has benefited from these techniques, and advanced solution strategies have been proposed in the last 20 years to solve it.

We focus on a variant of the crossing problem recently introduced in Stallmann (2012). In particular, this author identified some applications in the context of VLSI circuits design in which it is more appropriate to minimize the maximum number of crossings over all edges (min-max) rather than the sum of the edge crossings over all the graph (min-sum). This application motivated the work by Stallman, originally called the bottleneck crossing minimization, where a heuristic algorithm is proposed to minimize the maximum number of crossings among all edges. More recently, Martí et al. (2018) applied a metaheuristic algorithm to solve the problem defined in Stallman’s work, which they called the max-min crossing problem. Remarkably, the solution of the min-max problem is also useful in general graph drawing softwares, where zooming highlights a specific area of the graph where it is then desirable to have a low number of crossings.


State of the Art Methods

Two previous heuristic algorithms were developed to solve this problem:

  • MCE: method based on the sifting principle, which performs passes over the layers of the graph, trying to relocate the endpoints of edges with an elevated number of crossing, until no further improvement can be found. Stallmann (2012)
  • SO: iterated greedy heuristic based on the Strategic Oscillation methodology. This procedure alternates three steps: constructive phase, neighborhood search and destructive phase, in which tries to improve the number of crossing of edges whose cost is close to the maximum (near critical edges). Martí et al. (2018).

Instances

All the instances employed in the experimentation were generated using the generator provided by Stallmann (2012). The benchmark set is made up by a total of 149 networks of heterogeneous size, with graph densities ranging from low values, with a minimum density of 1.5, to high values, with a maximum density of 14.5.

There is 1 folder in the MinMaxGDPlib.zip file: with 60 instances. The file format follows:

The first line has the following fields separed with spaces:

  • n: Integer indicating the total number of vertices in the graph
  • m: Integer indicating the total number of edges in the graph
  • k: Integer indicating the total number of layers in the graph

Starting from the second line, the number of nodes in each layer are reported. The nodes are numbered sequentially. Each of the following lines represent an edge among two adjacent layers of the graph, in the format: starting_node end_node. For example:6 4 2 3 3 1 5 2 4 3 6 3 5

is a graph with six total nodes, divided in two layers of three nodes each. The total number of edges is four, and the vertices in the first layer are labeled as 1 2 3, while the vertices in the second layer are labeled 4 5 6. the connections are between node 1 and node 5, node 2 and node 4, node 3 and 6, and node 3 and 5.

Download Min-Max Arc Crossing Instances (MinMaxGDPlib).


Computational Experience

The computational experiments described in this section were performed to assess the performances of the Tabu Search implementation proposed in this paper. The comparative testing can be divided in a two-round competitive experimentation: in the first round of experiments, we investigate the comparison between CPLEX (v12.8), MCE and our Tabu Search, while solving small-sized instances with low density. In the second round of experiments we undertake the comparison of the three heuristic methods (MCE, SO and Tabu Search), while drawing more complex networks with higher graph densities.

Min-Max Arc Crossing results


References

  • Carpano (1980). Automatic display of hierarchized graphs for computer-aided decision analysis. IEEE Transactions on Systems, Man, and Cybernetics, 10(11):705-715.
  • Martí, R., V. Campos, A. Hoff, and J. Peiró (2018). Heuristics for the min-max arc crossing problem in graphs. Expert Systems with Applications 109, 100-113.
  • Stallmann, M.F. (2012). A heuristic for bottleneck crossing minimization and its performance on general crossing minimization: Hypothesis and experimental study. ACM Journal of Experimental Algorithms, 17(1): 1-30.

Dynamic Bipartite Graph Drawing Problem

Martí R., Martínez-Gavara, A., Sánchez-Oro J., and Duarte A. (2017)
Optsicom project, University of Valencia (Spain)

Problem Description

Drawings of graphs have many applications and they are nowadays well-established tools in computer science in general, and optimization in particular. Project scheduling is one of the many areas in which representation of graphs constitutes an important instrument. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic in this context, where we seek to preserve the layout of a graph over successive drawings. In this paper, we target the edge crossing reduction in the context of incremental graph drawing. Specifically, we apply a mathematical programming formulation and several heuristic methods based on the tabu search methodology to solve it. In line with the previous paper on this topic, we consider bipartite graphs in our experimentation. The extensive computational experiments with more than 1,000 instances show the superiority of our proposals in both, quality and computing time.


Instances (DBDPLIB)

We employed two sets of instances in our experimentation. The first one contains 120 instances generated according to Martí and Estruch (2001), while the second one has 1000 instances and of instances based on the original number of vertices in each layer, (n1, n2), and the graph 12 was proposed by Stallmann et al. (2001). In line with previous papers, we generated the first set density d in the interval [0.065, 0.175]. Additionally, as in Martí and Estruch (2001), the instances are incremented adding vertices and edges up to pre-established numbers. These numbers are calculated as a percentage δ of the quantities in the original graph (|IVi| = δ|Vi| for each i=1,2, and |IE|=δ|E|. The second set contains 1000 instances obtained with the generator described in Stallmann et al. (2001), which is publicly available. The size of the first layer is in the range [10, 377], while the size of second layer ranges from 10 to 190 nodes. The number of edges is in the range [20, 950]. These instances are bipartite graphs, and we convert them in incremental bipartite graphs by considering a percentage of their nodes as the new nodes added to the original graph. In this way, we kept the structure and density of the instance. In particular, for each original instance we have generated three new instances obtained by selecting as new nodes the 10%, 20%, and 30% percent of the original nodes.

The DBDPLIB contains 1120 instances:

Download DBDP instances (DBDPLIB).


Computational Experience

The computational experiments described in this section were performed to test the effectiveness and efficiency of the procedures discussed above. The previous GRASP method, called prev_GRASP, by Martí and Estruch (2001), and our new procedures were implemented in Java SE 8, and the experiments were conducted on a computer with a 2.8 GHz Intel Core i7 processor with 16 GB of RAM. In particular, we report the results obtained with our constructive method, tabu search, and path relinking post-processing. Additionally, the mathematical programming formulation described in Section 2 was solved with Gurobi

Dynamic Bipartite Drawing Problem results

Uncapacitated r-Allocation p-Hub Median Problem

Peiró J., Corberán A., Martí R. (2013)
Optsicom project, University of Valencia (Spain)

Problem Description

The Uncapactitated r-Allocation p-Hub Median Problem (UrApHMP) is a variant of the classical p-hub problem. Hub location problems arise when given a set of nodes with pairwise traffic demands, we have to choose p of them as hub locations and route all the traffic through these hubs at a minimum cost. For each pair of nodes i and j, there is a traffic tij that needs to be transported. It is generally assumed that direct transportation between non-hub nodes is not possible, and the tij traffic travels on a path i→hi→hj→j, where hi and hj are hubs assigned to i and j, respectively.

Recently, Yaman (2011) proposed the UrApHMP, a very interesting variant of this classical location problem in which each node can be connected to at most r of the p hubs. The motivation of this variant comes from the fact that the single allocation version, in which a node is connected (assigned) to a single hub is too restricted for real-world situations, while the multiple allocation variant, where each node can use any of the p hubs to route its traffic, results in high fixed costs and complicated networks. The r-allocation p-hub problem, being r≤p, generalizes both versions of the p-hub median problem. When r=1 we are at the single allocation version, whereas if r=p, we have the multiple allocation version.

In mathematical terms, given a network with a set of nodes N and a set of arcs A, let tij be the amount of traffic to be routed from node i to node j, i.e., through the arc (i,j), and let dij be its associated unit routing cost. The UrApHMP is then formulated (Yaman, 2011) in terms of the following variables: Given a node kzkk=1 if the node is a hub (i.e., if a hub is set or located at this node), and zkk=0 otherwise. Given a non-hub node i and a hub kzik=1 if node i is assigned or allocated to node k, and 0 otherwise. Finally, fijkl is the proportion of the traffic tij from node i to node j that travels along the path i→k→l→j, where k and l are hubs. With these variables, the problem can be formulated as follows:

The p-hub median problem belongs to the class of NP-hard problems. Even when the set of hubs is given, the sub-problem of optimal allocation of non-hub nodes to hubs is also NP-hard (Love, Morris and Wesolowski, 1988).


State of the Art Methods

A GRASP in which we consider three local search procedures. We also implement a filtering mechanism to discard low-quality constructions to help saving running time for large instances.

A scatter search algorithm in which we consider seven diversification generation methods, and path-relinking as an extension of the classical combination method.


Instances

We have tested our algorithms on three sets of instances:

  1. The CAB (Civil Aviation Board) data set. It is based on airline passenger flows between some important cities in the United States. It consists of a data file, presented by O’Kelly in 1987, with the distances and flows of a 25 nodes graph. From this original file, 75 instances with 25 nodes and p= 1,…, 5, and r= 1,…, p have been generated by several authors. The following parameter values have been widely used: χ=1,δ=1, and α= 0.2, 0.4, 0.6, 0.8, and 1.
  2. The AP (Australian Post) data set. It is based on real data from the Australian postal service and was presented by Ernst and Krishnamoorthy in 1996. The size of the original data file is 200 nodes. Smaller instances can be obtained using a code from ORLIB. As with CAB, many authors have generated different instances from the original file. We have extended this set of instances by generating 360 instances with n= 40, 50, 70, 75, 80, 85, 90, 95, 100, 150 and 200 nodes. For those instances with 40≤n≤50, p ranges from 1 to 5. For those with 70≤n≤95, p ranges from 1 to 8, and for those with 100≤n≤200, p takes values between 1 and 20. In all these cases, r<∈{1,…,p}. According with previous articles, cost parameter values are χ=3, α=0.75 and δ=2. Regarding the flows between nodes, these instances do not have symmetric flows (i.e., for a given pair of nodes iand j,tij is not necessarily equal to tji). Moreover, flows from one node to itself can be positive (i.e., tiican be strictly positive for a given i).
  3. The USA423 data set. This is a new family of instances that we introduce here based on real airline data. It consists of a data file concerning 423 cities in the United States, where real distances and passenger flows for an accumulated 3 months period are considered. From the original data, 30 instances have been generated with p∈{3,4,5,6,7} and 2≤r≤p-1. For each combination of parameters p and r, two different values for χ,α,δ have been used: 0.1, 0.07, 0.09, and 0.09, 0.075, 0.08, respectively.

You can download the instances here.


Computational Experience

We performed extensive computational experiments with 465 instances. The best values for the hardest instances can be downloaded here.


References

  • Aiex, R. M., M. G. C. Resende, and C. C. Ribeiro. 2007. TTT plots: A perl program to create time-to-target plots. Optimization Letters 1, no. 4: 355-366.
  • Alumur, S., and Kara, B. Y. Network hub location problems: The state of the art. European Journal of Operational Research 190, 1 (2008), 1-21.
  • Campbell, J. F. 1994. Integer programming formulations of discrete hub location problems. European Journal of Operational Research 72, no. 2: 387-405.
  • Campbell, J. F. and M. E. O’Kelly. 2012. Twenty-five years of hub location research. Transportation Science 46, no. 2: 153-169.
  • Contreras, I., and Fernández, E. General network design: A unified view of combined location and network design problems. European Journal of Operational Research 219, 3 (2012), 680-697.
  • Correia, I., Nickel, S., and Saldanha da Gama, F. Hub and spoke network design with single-assignment, capacity decisions and balancing requirements. Applied Mathematical Modelling 35, 10 (2011), 4841-4851.
  • Díaz, J. A., and Fernández, E. Hybrid scatter search and path relinking for the capacitated p-median problem. European Journal of Operational Research 169, 2 (2006), 570-585.
  • Ernst, A. and M. Krishnamoorthy. 1996. Efficient algorithms for the uncapacitated single allocation p-hub median problem. Location Science 4, no. 3: 139-154.
  • Farahani, R. Z., Hekmatfar, M., Arabani, A. B., and Nikbakhsh, E. Hub location problems: A review of models, classification, solution techniques, and applications. Computers & Industrial Engineering 64, 4 (2013), 1096-1109.
  • Feo, T. A. and M. G. C. Resende. 1989. A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters 8, no. 2: 67-71.
  • Feo, T. A. and M. G. C. Resende. 1995. Greedy randomized adaptive search procedures. Journal of Global Optimization 6, no. 2: 109-133.
  • Festa, P. and M. G. C. Resende. 2011. GRASP: Basic components and enhancements. Telecommunication Systems 46, no. 3: 253-271.
  • García, S., M. Landete, and A. Marín. 2012. New formulation and a branch-and-cut algorithm for the multiple allocation p-hub median problem. European Journal of Operational Research 220, no. 1: 48-57.
  • Gelareh, S. and S. Nickel. 2011. Hub location problems in transportation networks. Transportation Research Part E: Logistics and Transportation Review 47, no. 6: 1092-1111.
  • Glover, F. A template for scatter search and path relinking. In Artificial Evolution, J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer, and D. Snyers, Eds., Lecture Notes in Computer Science 1363, Springer (1998), pp. 13-54.
  • Glover, F. Tabu search and adaptive memory programing – advances, applications and challenges. In Interfaces in Computer Science and Operations Research (1996), Kluwer, pp. 1-75.
  • Glover, F., Laguna, M., and Martí, R. Fundamentals of scatter search and path relinking. Control and Cybernetics 29, 3 (2000), 652-684.
  • Ilić, A., D. Urosević, J. Brimberg, and N. Mladenović. 2010. A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem. European Journal of Operational Research 206, no. 2: 289-300.
  • Kratica, J., Z. Stanimirović, D. Tosić, and V. Filipović. 2007. Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem. European Journal of Operational Research 182, no. 1: 15-28.
  • Labbé M., and Yaman, H. Solving the hub location problem in a star-star network. Networks 51, 1 (2008), 19-33.
  • Laguna, M. and R. Martí. 1999. GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing 11, no. 1: 44-52.
  • Laguna, M., and Martí, R. Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers (2002).
  • Love, R.F., Morris, J.G., and Wesolowski, G.O. 1988. Facilities location: Models and methods. Elsevier Science Publishing Co., New York.
  • Martí, R., Laguna, M., and Glover, F. Principles of scatter search. European Journal of Operational Research 169, 2 (2006), 359-372.
  • Milanović, M. 2010. A new evolutionary based approach for solving the uncapacitated multiple allocation p-hub median problem. In Soft Computing in Industrial Applications, AISC 75 (X. Z. Gao et al., eds.). Springer-Verlag, Berlin, pp: 81-88.
  • O’Kelly, M. E. 1987. A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research 32, no. 3: 393-404.
  • Pacheco, J. A., and Casado, S. Solving two location models with few facilities by using a hybrid heuristic: A real health resources case. Computers & Operations Research 32, 12 (2005), 3075-3091.
  • Resende, M. G. C., Ribeiro, C. C., Glover, F., and Martí, R. Scatter search and path-relinking: Fundamentals, advances, and applications. In Handbook of Metaheuristics, M. Gendreau and J. Y. Potvin, Eds., International Series in Operations Research & Management Science 146. Springer (2010), pp. 87-107.
  • Resende, M. G. C., and Werneck, R. F. A hybrid heuristic for the p-median problem. Journal of Heuristics 10, 1 (2004), 59-88.
  • Ribeiro, C. C., and Resende, M. G. C. Path-relinking intensification methods for stochastic local search algorithms. Journal of Heuristics 18, 2 (2012), 193-214.
  • Yaman, H. 2011. Allocation strategies in hub networks. European Journal of Operational Research 211, no. 3: 442-451.