Goto ZIB Goto TU-Braunschweig Goto TU-Darmstadt

Testset 1R

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 
 1r1111250 2352 Ps 28000 
 1r1121250 2352 Ps 28000 
 1r1131250 2352 Ps 26000 
 1r1211250 2340 Ps 36000 
 1r1221250 2342 Ps 45000 
 1r1231250 2343 Pm 40000 
 1r1311250 2336 Ps 43000 
 1r1321250 2340 Ps 37000 
 1r1331250 2326 Ps 36000 
 1r2111250 2352 31 Pm 77000 
 1r2121250 2352 30 Pm 81000 
 1r2131250 2352 29 Ps 70000 
 1r2211250 2341 31 Pm 79000 
 1r2221250 2343 31 Ps 68000 
 1r2231250 2340 31 Ps 77000 
 1r2311250 2331 30 Ps 80000 
 1r2321250 2335 29 Ps 86000 
 1r2331250 2327 31 Ps 71000 
 1r3111250 2352 56 Ps 108000 
 1r3121250 2352 60 Ps 113000 
 1r3131250 2352 58 Ps 106000 
 1r3211250 2338 59 Ps 118000 
 1r3221250 2336 60 Ps 113000 
 1r3311250 2319 58 Ps 103000 
 1r3321250 2333 58 Ps 109000 
 1r3331250 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. secounds means less than a minute (this includes instances which can be solved in fractions of a second). minutes means less than an hour. hours is less than a day and days is less than a week. weeks 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