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.

Last Update May 15, 2018 by Gerald Gamrath

© 2018 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

Imprint