These instances are random generated sparse graphs with edge weights between 1 and 10.

The were introduced in Bea89 and were generated following a scheme outlined in Ane80 . More information is among others in Luc93 , KM98 , PD00 .

The original data sets are from the OR-Library.

The files can be found in the download section.

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

e01 | 2500 | 3125 | 5 | Ps | 111 |

e02 | 2500 | 3125 | 10 | Ps | 214 |

e03 | 2500 | 3125 | 417 | Ps | 4013 |

e04 | 2500 | 3125 | 625 | Ps | 5101 |

e05 | 2500 | 3125 | 1250 | Ps | 8128 |

e06 | 2500 | 5000 | 5 | Ps | 73 |

e07 | 2500 | 5000 | 10 | Pm | 145 |

e08 | 2500 | 5000 | 417 | Pm | 2640 |

e09 | 2500 | 5000 | 625 | Pm | 3604 |

e10 | 2500 | 5000 | 1250 | Pm | 5600 |

e11 | 2500 | 12500 | 5 | Pm | 34 |

e12 | 2500 | 12500 | 10 | Pm | 67 |

e13 | 2500 | 12500 | 417 | Pm | 1280 |

e14 | 2500 | 12500 | 625 | Pm | 1732 |

e15 | 2500 | 12500 | 1250 | Ps | 2784 |

e16 | 2500 | 62500 | 5 | Ph | 15 |

e17 | 2500 | 62500 | 10 | Ph | 25 |

e18 | 2500 | 62500 | 417 | NPh | 564 |

e19 | 2500 | 62500 | 625 | Pm | 758 |

e20 | 2500 | 62500 | 1250 | Ls | 1342 |

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