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

taq0014 | 6466 | 11046 | 128 | Ps | 5326 |

taq0023 | 572 | 963 | 11 | Ps | 621 |

taq0365 | 4186 | 7074 | 22 | Ps | 1914 |

taq0377 | 6836 | 11715 | 136 | NPs | 6393 |

taq0431 | 1128 | 1905 | 13 | Ps | 897 |

taq0631 | 609 | 932 | 10 | Ps | 581 |

taq0739 | 837 | 1438 | 16 | NPs | 848 |

taq0741 | 712 | 1217 | 16 | Ps | 847 |

taq0751 | 1051 | 1791 | 16 | Ps | 939 |

taq0891 | 331 | 560 | 10 | Ls | 319 |

taq0903 | 6163 | 10490 | 130 | NPs | 5099 |

taq0910 | 310 | 514 | 17 | Ls | 370 |

taq0920 | 122 | 194 | 17 | Ls | 210 |

taq0978 | 777 | 1239 | 10 | Ls | 566 |

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