# Testset LIN

These instances where created by A. Lin . They are derived from a placement of rectangular blocks in a 2D plane, so all line segments are either horizontal or vertical. You could also see it as a very sparsified grid graph.

Here is an picture of lin12 with solution:

Solutions can be found in PV01c

Name   |V|    |E|    |T|    DC    Opt
lin0153 80 Ls 503
lin0255 82 Ls 557
lin0357 84 Ls 926
lin04157 266 Ps 1239
lin05160 269 Ls 1703
lin06165 274 14 Ls 1348
lin07307 526 Ps 1885
lin08311 530 10 Ps 2248
lin09313 532 12 Ps 2752
lin10321 540 20 Ps 4132
lin11816 1460 10 Ps 4280
lin12818 1462 12 Ps 5250
lin13822 1466 16 Ps 4609
lin14828 1472 22 Ps 5824
lin15840 1484 34 Ps 7145
lin161981 3633 12 Ps 6618
lin171989 3641 20 Ps 8405
lin181994 3646 25 NPs 9714
lin192010 3662 41 Ps 13268
lin203675 6709 11 Ps 6673
lin213683 6717 20 Ps 9143
lin223692 6726 28 Ps 10519
lin233716 6750 52 Ps 17560
lin247998 14734 16 Ps 15076
lin258007 14743 24 Ps 17803
lin268013 14749 30 Ps 21757
lin278017 14753 36 NPs 20678
lin288062 14798 81 NPs 32584
lin2919083 35636 24 NPs 23765
lin3019091 35644 31 Pm 27684
lin3119100 35653 40 ?m 31696
lin3219112 35665 53 ?m 39832
lin3319177 35730 117 ?m 56061
lin3438282 71521 34 ?h 45018
lin3538294 71533 45 ?h 50559
lin3638307 71546 58 ?d 55608
lin3738418 71657 172 ?d 99560

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