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":

@incollection{MB_combined,
    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={http://www.rpi.edu/~mitchj/papers/combined.html} }

You need to download two files to generate the problems:

linordgen.f: This file will take a seed file and generate a linear ordering problem.
geninput.f: This file will create the thirty seed files used in the paper.

The following are also available:

problems.tar.gz (1.1M): This contains the thirty instances in a single file. You will need to gunzip the file, and then use tar to extract the instances. The tar process will set up a directory problems containing the instances. Note: this file is large, so you should probably only download it if you are unable to get the problem generator to work.
gen_probs: This is a 60 line command file that will take the inputs created by geninput.f and use linordgen.f to turn them into the problem instances. This replaces the mechanical steps of copying the seed files to fort.15 and then creating the actual instances. Take the following steps:
1. Compile geninput.f to give an executable geninput, place it in a subdirectory seeds, and run it.
2. Compile linordgen.f to give an executable linordgen, in the main directory.
3. Create another subdirectory called problems.
4. Run gen_probs.
The optimal values of the problems.

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: The number of sectors in the instance. Can be no larger than 250.
ISEED: A random seed.
RATIO and PROPZERO: See above.

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

MAT(1,1)
MAT(1,2)
...
MAT(1,MATSIZE)
MAT(2,1)
MAT(2,2)
...
...
MAT(MATSIZE,1)
MAT(MATSIZE,2)
...
MAT(MATSIZE,MATSIZE)

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.