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 ofSolutions can be found in PV01c

The files can be found in the download section.

Name | |V| | |E| | |T| | DC | Opt |
---|---|---|---|---|---|

lin01 | 53 | 80 | 4 | Ls | 503 |

lin02 | 55 | 82 | 6 | Ls | 557 |

lin03 | 57 | 84 | 8 | Ls | 926 |

lin04 | 157 | 266 | 6 | Ps | 1239 |

lin05 | 160 | 269 | 9 | Ls | 1703 |

lin06 | 165 | 274 | 14 | Ls | 1348 |

lin07 | 307 | 526 | 6 | Ps | 1885 |

lin08 | 311 | 530 | 10 | Ps | 2248 |

lin09 | 313 | 532 | 12 | Ps | 2752 |

lin10 | 321 | 540 | 20 | Ps | 4132 |

lin11 | 816 | 1460 | 10 | Ps | 4280 |

lin12 | 818 | 1462 | 12 | Ps | 5250 |

lin13 | 822 | 1466 | 16 | Ps | 4609 |

lin14 | 828 | 1472 | 22 | Ps | 5824 |

lin15 | 840 | 1484 | 34 | Ps | 7145 |

lin16 | 1981 | 3633 | 12 | Ps | 6618 |

lin17 | 1989 | 3641 | 20 | Ps | 8405 |

lin18 | 1994 | 3646 | 25 | NPs | 9714 |

lin19 | 2010 | 3662 | 41 | Ps | 13268 |

lin20 | 3675 | 6709 | 11 | Ps | 6673 |

lin21 | 3683 | 6717 | 20 | Ps | 9143 |

lin22 | 3692 | 6726 | 28 | Ps | 10519 |

lin23 | 3716 | 6750 | 52 | Ps | 17560 |

lin24 | 7998 | 14734 | 16 | Ps | 15076 |

lin25 | 8007 | 14743 | 24 | Ps | 17803 |

lin26 | 8013 | 14749 | 30 | Ps | 21757 |

lin27 | 8017 | 14753 | 36 | NPs | 20678 |

lin28 | 8062 | 14798 | 81 | NPs | 32584 |

lin29 | 19083 | 35636 | 24 | NPs | 23765 |

lin30 | 19091 | 35644 | 31 | Pm | 27684 |

lin31 | 19100 | 35653 | 40 | ?m | 31696 |

lin32 | 19112 | 35665 | 53 | ?m | 39832 |

lin33 | 19177 | 35730 | 117 | ?m | 56061 |

lin34 | 38282 | 71521 | 34 | ?h | 45018 |

lin35 | 38294 | 71533 | 45 | ?h | 50559 |

lin36 | 38307 | 71546 | 58 | ?d | 55608 |

lin37 | 38418 | 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.
**s**ecounds means less than a minute (this includes
instances which can be solved in fractions of a second).
**m**inutes means less than an hour. **h**ours is less than a
day and **d**ays is less than a week. **w**eeks 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