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 D_n = (V_n, A_n) denote the complete digraph on n nodes, where V_n is the set of nodes and A_n the set of arcs. A tournament T in A_n consists of a subset of arcs containing for every pair of nodes i and j either arc (i, j) or arc (j, i), but not both. T is an acyclic tournament if it does not contain any directed cycle. Obviously, an acyclic tournament induces an ordering < v_i1, v_i2,…,v_in > of the nodes (and vice versa). Node v_i1 is the one with no entering arcs in T, v_i2 has exactly one entering arc, etc., and v_in is the node with no outgoing arc. Given arc weights w_ij for every pair i, j in V_n, the linear ordering problem (lop) consists of finding an acyclic tournament T in A_n 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 (n, n) matrix C = (c_ij) 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 w_ij = c_ij for the complete digraph D_n, the triangulation problem forC can be solved as linear ordering problem D_n. Conversely,a linear odering problem for D_n can be transformed to a triangulation problem for an (n, n) matrix C by setting c_ij = w_ij and the diagonal entries c_ii = 0 (or to arbitrary values).

The LOP can be formulated as 0/1 linear integer programming problem as follows. We use 0/1 variables x_ij, for (i, j) inA_n, stating whether arc (i, j) 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 n, n/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,U₁] and the subdiagonal entries from [0,U₂], where U₁ >=e U₂. Download.
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 (i, j) 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.