Goto ZIB Goto TU-Braunschweig Goto TU-Darmstadt

Testset MSM

These instances are grid graphs with rectangular holes. They come from a VLSI application (see JMRW94 ).

They were introduced in KM98 . More information can be found among others in UdAR99 and PD00 .

Here is an image of alue7080 PS DjVu with solution made by E. Uchoa .

This is a picture of diw0495 with solution. diw0495 with solution

The files can be found in the download section.

Name   |V|    |E|    |T|    DC    Opt 
 msm0580338 541 11 Ps 467 
 msm06541290 2270 10 Ls 823 
 msm07091442 2403 16 Ls 884 
 msm0920752 1264 26 Ps 806 
 msm1008402 695 11 Ps 494 
 msm1234933 1632 13 Ps 550 
 msm14771199 2078 31 Ps 1068 
 msm1707278 478 11 Ls 564 
 msm184490 135 10 Ps 188 
 msm1931875 1522 10 Ps 604 
 msm2000898 1562 10 Ls 594 
 msm21522132 3702 37 Ps 1590 
 msm2326418 723 14 Ps 399 
 msm24924045 7094 12 Ps 1459 
 msm25253031 5239 12 Ps 1290 
 msm26012961 5100 16 Ps 1440 
 msm27051359 2458 13 Ps 714 
 msm28021709 2963 18 Ps 926 
 msm28463263 5783 89 NPs 3135 
 msm32771704 2991 12 Ls 869 
 msm3676957 1554 10 Ls 607 
 msm37274640 8255 21 Ls 1376 
 msm38294221 7255 12 Ps 1571 
 msm4038237 390 11 Ls 353 
 msm4114402 690 16 Ls 393 
 msm4190391 666 16 Ls 381 
 msm4224191 302 11 Ls 311 
 msm43125181 8893 10 Ps 2016 
 msm4414317 476 11 Ls 408 
 msm4515777 1358 13 Ps 630 

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