Pith. sign in

REVIEW 9 cited by

Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2107.10201 v3 pith:O64MALBG submitted 2021-07-21 math.OC cs.LG

Nicolas Sonnerat , Pengming Wang , Ira Ktena , Sergey Bartunov , Vinod Nair This is my paper · ORCID
classification math.OCcs.LG
keywords neighborhoodassignmentlargesearchpolicytimesapplicationsapproach
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

Large Neighborhood Search (LNS) is a combinatorial optimization heuristic that starts with an assignment of values for the variables to be optimized, and iteratively improves it by searching a large neighborhood around the current assignment. In this paper we consider a learning-based LNS approach for mixed integer programs (MIPs). We train a Neural Diving model to represent a probability distribution over assignments, which, together with an off-the-shelf MIP solver, generates an initial assignment. Formulating the subsequent search steps as a Markov Decision Process, we train a Neural Neighborhood Selection policy to select a search neighborhood at each step, which is searched using a MIP solver to find the next assignment. The policy network is trained using imitation learning. We propose a target policy for imitation that, given enough compute resources, is guaranteed to select the neighborhood containing the optimal next assignment amongst all possible choices for the neighborhood of a specified size. Our approach matches or outperforms all the baselines on five real-world MIP datasets with large-scale instances from diverse applications, including two production applications at Google. It achieves $2\times$ to $37.8\times$ better average primal gap than the best baseline on three of the datasets at large running times.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 9 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs

    cs.LG 2025-08 unverdicted novelty 6.0 of 10

    SPL-LNS replaces the greedy proposal step in neural Large Neighborhood Search with sampling over locally-informed proposals, trained by hindsight relabeling on self-generated data, and reports large gains over prior n...

  2. Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem

    cs.AI 2024-12 conditional novelty 6.0 of 10

    Balans uses online multi-armed bandits to adaptively choose among large-neighborhood search operators on top of a MIP solver, reporting large primal gap improvements over default SCIP and Gurobi on hard instances with...

  3. RL-SPH: Learning to Achieve Feasible Solutions for Integer Linear Programs

    cs.LG 2024-11 unverdicted novelty 6.0 of 10

    RL-SPH is a reinforcement learning start primal heuristic that independently produces feasible solutions for ILPs with non-binary integers at 100% rate and with 28.6× lower primal gap than prior start heuristics.

  4. Learning optimal objective values for MILP

    math.OC 2024-11 conditional novelty 6.0 of 10

    A graph neural network predicts MILP optimal objective values, and dynamic solver features improve detection of when the current incumbent is optimal.

  5. Uncovering expert objectives in production planning via inverse optimization: An industrial case study

    math.OC 2026-08 conditional novelty 5.0 of 10

    Inverse optimization of a mixed-integer production planning model on 50 training plans reveals that Dow planners weight avoiding understock and stable cycle lengths most heavily.

  6. Self-Improving Neural Pruning: A Graph Neural Network Framework for Scalable Mixed Bundle Pricing

    cs.LG 2025-09 conditional novelty 5.0 of 10

    A GNN-guided pruning framework predicts customer-product assignment probabilities and solves a restricted mixed-bundling MILP, reporting 97-99% of optimal revenue on small instances and faster large-scale solutions.

  7. Code Retrieval for MILP Instance Generation

    math.OC 2025-05 reject novelty 5.0 of 10

    Code retrieval from a pre-built MILP library can generate new instances similar to a target, but the paper's evidence is weakened by using the retrieval metric as the evaluation metric.

  8. SORREL: Suboptimal-Demonstration-Guided Reinforcement Learning for Learning to Branch

    cs.LG 2024-12 conditional novelty 5.0 of 10

    SORREL combines offline reinforcement learning on suboptimal demonstrations with self-imitation finetuning to learn branching policies that match expert-trained solvers.

  9. Mixed-Integer Linear Optimization via Learning-Based Two-Layer Large Neighborhood Search

    math.OC 2024-12 conditional novelty 5.0 of 10

    Recursively applying large neighborhood search to its own auxiliary MILPs, guided by a graph transformer, finds good solutions faster than one-layer LNS and standard solvers on four large MILP benchmarks.

Pith tools