Separator-Based Pruned Dynamic Programming for Steiner Tree
Authors: Yoichi Iwata, Takuto Shigemura1520-1527
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical evaluation shows that our pruned DP algorithm is quite effective against real-world instances admitting small separators, scales to more than a hundred terminals, and is competitive with a branch-and-cut solver. |
| Researcher Affiliation | Academia | Yoichi Iwata National Institute of Informatics yiwata@nii.ac.jp Takuto Shigemura The University of Tokyo sigma@is.s.u-tokyo.ac.jp |
| Pseudocode | Yes | Algorithm 1 (Erickson, Monma, and Veinott 1987) and Algorithm 2 Separator-based Pruned DP Algorithm. |
| Open Source Code | Yes | Our implementation is available on Git Hub2. 2https://github.com/wata-orz/steiner tree |
| Open Datasets | Yes | We conducted experiments using the benchmark datasets used in the DIMACS challenge and the PACE challenge. Stein Lib A collection of crafted/real-world testsets (Koch, Martin, and Voß 2000). ... Vienna Real-world instances from telecommunication networks (Leitner et al. 2014). Copenhagen Obstacle-avoiding rectilinear Steiner tree instances preprocessed with Ob Steiner (Huang and Young 2013). PACE Public instances of the two exact tracks of the PACE challenge, each of which consists of 100 instances from Stein Lib and Vienna. |
| Dataset Splits | No | The paper mentions using benchmark datasets but does not specify any training/validation/test splits, specific percentages, or sample counts used for reproduction. |
| Hardware Specification | Yes | We conducted experiments on a Linux server with Intel Xeon E5-2670 (2.6 GHz) which produced a score of 399 for the DIMACS benchmark. |
| Software Dependencies | Yes | SCIP-JACK uses the latest version of SCIP-JACK... It internally uses an MIP solver SCIP (Gleixner et al. 2018) version 5.0.1 and an LP solver So Plex (Gleixner, Steffy, and Wolter 2012; 2015) version 3.1.1. |
| Experiment Setup | Yes | For each test, we use a single thread and limit the maximum run time by 30 minutes and the maximum memory by 6GB. |