Generating linear ordering problems

Downloading the generator

You can find here pointers to FORTRAN files that can be used to generate random degenerate linear ordering problems. In particular, these routines can be used to generate the thirty problems described in the paper "Solving linear ordering problems with a combined interior point/simplex cutting plane algorithm":
    AUTHOR  =  {J. E. Mitchell and B. Borchers},
    TITLE   =  {Solving linear ordering problems with a combined
      interior point/simplex cutting plane algorithm},
    YEAR    =  2000,
    BOOKTITLE= {High Performance Optimization},
    EDITOR  =  {H. L. Frenk and C. Roos and T. Terlaky and S. Zhang},
    PUBLISHER= {Kluwer Academic Publishers},
    ADDRESS =  {Dordrecht, The Netherlands},
    PAGES   =  {349--366},
    CHAPTER =  14,
    URL={} }
You need to download two files to generate the problems: The following are also available:

The linear ordering problem

In the linear ordering problem, we are given MATSIZE objects, and we have pairwise comparisons between the objects. We want to choose the best ordering for the objects. MAT(I,J) gives the benefit of placing I before J in the ordering. Thus, we want to choose the ordering that solves:
  max  sum MAT(I,J): I is before J in the ordering
A collection of real-world instances of the linear ordering problem is available from LOLIB.

The generated instances

The files generate random DEGENERATE linear ordering problems. The coefficients mat_ij are uniformly distributed between 0 and 99 for i < j,and uniformly distributed between 0 and (100*RATIO)-1 for i > j. They are INTEGRAL. Further, PROPZERO of the coefficients are zero.

The program linordgen.f reads in four parameters from the file fort.15:

MATSIZE and ISEED are integers, the other two numbers can be anything between 0 and 1. The format of file fort.15 is MATSIZE, ISEED, RATIO, PROPZERO

The generator creates a permutation before actually generating the instances, so that the trivial ordering is not necessarily a good guess.

The FORTRAN program geninput.f generates 30 input files in the required fort.15 format. These correspond to the instances described in the paper "Solving linear ordering problems with a combined interior point/simplex cutting plane algorithm". These seed files are also contained in the subdirectory seeds. The optimal values for these problems and some others are available.

These input files can then be copied to fort.15 and then linordgen.f can be used to generate the matrices. Note that linordgen.f generates several lines of additional output before generating the entries MAT(I,J). The entries MAT(I,J) are output as

The file r100a2prob contains the output generated by linordgen.f from input seeds/r100a2. The first 14 lines contain information about the instance, and the last 10000 lines contain the entries in MAT(.,.)

Another version of geninput.f that generates a larger number of test input files is also available: geninput0.f. The output from this program is in the directory seeds/lots.

Back to my homepage.