Learning To Dive In Branch And Bound
Authors: Max Paulus, Andreas Krause
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluated the effectiveness of L2Dive in two different experiments and on a total of six datasets. The first set of experiments (Section 5.1) was designed to study the diving performance of L2Dive in isolation and compare it against existing diving heuristics. On a benchmark of four synthetic combinatorial optimization problems from previous work [17], we performed single dives with each diver and measured the average primal gap. The second set of experiments (Section 5.2) directly included L2Dive into the branch and bound process of the open-source solver SCIP. |
| Researcher Affiliation | Academia | Max B. Paulus ETH Zurich max.paulus@inf.ethz.ch Andreas Krause ETH Zurich krausea@ethz.ch |
| Pseudocode | Yes | Algorithm 1 illustrates a generic diving heuristic. Algorithm 1: Generic Diving Heuristic |
| Open Source Code | Yes | L2Dive is fully integrated into the open-source solver SCIP. |
| Open Datasets | Yes | We used the dataset from Gasse et al. [18] which contains 9900 instances for training and 100 instances for validation and testing respectively. We considered the instances from Nair et al. [33], but used the same subset as Paulus et al. [35] who disregard trivial and numerically unstable instances. |
| Dataset Splits | Yes | For each class, we used 2000 instances in total; we trained on 1000 instances and validated and tested on 500 instances respectively. We used the dataset from Gasse et al. [18] which contains 9900 instances for training and 100 instances for validation and testing respectively. This dataset contains 2384 instances for training, 519 instances for validation and 545 instances for testing. |
| Hardware Specification | Yes | For each dataset, we chose the batch size to exhaust the memory of a single NVIDIA Ge Force GTX 1080 Ti device. Our experiments were conducted on a shared distributed compute cluster. To reduce measurement variability, we ran all test time evaluations repeatedly on machines equipped with the same Intel Xeon Gold 5118 CPU 2.3 GHz processors for three different seedings of the solver. |
| Software Dependencies | Yes | We fully integrate L2Dive into the open-source solver SCIP 7.0.2 [16]. |
| Experiment Setup | Yes | We trained each model with ADAM [27] for 100 epochs in the first set of experiments and for 10 epochs in the second set of experiments. We individually tuned the learning rate from a grid of [10 2, 10 3, 10 4]. For each dataset, we chose the batch size to exhaust the memory of a single NVIDIA Ge Force GTX 1080 Ti device. |