@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.

- 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:
- Compile geninput.f to give an executable
`geninput`, place it in a subdirectory`seeds`, and run it. - Compile linordgen.f to give an executable
`linordgen`, in the main directory. - Create another subdirectory called
`problems`. - Run
`gen_probs`.

- Compile geninput.f to give an executable
- The optimal values of the problems.

max sum MAT(I,J): I is before J in the orderingA collection of

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.

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.