An Improved Reinforcement Learning Algorithm for Learning to Branch
This work addresses the challenge of learning to branch in mixed integer linear programming, which is incremental as it builds on existing reinforcement learning approaches with specific enhancements for robustness and data mixing.
The paper tackles the problem of improving branch-and-bound algorithms for combinatorial optimization by proposing a reinforcement learning-based method that uses a prioritized storage mechanism to balance demonstration and self-generated data, achieving the best performance on three benchmarks compared to classical heuristics and a state-of-the-art imitation learning baseline.
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.