Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation
Authors: Daniel Anderson, Gregor Hendel, Pierre Le Bodic, Merlin Viernickel1427-1434
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases. |
| Researcher Affiliation | Academia | Daniel Anderson,1 Gregor Hendel,2 Pierre Le Bodic,3 Merlin Viernickel2 1Department of Computer Science, Carnegie Mellon University, Pittsburgh, USA 2Mathematical Optimization Department, Zuse Institute Berlin, Berlin, Germany 3Faculty of Information Technology, Monash University, Melbourne, Australia |
| Pseudocode | No | The paper describes the methods in text and mathematical formulas but does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper states: "It is implemented in the MIP solver SCIP and will be available in future releases." This indicates future availability, not concrete access to the source code at the time of publication. |
| Open Datasets | Yes | Throughout the paper we use the MIP solver SCIP 6.0 (Gleixner et al. 2018) and the so-called MMMc MIP benchmark, a collection of 496 instances from MIPLIB 2010 benchmark (Koch et al. 2011), MIPLIB 2003 (Achterberg, Koch, and Martin 2006), MIPLIB 3.0 (Bixby et al. 1998), and COR@L (Coral 2010). |
| Dataset Splits | No | The paper uses established MIP benchmark instances (MMMc MIP benchmark), but it does not describe specific training, validation, or test dataset splits in terms of percentages or sample counts, as might be done for training a machine learning model. The experiments involve running a solver on a set of instances. |
| Hardware Specification | Yes | All experiments have been conducted on a cluster with 48 nodes equipped with Intel Xeon Gold 5122 at 3.60GHz and 96GB RAM. |
| Software Dependencies | Yes | Throughout the paper we use the MIP solver SCIP 6.0 (Gleixner et al. 2018) and We use SCIP 6.0 with So Plex 4.0 as LP solver. |
| Experiment Setup | Yes | given a parameter γ > 1, a restart is decided at step k if γ rk < ˆr(k). In our experiments, γ is set to 100, and we update the estimate ˆr(k) at every leaf node, i.e. at every step k such that |Fk| = |Fk 1|+1. We have two safeguards against the potentially high variance of ˆr(k). First, a restart is only triggered after condition (3) is satisfied for 50 consecutive k s. Second, no restart is performed until |Fk| 1000. We test our restart strategy with four different tree-size estimates: WBE; linear, a linear forecast of the search progress using double exponential smoothing with parameters α = β = 0.15; window-acc and window-vel, a moving window with or without acceleration. Both use a window size of 100. |