Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch
Branch-and-bound is a systematic enumerative method for combinatorial
optimization, where the performance highly relies on the variable selection
strategy. State-of-the-art handcrafted heuristic strategies suffer from
relatively slow inference time for each selection, while the current machine
learning methods require a significant amount of labeled data. We propose a new
approach for solving the data labeling and inference latency issues in
combinatorial optimization based on the use of the reinforcement learning (RL)
paradigm. We use imitation learning to bootstrap an RL agent and then use
Proximal Policy Optimization (PPO) to further explore global optimal actions.
Then, a value network is used to run Monte-Carlo tree search (MCTS) to enhance
the policy network. We evaluate the performance of our method on four different
categories of combinatorial optimization problems and show that our approach
performs strongly compared to the state-of-the-art machine learning and
heuristics based methods.