Goto ZIB Goto TU-Braunschweig Goto TU-Darmstadt

Testset PUC

These instances where generated by I. Rosseti , M. P. de Arag„o , C. C. Ribeiro , E. Uchoa and R. F. Werneck .

The graphs are hypercubes, from code covering and bipartite ones. A detailed describtion can be found in RdARUW01 . Information on the results are given in dARUW01 .

The files can be found in the download section.

Name   |V|    |E|    |T|    DC    Opt 
 bip42p1200 3982 200 NP? 24657 
 bip42u1200 3982 200 NP? 236 
 bip52p2200 7997 200 NP? 24526 
 bip52u2200 7997 200 NP? 234 
 bip62p1200 10002 200 NP? 22843 
 bip62u1200 10002 200 ?? 219 
 bipa2p3300 18073 300 ?? 35326 
 bipa2u3300 18073 300 ?? 338 
 bipe2p550 5013 50 NP? 5616 
 bipe2u550 5013 50 NP? 54 
 cc10-2p1024 5120 135 ?? 35297 
 cc10-2u1024 5120 135 ?? 342 
 cc11-2p2048 11263 244 ?? 63491 
 cc11-2u2048 11263 244 ?? 612 
 cc12-2p4096 24574 473 ?? 121106 
 cc12-2u4096 24574 473 ?? 1172 
 cc3-10p1000 13500 50 ?? 12772 
 cc3-10u1000 13500 50 ?? 125 
 cc3-11p1331 19965 61 ?? 15582 
 cc3-11u1331 19965 61 ?? 153 
 cc3-12p1728 28512 74 ?? 18826 
 cc3-12u1728 28512 74 ?? 185 
 cc3-4p64 288 NP? 2338 
 cc3-4u64 288 NP? 23 
 cc3-5p125 750 13 NP? 3661 
 cc3-5u125 750 13 ?? 36 
 cc5-3p243 1215 27 ?? 7299 
 cc5-3u243 1215 27 ?? 71 
 cc6-2p64 192 12 NPm 3271 
 cc6-2u64 192 12 NPm 32 
 cc6-3p729 4368 76 ?? 20270 
 cc6-3u729 4368 76 ?? 197 
 cc7-3p2187 15308 222 ?? 56799 
 cc7-3u2187 15308 222 ?? 549 
 cc9-2p512 2304 64 ?? 17199 
 cc9-2u512 2304 64 ?? 167 
 hc10p1024 5120 512 ?? 59797 
 hc10u1024 5120 512 ?? 575 
 hc11p2048 11264 1024 ?? 119492 
 hc11u2048 11264 1024 ?? 1145 
 hc12p4096 24576 2048 ?? 236949 
 hc12u4096 24576 2048 ?? 2262 
 hc6p64 192 32 NPm 4003 
 hc6u64 192 32 NPm 39 
 hc7p128 448 64 NP? 7905 
 hc7u128 448 64 NP? 77 
 hc8p256 1024 128 NP? 15322 
 hc8u256 1024 128 NP? 148 
 hc9p512 2304 256 NP? 30242 
 hc9u512 2304 256 NP? 292 

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