An Improved Reinforcement Learning Algorithm for Learning to Branch

Most combinatorial optimization problems can be formulated as mixed integer linear programming (MILP), in which branch-and-bound (B\&B) is a general and widely used method. Recently, learning to branch has become a hot research topic in the intersection of machine learning and combinatorial opti...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-01
Main Authors: Qu, Qingyu, Li, Xijun, Zhou, Yunfan, Zeng, Jia, Yuan, Mingxuan, Wang, Jie, Lv, Jinhu, Liu, Kexin, Mao, Kun
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Integer programming
Linear programming
Machine learning
Mixed integer
Mixing ratio
Optimization
Performance enhancement
Performance evaluation
Training
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Most combinatorial optimization problems can be formulated as mixed integer linear programming (MILP), in which branch-and-bound (B\&B) is a general and widely used method. Recently, learning to branch has become a hot research topic in the intersection of machine learning and combinatorial optimization. In this paper, we propose a novel reinforcement learning-based B\&B algorithm. Similar to offline reinforcement learning, we initially train on the demonstration data to accelerate learning massively. With the improvement of the training effect, the agent starts to interact with the environment with its learned policy gradually. It is critical to improve the performance of the algorithm by determining the mixing ratio between demonstration and self-generated data. Thus, we propose a prioritized storage mechanism to control this ratio automatically. In order to improve the robustness of the training process, a superior network is additionally introduced based on Double DQN, which always serves as a Q-network with competitive performance. We evaluate the performance of the proposed algorithm over three public research benchmarks and compare it against strong baselines, including three classical heuristics and one state-of-the-art imitation learning-based branching algorithm. The results show that the proposed algorithm achieves the best performance among compared algorithms and possesses the potential to improve B\&B algorithm performance continuously.
ISSN:2331-8422