Research map / Learning theory and algorithms / Combinatorial and search optimization
A General Large Neighborhood Search Framework for Solving Integer Linear Programs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Replace a single Gurobi solve with repeated LNS subproblem optimization using random variable decompositions | Integer linear programs · MVC, MAXCUT, CATS, and risk-aware path planning benchmarks | objective value | Helped |
| Use forward-training learned decompositions instead of random decompositions | LNS · MVC, MAXCUT, and CATS benchmarks | objective value | Helped |
| Use behavior-cloned learned decompositions instead of random decompositions | LNS · Risk-aware path planning, 30 and 40 obstacles | objective value: 0.6487 ± 0.07 -> 0.5876 ± 0.07; 0.3680 ± 0.03 -> 0.3502 ± 0.07 | Helped |
| Use reinforcement-learned REINFORCE decompositions instead of random decompositions | LNS · MVC and MAXCUT benchmarks | objective value: MVC BA: 433.59± 0.51 -> 434.16 ± 0.38; MAXCUT BA: -3583.63± 3.81 -> -3584.70± 1.49 | Mixed |
| Use learned decompositions rather than random decompositions | LNS · CATS auction problems | objective value: CATS Regions 2000: -99570.1 ± 790.5 -> -102247.9± 709.0 | Helped |
| Use forward training rather than behavior cloning | LNS decomposition policy · MVC BA 1000 | objective value: 433.09 ± 0.53 -> 432.00 ± 0.52 | Helped |
| Use forward training rather than behavior cloning | LNS decomposition policy · CATS Arbitrary 4000 | objective value: -172268.1 ± 1594.8 -> -169846.7 ± 5293.2 | Hurt |
| Increase the number of LNS subsets from 2 to 5 (ablation) | LNS parameter configuration · MVC ER 1000 | improvement ratio Δ/t: 14.42 ± 0.88 -> 2.08 ± 0.23 | Hurt |
| Increase subproblem solver time limit from 1 to 3 seconds with 2 subsets (ablation) | LNS parameter configuration · MVC ER 1000 | improvement ratio Δ/t: 13.61 ± 0.82 -> 14.42 ± 0.88 | Helped |
| Increase the number of LNS subsets from 2 to 5 (ablation) | LNS parameter configuration · MAXCUT ER 500 | improvement ratio Δ/t: 2155.60 ± 22.79 -> 5414.01 ± 29,76 | Helped |
| Increase the number of LNS subsets from 2 to 5 (ablation) | LNS parameter configuration · CATS Regions 2000 | improvement ratio Δ/t: 65360.28 ± 799.26 -> 54571.21 ± 344.89 | Hurt |
| Increase the number of LNS subsets from 3 to 5 (ablation) | LNS parameter configuration · Risk-aware path planning 30 obstacles | improvement ratio Δ/t: 0.41 ± 0.07 -> 0.33 ± 0.04 | Hurt |
Closest papers by meaning
- Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning (ICML 2023 · similarity 0.91)
- Adaptive Constraint Partition Based Optimization Framework for Large-Scale Integer Linear Programming (Student Abstract) (AAAI 2023 · similarity 0.91)
- Learning to Search in Local Branching (AAAI 2022 · similarity 0.88)
- Learning Large Neighborhood Search Policy for Integer Programming (NeurIPS 2021 · similarity 0.88)
- Regularized Large Neighborhood Search (NeurIPS 2026 · similarity 0.88)
- Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems (ICML 2025 · similarity 0.88)
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.