LOP (linear ordering problem) instances
The instances presented here use Mersenne Twister (available at
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html)
to generate edge costs randomly from the integers in the interval [1, 99].
Their densities (probability that an edge between any two vertices exists)
vary from 1% to 100%. Instances are separated by size (number of vertices n)
and are named as follows:
n[number of vertices]d[density]-[instance ID].
There are five instances for each combination of size and density.
The format of the instances is as follows:
[number of vertices n]
c11 c12 c13 ... c1n
c21 c22 c23 ... c2n
. . .
cn1 cn2 cn3 ... cnn
where "cuv" is the cost of edge (u,v).
instances with n = 500 (zip file)
instances with n = 1000 (zip file)
instances with n = 2000 (zip file)
instances with n = 3000 (zip file)
instances with n = 4000 (zip file)
instances with n = 8000 (zip file)
These instances are used in the following papers:
- C.S. Sakuraba and M. Yagiura,
Efficient local search algorithms for the linear ordering problem,
International Transactions in Operational Research, 17 (2010) 711-737.
- C.S. Sakuraba, D.P. Ronconi, E.G. Birgin and M. Yagiura,
Metaheuristics for Large-Scale Instances of the Linear Ordering Problem,
Expert Systems with Applications, 42 (2015) 4432-4442.
More information, including well-known benchmark instances, is available
from Rafael Marti's website.
Mutsunori YAGIURA