These instances are grid graphs with rectangular holes. They come from a VLSI application (see JMRW94 ).

They were introduced in KM98 . More information can be found among others in UdAR99 and PD00 .

Here is an image of *alue7080*
PS
DjVu
with solution made by
E. Uchoa .

This is a picture of diw0495 with solution.

The files can be found in the download section.

Name | |V| | |E| | |T| | DC | Opt |
---|---|---|---|---|---|

msm0580 | 338 | 541 | 11 | Ps | 467 |

msm0654 | 1290 | 2270 | 10 | Ls | 823 |

msm0709 | 1442 | 2403 | 16 | Ls | 884 |

msm0920 | 752 | 1264 | 26 | Ps | 806 |

msm1008 | 402 | 695 | 11 | Ps | 494 |

msm1234 | 933 | 1632 | 13 | Ps | 550 |

msm1477 | 1199 | 2078 | 31 | Ps | 1068 |

msm1707 | 278 | 478 | 11 | Ls | 564 |

msm1844 | 90 | 135 | 10 | Ps | 188 |

msm1931 | 875 | 1522 | 10 | Ps | 604 |

msm2000 | 898 | 1562 | 10 | Ls | 594 |

msm2152 | 2132 | 3702 | 37 | Ps | 1590 |

msm2326 | 418 | 723 | 14 | Ps | 399 |

msm2492 | 4045 | 7094 | 12 | Ps | 1459 |

msm2525 | 3031 | 5239 | 12 | Ps | 1290 |

msm2601 | 2961 | 5100 | 16 | Ps | 1440 |

msm2705 | 1359 | 2458 | 13 | Ps | 714 |

msm2802 | 1709 | 2963 | 18 | Ps | 926 |

msm2846 | 3263 | 5783 | 89 | NPs | 3135 |

msm3277 | 1704 | 2991 | 12 | Ls | 869 |

msm3676 | 957 | 1554 | 10 | Ls | 607 |

msm3727 | 4640 | 8255 | 21 | Ls | 1376 |

msm3829 | 4221 | 7255 | 12 | Ps | 1571 |

msm4038 | 237 | 390 | 11 | Ls | 353 |

msm4114 | 402 | 690 | 16 | Ls | 393 |

msm4190 | 391 | 666 | 16 | Ls | 381 |

msm4224 | 191 | 302 | 11 | Ls | 311 |

msm4312 | 5181 | 8893 | 10 | Ps | 2016 |

msm4414 | 317 | 476 | 11 | Ls | 408 |

msm4515 | 777 | 1358 | 13 | Ps | 630 |

The column **DC** classifies the difficulty of the instance.

- L
- Solvable by usage of local preprocessing. Typical examples are the SD-Test, BD-n Tests and FST computations. Neither a global upper nor lower bound needs to be computed.
- P
- Solvable by polynomial time algorithms, like dual ascent in combination with primal heuristic, a integral LP formulation or advanced preprocessing like reduced cost criteria or the RCR-Test.
- NP
- No polynomial time algorithm is known. Use of an exponential time enumeration sceme like Branch-and-Bound is neccessary.

The letter after class gives an impression how long it takes to solve
the problem using state-of-the-art soft- and hardware.
**s**ecounds means less than a minute (this includes
instances which can be solved in fractions of a second).
**m**inutes means less than an hour. **h**ours is less than a
day and **d**ays is less than a week. **w**eeks mean it takes
really a long time to solve this instance.
**?** means the instance is not solved or the time is not known.

If the number in the **Opt** column is written in *italics*
the optimum is not known. The number given is the best know upper bound.

Last Update : 2015/02/11 11:57:20 $ by Thorsten Koch

© 2001 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

URL: http://www.zib.de