Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning Cuts via Enumeration Oracles
Daniel Thuerck, Boro Sofranac, Marc Pfetsch, Sebastian Pokutta
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| separate local cuts at every node with up- and down-lifting (lc1-nc-lifting) vs SCIP default | Branch-and-cut with Frank-Wolfe local cuts · SCIP generalized assignment (45 instances) | time (s): 98.2 -> 86.8 | Improved |
| same, on GAP instances solved by all variants | lc1-nc-lifting · GAP 21 solved instances | time (s): 6.0 -> 4.2 | Improved |
| same, on GAP instances solved by all variants | lc1-nc-lifting · GAP 21 solved instances | # nodes: 614 -> 185 | Improved |
| local cuts only in the root node instead of whole tree (ablation) | lc0-nc-lifting vs lc1-nc-lifting · SCIP generalized assignment (45 instances) | # solved: 29 -> 26 | Hurt |
| use only down-lifting instead of up- and down-lifting (ablation) | lc0-nc-downlift vs lc0-nc-lifting · SCIP generalized assignment (45 instances) | time (s): 113.7 -> 411.7 | Hurt |
| use only down-lifting instead of up- and down-lifting (ablation) | lc0-nc-downlift vs lc0-nc-lifting · SCIP generalized assignment (45 instances) | # solved: 26 -> 21 | Hurt |
| replace LP-based local cuts with Frank-Wolfe local cuts | Local cut separation · MKP n=100, m=5, alpha=25 root node | gap closed (%): 18.88 -> 12.54 | Hurt |
| replace LP-based local cuts with Frank-Wolfe local cuts | Local cut separation · MKP n=100, m=5, alpha=25 root node | separation time (s): 1.60 -> 0.76 | Improved |
| replace LP-based local cuts with Frank-Wolfe local cuts | Local cut separation · MKP n=500, m=5, alpha=75 root node | time (s): 22.53 -> 7.63 | Improved |
| use lc1-nc-uplift in full branch-and-cut on larger MKP instances (ablation) | Local cuts in branch-and-cut · MKP n=100, m=30, alpha=25 | # solved: 10 -> 3 | Hurt |
| use lc0-nc-lifting in full branch-and-cut on small MKP instances | Local cuts at root · MKP n=100, m=5, alpha=25 | time (s): 11.76 -> 5.89 | Improved |
| apply CMIR to the produced cut (ablation) | Frank-Wolfe local cuts · GAP | performance | No clear effect |
Closest papers by meaning
- Learning to Remove Cuts in Integer Linear Programming (ICML 2024 · similarity 0.89)
- Learning Cut Generating Functions for Integer Programming (NeurIPS 2024 · similarity 0.86)
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates (AAAI 2024 · similarity 0.84)
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.84)
- Faster Global Minimum Cut with Predictions (ICML 2025 · similarity 0.83)
- Box Facets and Cut Facets of Lifted Multicut Polytopes (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
