Name | stp3d |
Download | stp3d.mps.gz |
Solution | stp3d.sol.gz |
Set Membership | Challenge Reoptimize |
Problem Status | Hard |
Problem Feasibility | Feasible |
Originator/Contributor | T. Koch |
Rows | 159488 |
Cols | 204880 |
Num. non-zeros in A | 662128 |
Num. non-zeros in c | 75648 |
Rows/Cols | 0.778445919563 |
Integers | |
Binaries | 204880 |
Continuous | |
min nonzero |Aij| | 1 |
max |Aij| | 1 |
min nonzero |cj| | 1.00001 |
max |cj| | 1.00303 |
Integer Objective | 493.71965 |
LP Objective | 481.877786 |
Aggregation | |
Variable Bound | 129232 |
Set partitioning | 82 |
Set packing | 2171 |
Set covering | |
Cardinality | 28003 |
Equality Knapsacks | |
Bin packing | |
Invariant Knapsack | |
Knapsacks | |
Integer Knapsack | |
Mixed 0/1 | |
General Cons. | |
References | Koch2004 |
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(http://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.