LOLIB

LOLIB is a library of sample instances for the linear ordering problem. LOLIB includes data as well as optimum solution values.

The is the old version of the library!! The current version is available at http://www.optsicom.es/lolib.

The Linear Ordering Problem

The Linear Ordering Problem is the following question. A set of n objects is given which have to be ordered in a linear sequence. For every pair i and j of objects there are coefficients c_{ij} (c_{ji}) expressing the preference for having i before j (j before i) in this sequence. The task is to find a linear sequence such that the sum of the coefficients that are compatible with this ordering is maximized.

A popular application of the Linear Ordering Problem occurs in economics as the so-called Triangulation Problem for Input-Output Matrices. Our data comes from this application.

Input-Output Matrices

-> I/O matrices: data

Optimal solutions

-> I/O matrices: optimal solutions

Warning

In previous versions of LOLIB optimal solutions were given that were not compatible with the matrices of the library. This should be fixed now. In case of problems please contact the address given below.

Note

The LOLIB problem instances are the only instances from practical applications I could obtain. They have to be considered as fairly easy. Most of them can be solved to optimality using the 3-dicycle LP relaxation and they also do not provide a real challenge for heuristic algorithms. Researchers interested in more difficult problems are referred to a collection of problem instances maintained by Rafael Marti. The instances are randomly generated and a large part of them are difficult and their optimum solutions are not yet known.

References

M.Grötschel, M.Jünger, G.Reinelt: Optimal Triangulation of Large Real World Input-Output Matrices, Statistische Hefte 25 (1984) 261-295

G.Reinelt: The Linear Ordering Problem: Algorithms and Applications, research and exposition in mathematics 8, Heldermann Verlag, Berlin 1985

Address

Gerhard Reinelt

Universität Heidelberg

Institut für Informatik

Im Neuenheimer Feld 368

D - 69120 Heidelberg

Germany

tel: ++49 - 6221 - 54 57 49

fax: ++49 - 6221 - 54 57 50

e-mail: Gerhard.Reinelt{at}Informatik.Uni-Heidelberg.de