Submitter | Variables | Constraints | Density | Status | Group | Objective | MPS File |
---|---|---|---|---|---|---|---|

T. Koch | 204880 | 159488 | 2.02635e-05 | hard | – | 493.71965 | stp3d.mps.gz |

Steiner tree packing instance in a 3 dimensional grid-graph, LP relaxation is highly degenerate. Alkis Vazacopoulos reports finding the first feasible solution of this instance using XPRESS 2006B. This instance was solved by a first implementation of ParaSCIP using up to 2048 cores of HLRN-II(https://www.hlrn.de). ParaSCIP, mainly developed by Yuji Shinano, is an extension of SCIP and realizes a parallelization on a distributed memory computing environment. For being able to interrupt and warmstart the computations, ParaSCIP has a checkpoint mechanism. Therefore, selected subproblems are stored as warm start information, which allows to virtually run ParaSCIP, although the HLRN-II environment imposes a time limit of 48 hours per run. The problem was presolved several times with SCIP presolving techniques. After that, it took approximately 114 hours to solve this instance. Imported from MIPLIB2010.

Detailed explanation of the following tables can be found here.

Original | Presolved | |
---|---|---|

Variables | 204880 | 179062 |

Constraints | 159488 | 139386 |

Binaries | 204880 | 179062 |

Integers | 0 | 0 |

Continuous | 0 | 0 |

Implicit Integers | 0 | 0 |

Fixed Variables | 0 | 0 |

Nonzero Density | 2.02635e-05 | 2.33948e-05 |

Nonzeroes | 662128 | 583904 |

Original | Presolved | |
---|---|---|

Total | 159488 | 139386 |

Empty | 0 | 0 |

Free | 0 | 0 |

Singleton | 0 | 0 |

Aggregations | 0 | 94 |

Precedence | 129232 | 112973 |

Variable Bound | 0 | 50 |

Set Partitioning | 82 | 23 |

Set Packing | 2171 | 1965 |

Set Covering | 0 | 0 |

Cardinality | 28003 | 24281 |

Invariant Knapsack | 0 | 0 |

Equation Knapsack | 0 | 0 |

Bin Packing | 0 | 0 |

Knapsack | 0 | 0 |

Integer Knapsack | 0 | 0 |

Mixed Binary | 0 | 0 |

General Linear | 0 | 0 |

Indicator | 0 | 0 |

Available nonzero structure and decomposition information. Further information can be found here.

Decomposed structure of original problem (dec-file)

Decomposed structure after trivial presolving (dec-file)

value | min | median | mean | max | |
---|---|---|---|---|---|

Components | 1.672098 | ||||

Constraint % | 0.00215 | 2.14327 | 2.39622 | 12.05640 | |

Variable % | 0.00223 | 2.17372 | 3.06850 | 9.25909 | |

Score | 0.934837 |

No solution available for stp3d .

The following instances are most similar to stp3d in the collection. This similarity analysis is based on 100 scaled instance features describing properties of the variables, objective function, bounds, constraints, and right hand sides.

```
@phdthesis{Koch2004,
author = {Thorsten Koch},
language = {English},
school = {Technische {Universit\"at} Berlin},
title = {Rapid Mathematical Programming},
year = {2004}
}
```

Last Update 2024 by Julian Manns

generated with R Markdown

© by Zuse Institute Berlin (ZIB)

Imprint