Goto ZIB Goto TU-Braunschweig Goto TU-Darmstadt

Testset EFST

The files can be found in the download section.

Name   |V|    |E|    |T|    DC    Opt 
 d198    11424.301667772 
 lin318    36110.580036373 
 fl417    9871.4179319117 
 pcb442    44471.068825944 
 att532    73335.267625368 
 ali535    1650.6377719502 
 u574    31094.463448656 
 rat575    6035.7245763774 
 p654    28314.810030354 
 d657    41214.425048195 
 gr666    2529.229037536 
 u724    36634.261347888 
 rat783    7866.6645608979 
 dsj1000    15447941.064458 
 pr1002    217373.24422704 
 u1060    189093.02051975 
 vm1084    203482.71699821 
 pcb1173    49822.613134651 
 d1291    45973.789747608 
 rl1304    219093.29859421 
 rl1323    236004.75098461 
 nrw1379    49851.160470726 
 fl1400    16368.627244616 
 u1432    137176.50832733 
 fl1577    18869.833664741 
 d1655    55008.061282658 
 vm1748    286342.86703777 
 u1817    52872.086967484 
 rl1889    272639.73159176 
 d2103     
 u2152    59842.815269889 
 u2319     
 pr2392    329934.9393818 
 pcb3038    122708.01599934 
 fl3795     
 fnl4461    161758.84199824 
 rl5915    510263.923619 
 rl5934    503013.18732577 
 pla7397     
 rl11849    830826.11634121 
 usa13509    17259142.879384 
 brd14051    412293.95412125 
 d15112    1375126.1375231 
 d18512    569700.01214726 
 pla33810     
 pla85900     
 R25K01    98.961213338945 
 R25K02    99.037087811052 
 R25K03    99.215720747152 
 R25K04    98.943139188216 
 R25K05    99.491232074783 
 R25K06    99.372876645628 
 R25K07    99.564610492085 
 R25K08    99.266201605252 
 R25K09    99.096863627624 
 R25K10    99.11048009775 
 R25K11    99.121634469591 
 R25K12    99.113444661919 
 R25K13    99.400552566176 
 R25K14    99.204641432083 
 R25K15    99.252132405203 
 R50K01    140.39836924048 
 R50K02    139.95578059277 
 R50K03    140.00641242385 
 R50K04    140.0928689389 
 R50K05    139.99490604066 
 R50K06    140.34854151925 
 R50K07    140.24958165944 
 R50K08    140.35114677927 
 R50K09    140.36284558041 
 R50K10    140.32109312112 
 R50K11    140.16941813112 
 R50K12    140.20101310284 
 R50K13    140.03945196895 
 R50K14    140.20979540971 
 R50K15    140.44792646591 
 R100K01    198.30618792184 
 R100K02    197.96950012452 
 R100K03    198.0220998458 
 R100K04    198.18937285641 
 R100K05    198.15227707417 
 R100K06    198.174298814 
 R100K07    197.8772001419 
 R100K08    197.99443344263 
 R100K09    198.13583204498 
 R100K10    198.03909190767 
 R100K11    198.13590213158 
 R100K12    198.38401807733 
 R100K13    198.05354369702 
 R100K14    198.22592767164 
 R100K15    198.27303096961 

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