Ruprecht-Karls-Universität Heidelberg


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

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


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.


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.


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


    Gerhard Reinelt
    Universität Heidelberg
    Institut für Informatik
    Im Neuenheimer Feld 368
    D - 69120 Heidelberg
    tel: ++49 - 6221 - 54 57 49
    fax: ++49 - 6221 - 54 57 50
    e-mail: Gerhard.Reinelt{at}

Erstellt am Wed Aug 6 16:34:28 2008