These instances are generated 2D cross-grid graphs to resample a construction problem.

The were introduced in Fre97 .

The files can be found in the download section.

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

1r111 | 1250 | 2352 | 6 | Ps | 28000 |

1r112 | 1250 | 2352 | 6 | Ps | 28000 |

1r113 | 1250 | 2352 | 6 | Ps | 26000 |

1r121 | 1250 | 2340 | 6 | Ps | 36000 |

1r122 | 1250 | 2342 | 6 | Ps | 45000 |

1r123 | 1250 | 2343 | 6 | Pm | 40000 |

1r131 | 1250 | 2336 | 6 | Ps | 43000 |

1r132 | 1250 | 2340 | 6 | Ps | 37000 |

1r133 | 1250 | 2326 | 6 | Ps | 36000 |

1r211 | 1250 | 2352 | 31 | Pm | 77000 |

1r212 | 1250 | 2352 | 30 | Pm | 81000 |

1r213 | 1250 | 2352 | 29 | Ps | 70000 |

1r221 | 1250 | 2341 | 31 | Pm | 79000 |

1r222 | 1250 | 2343 | 31 | Ps | 68000 |

1r223 | 1250 | 2340 | 31 | Ps | 77000 |

1r231 | 1250 | 2331 | 30 | Ps | 80000 |

1r232 | 1250 | 2335 | 29 | Ps | 86000 |

1r233 | 1250 | 2327 | 31 | Ps | 71000 |

1r311 | 1250 | 2352 | 56 | Ps | 108000 |

1r312 | 1250 | 2352 | 60 | Ps | 113000 |

1r313 | 1250 | 2352 | 58 | Ps | 106000 |

1r321 | 1250 | 2338 | 59 | Ps | 118000 |

1r322 | 1250 | 2336 | 60 | Ps | 113000 |

1r331 | 1250 | 2319 | 58 | Ps | 103000 |

1r332 | 1250 | 2333 | 58 | Ps | 109000 |

1r333 | 1250 | 2331 | 58 | Ps | 113000 |

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