Goto ZIB Goto TU-Braunschweig Goto TU-Darmstadt

Testset WRP3

These instances are wire routing problems from industry. Only one terminal of a group needs to be connected to the tree.

More information can be found in ZR00 .

The files can be found in the download section.

Name   |V|    |E|    |T|    DC    Opt 
 wrp3-11128 227 11 Ps 1100361 
 wrp3-1284 149 12 Ps 1200237 
 wrp3-13311 613 13 Ps 1300497 
 wrp3-14128 247 14 Ps 1400250 
 wrp3-15138 257 15 Ps 1500422 
 wrp3-16204 374 16 Ps 1600208 
 wrp3-17177 354 17 Ps 1700442 
 wrp3-19189 353 19 Ps 1900439 
 wrp3-20245 454 20 Ps 2000271 
 wrp3-21237 444 21 Ps 2100522 
 wrp3-22233 431 22 Ps 2200557 
 wrp3-23132 230 23 Ps 2300245 
 wrp3-24262 487 24 Ps 2400623 
 wrp3-25246 468 25 Ps 2500540 
 wrp3-26402 780 26 Ps 2600484 
 wrp3-27370 721 27 Ps 2700502 
 wrp3-28307 559 28 Ps 2800379 
 wrp3-29245 436 29 Ps 2900479 
 wrp3-30467 896 30 Ps 3000569 
 wrp3-31323 592 31 Ps 3100635 
 wrp3-33437 838 33 Ps 3300513 
 wrp3-341244 2474 34 Pm 3400646 
 wrp3-36435 818 36 Ps 3600610 
 wrp3-371011 2010 37 Pm 3700485 
 wrp3-38603 1207 38 Pm 3800656 
 wrp3-39703 1616 39 Ph 3900450 
 wrp3-41178 307 41 Ps 4100466 
 wrp3-42705 1373 42 Pm 4200598 
 wrp3-43173 298 43 Ps 4300457 
 wrp3-451414 2813 45 Pm 4500860 
 wrp3-48925 1738 48 Pm 4800552 
 wrp3-49886 1800 49 Pm 4900882 
 wrp3-501119 2251 50 NPh 5000673 
 wrp3-52701 1352 52 NPm 5200825 
 wrp3-53775 1471 53 Ps 5300847 
 wrp3-551645 3186 55 NPh 5500888 
 wrp3-56853 1590 56 Pm 5600872 
 wrp3-60838 1763 60 Ph 6001164 
 wrp3-62670 1316 62 Pm 6201016 
 wrp3-641822 3610 64 Ph 6400931 
 wrp3-662521 4858 66 Ph 6600922 
 wrp3-67987 1923 67 Pm 6700776 
 wrp3-69856 1621 69 Pm 6900841 
 wrp3-701468 2931 70 Pm 7000890 
 wrp3-711221 2414 71 Pm 7101028 
 wrp3-731890 3613 73 Ph 7301207 
 wrp3-741019 1941 74 Pm 7400759 
 wrp3-75729 1395 75 Pm 7501020 
 wrp3-761761 3370 76 Ph 7601028 
 wrp3-782346 4656 78 Ph 7801094 
 wrp3-79833 1595 79 Pm 7900444 
 wrp3-801491 2831 80 Pm 8000849 
 wrp3-833168 6220 83 ?? 8300906 
 wrp3-842356 4547 84 Pd 8401094 
 wrp3-85528 1017 85 NPm 8500739 
 wrp3-861360 2607 86 Pm 86000746 
 wrp3-88743 1409 88 NPm 88001175 
 wrp3-911343 2594 91 Ph 91000866 
 wrp3-921765 3613 92 Ph 92000764 
 wrp3-941976 3836 94 NPh 94001181 
 wrp3-962518 4985 96 Ph 96001172 
 wrp3-982265 4545 98 NPd 98001224 
 wrp3-992076 4072 99 Ph 99001097 

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