Research map / Learning theory and algorithms / Combinatorial and search optimization

BTBS-LNS: Binarized-Tightening, Branch and Search on Learning LNS Policies for MIP

ICLR 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Heuristic and local search algorithms

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes BTBS-LNS, a learned LNS policy for MIP that uses binarized tightening and branch-and-search to avoid prematurely fixing important variables and escape local optima.

Problem

Policy-learning-based Large Neighborhood Search for large-scale Mixed Integer Programs often has a limited explored space, so the learned policy may wrongly fix potentially important variables early, leading to local optima.

Approach

Combines binarized tightening with branch-and-search inside learned LNS so the explored neighborhood space is expanded rather than fixing variables irrevocably early in the search.

Experimental setup

Builds on: large neighborhood search policy learning for LNS

Closest papers by meaning

• Learning Large Neighborhood Search Policy for Integer Programming (NeurIPS 2021 · similarity 0.89)
• Generalization Guarantees for Learning Score-Based Branch-and-Cut Policies in Integer Programming (NeurIPS 2025 · similarity 0.88)
• Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems (ICML 2025 · similarity 0.87)
• Search Strategy Generation for Branch and Bound Using Genetic Programming (AAAI 2025 · similarity 0.86)
• BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks (NeurIPS 2025 · similarity 0.86)
• Predicting Lagrangian Multipliers for Mixed Integer Linear Programs (ICML 2024 · similarity 0.85)