Learning Cuts via Enumeration Oracles
Authors: Daniel Thuerck, Boro Sofranac, Marc E Pfetsch, Sebastian Pokutta
NeurIPS 2023 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We demonstrate the effectiveness of our approach with a case study targeting the multidimensional knapsack problem (MKP). Our computational results show that embedding our method in the academic solver SCIP leads to 31% faster solving times on the instances solved to optimality, on average. |
| Researcher Affiliation | Collaboration | Daniel Thuerck Quantagonia Bad Homburg, Germany EMAIL Boro Sofranac Quantagonia Bad Homburg, Germany EMAIL Marc E. Pfetsch Department of Mathematics, TU Darmstadt Darmstadt, Germany EMAIL Sebastian Pokutta Zuse Institute Berlin and TU Berlin Berlin, Germnany EMAIL |
| Pseudocode | Yes | Algorithm 1 Lazy Away-Step Frank-Wolfe [18, 19] with explicit active set and early termination |
| Open Source Code | No | The paper mentions using SCIP, an open-source solver, but does not provide concrete access (link or explicit statement of release) to the source code for the specific methodology described in this paper. |
| Open Datasets | Yes | To demonstrate the advantage of using local cuts with the Frank-Wolfe approach, we run our implementation on the generalized assignment instances from the OR-Library available at http:// people.brunel.ac.uk/~mastjjb/jeb/orlib/gapinfo.html. We use the same multi-dimensional knapsack instances as Kaparis and Letchford: they were originally generated randomly by Chu and Beasley [24] and are available at http://people.brunel.ac.uk/~mastjjb/jeb/orlib/ mknapinfo.html. |
| Dataset Splits | No | The paper uses existing problem instances (e.g., from OR-Library) but does not provide specific details on how these instances are split into training, validation, or test sets (e.g., percentages, sample counts, or explicit cross-validation setup) for the purpose of reproducing data partitioning. |
| Hardware Specification | Yes | All tests were performed on a Linux cluster with 3.5 GHz Intel Xeon E5-1620 Quad-Core CPUs, having 32 GB main memory and 10 MB cache. |
| Software Dependencies | Yes | We implemented the described methods in C/C++, using a developer version of SCIP 8.0.4 (githash 3dbcb38) and CPLEX 12.10 as LP-solver. |
| Experiment Setup | Yes | All computations were run single-threaded and with a time limit of one hour. To concentrate on the improvement of local cuts on the dual bound, we initialize all runs with the optimal value. We used ϵ = 1 10 9 in Algorithm 1. The iteration limit for the Frank-Wolfe algorithm is 10 000 in the root node and 1000 in the subtree. |