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.

本文提出一种基于强化学习的方法用于解决组合优化中的数据标记和推理延迟问题，并使用蒙特卡罗树搜索和价值网络提高策略网络的性能表现。作者在四种不同类别的组合优化问题上进行了评估，结果表明该方法相较于现有机器学习和启发式方法有更优的性能表现。

精确组合优化的深度强化学习：学习分支