Improving Learning to Branch via Reinforcement Learning

2021-01-01 · NeurIPS Workshop LMCA 2020 12 · Haoran Sun, Wenbo Chen, Hui Li, Le Song

Branch-and-Bound~(B\&B) is a general and widely used algorithm paradigm for solving Mixed Integer Programming~(MIP). Recently there is a surge of interest in designing learning-based branching policies as a fast approximation of strong branching, a human-designed heuristic. In this work, we argue strong branching is not a good expert to imitate for its poor decision quality when turning off its side effects in solving linear programming. To obtain more effective and non-myopic policies than a local heuristic, we formulate the branching process in MIP as reinforcement learning~(RL) and design a policy characterization for the B\&B process to improve our agent by novelty search evolutionary strategy. Across a range of NP-hard problems, our trained RL agent significantly outperforms expert-designed branching rules and the state-of-the-art learning-based branching methods in terms of both speed and effectiveness. Our results suggest that with carefully designed policy networks and learning algorithms, reinforcement learning has the potential to advance algorithms for solving MIPs.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Branching Reinforcement Learning

2022-02-16 · Yihan Du, Wei Chen

In this paper, we propose a novel Branching Reinforcement Learning (Branching RL) model, and investigate both Regret Minimization (RM) and Reward-Free Exploration (RFE) metrics for this model. Unlike standard RL where th…

LEMMA Recommendation Systems reinforcement-learning Reinforcement Learning+1

Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization

2025-11-12 · Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan 외 arxiv

Mixed-Integer Linear Programming (MILP) lies at the core of many real-world combinatorial optimization (CO) problems, traditionally solved by branch-and-bound (B&B). A key driver influencing B&B solvers efficiency is the…

Reinforcement Learning

Branch Prediction as a Reinforcement Learning Problem: Why, How and Case Studies

2021-06-25 · Anastasios Zouzias, Kleovoulos Kalaitzidis, Boris Grot

Recent years have seen stagnating improvements to branch predictor (BP) efficacy and a dearth of fresh ideas in branch predictor design, calling for fresh thinking in this area. This paper argues that looking at BP from …

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

TreeDQN: Learning to minimize Branch-and-Bound tree

2023-06-09 · Dmitry Sorokin, Alexander Kostin

Combinatorial optimization problems require an exhaustive search to find the optimal solution. A convenient approach to solving combinatorial optimization tasks in the form of Mixed Integer Linear Programs is Branch-and-…

Combinatorial Optimization reinforcement-learning Reinforcement Learning Variable Selection

Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm

2020-05-20 · Marc Etheve, Zacharie Alès, Côme Bissuel, Olivier Juan 외

Mixed integer linear programs are commonly solved by Branch and Bound algorithms. A key factor of the efficiency of the most successful commercial solvers is their fine-tuned heuristics. In this paper, we leverage patter…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Variable Selection