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

diw0234 | 5349 | 10086 | 25 | Ps | 1996 |

diw0250 | 353 | 608 | 11 | Ls | 350 |

diw0260 | 539 | 985 | 12 | Ls | 468 |

diw0313 | 468 | 822 | 14 | Ls | 397 |

diw0393 | 212 | 381 | 11 | Ls | 302 |

diw0445 | 1804 | 3311 | 33 | Ps | 1363 |

diw0459 | 3636 | 6789 | 25 | Ls | 1362 |

diw0460 | 339 | 579 | 13 | Ls | 345 |

diw0473 | 2213 | 4135 | 25 | Ps | 1098 |

diw0487 | 2414 | 4386 | 25 | Ps | 1424 |

diw0495 | 938 | 1655 | 10 | Ls | 616 |

diw0513 | 918 | 1684 | 10 | Ls | 604 |

diw0523 | 1080 | 2015 | 10 | Ls | 561 |

diw0540 | 286 | 465 | 10 | Ls | 374 |

diw0559 | 3738 | 7013 | 18 | Ps | 1570 |

diw0778 | 7231 | 13727 | 24 | Ps | 2173 |

diw0779 | 11821 | 22516 | 50 | NPs | 4440 |

diw0795 | 3221 | 5938 | 10 | Ps | 1550 |

diw0801 | 3023 | 5575 | 10 | Ps | 1587 |

diw0819 | 10553 | 20066 | 32 | Ps | 3399 |

diw0820 | 11749 | 22384 | 37 | Ps | 4167 |

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