Learning Cuts via Enumeration Oracles
Authors: Daniel Thuerck, Boro Sofranac, Marc E Pfetsch, Sebastian Pokutta
NeurIPS 2023 | Conference 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 daniel.thuerck@quantagonia.com Boro Sofranac Quantagonia Bad Homburg, Germany boro.sofranac@quantagonia.com Marc E. Pfetsch Department of Mathematics, TU Darmstadt Darmstadt, Germany pfetsch@mathematik.tu-darmstadt.de Sebastian Pokutta Zuse Institute Berlin and TU Berlin Berlin, Germnany pokutta@zib.de |
| 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. |