Sparsity pattern

stp3d

Namestp3d
Downloadstp3d.mps.gz
Solutionstp3d.sol.gz
Set Membership Challenge Reoptimize
Problem StatusHard
Problem FeasibilityFeasible
Originator/ContributorT. Koch
Rows159488
Cols204880
Num. non-zeros in A662128
Num. non-zeros in c75648
Rows/Cols0.778445919563
Integers
Binaries204880
Continuous
min nonzero |Aij|1
max |Aij|1
min nonzero |cj|1.00001
max |cj|1.00303
Integer Objective493.71965
LP Objective481.877786
Aggregation
Variable Bound129232
Set partitioning82
Set packing2171
Set covering
Cardinality28003
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.


Last Update February 28, 2017 by Gerald Gamrath
© 2017 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
Imprint