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

research:mlcm

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:

- M. Chimani, P. Hungerländer, M. Jünger, P. Mutzel.
**An SDP Approach to Multi-level Crossing Minimization.**SIAM Workshop on Algorithm Engineering & Experiments 2011, San Francisco (ALENEX11), pp. 116-126, SIAM, 2011. (link to published version)

- M. Chimani, P. Hungerländer, M. Jünger, P. Mutzel.
**An SDP Approach to Multi-level Crossing Minimization.**ACM Journal of Experimental Algorithmics, Volume 17(3), Article 3.3, 2012.

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.

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: 2013/04/17 21:43 by chimani