Theoretical Computer Science / Theoretische Informatik

Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]

Multi-Level Crossing Minimization

Here, you can find the benchmark sets used in our study of Semidefinite Programs to solve Multi-level Crossing Minimization problems. Detailed descriptions can be found in the papers:

Instances

Description Table (in paper) Link
Random instances of varying complexity 1 random.tar.bz2 (460KB)
Rome graphs & North DAGs,
with layerings GKNV & UPL
2 rome_north_gknv-upl.tar.bz2 (1MB)
Polytopes, Graphviz & Other 3 polytopes_graphviz_other.tar.bz2 (3KB)
Further real-world instances - further_realworld.tar.bz2 (1KB)

The order given in these files is the order of the optimal (or best known) solution, as reported in the paper.

The instances north64.18_GKNV.mlcm and north42.8_GKNV.mlcm are particularly interesting, as they are the only two instances in Table 2 not solved to optimality within 1500 SDP function evaluations. For the former, we assume that the upper bound (the ordering in the file) is actually the optimal solution.

The instances in the set Further were not considered in the original paper, but for the comparison to Multi-level Verticality Optimization.

File Format

The tar.gz-files contain simple text files, each text file is a single instance. The format is as follows:

  <Number-of-Levels>
<Number-of-Edges-Between-First-and-Second-Level>
<Number-of-Edges-Between-Second-and-Third-Level>
...
<Number-of-Nodes-on-First-Level>
<Number-of-Nodes-on-Second-Level>
...
<Index-of-Node-on-First-Layer> <Index-of-Node-on-Second-Level>
<Index-of-Node-on-First-Layer> <Index-of-Node-on-Second-Level>
...
<Index-of-Node-on-Second-Layer> <Index-of-Node-on-Third-Level>
...

Thereby, the 2-tuples describe the edges in the graph. The node indices start with 0 on each level.

research/mlcm.txt · Last modified: April 17, 2013 (21:43) by chimani