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.


翻译:分节和分界线是组合优化的系统统计方法,其性能高度依赖变量选择战略。 最先进的手工制作的超光速战略每个选择的推算时间相对缓慢,而目前的机器学习方法需要大量贴标签数据。 我们提出一种新的方法来解决组合优化中的数据标签和推论延绳问题,基于使用强化学习(RL)范式。 我们用模仿学习来诱导一个RL代理,然后使用Proximal政策优化(PPPO)来进一步探索全球最佳行动。 然后,我们使用一个价值网络来运行蒙特卡洛树搜索(MCTS),以加强政策网络。 我们评估了我们方法在四种不同类型组合优化问题上的性能,并表明我们的方法与最先进的机器学习和超光学方法相比表现很强。

0
下载
关闭预览

相关内容

【2022新书】强化学习工业应用,408页pdf
专知会员服务
226+阅读 · 2022年2月3日
【强化学习资源集合】Awesome Reinforcement Learning
专知会员服务
93+阅读 · 2019年12月23日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
3+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
66+阅读 · 2022年4月13日
A Multi-Objective Deep Reinforcement Learning Framework
VIP会员
相关VIP内容
【2022新书】强化学习工业应用,408页pdf
专知会员服务
226+阅读 · 2022年2月3日
【强化学习资源集合】Awesome Reinforcement Learning
专知会员服务
93+阅读 · 2019年12月23日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
【ICIG2021】Latest News & Announcements of the Industry Talk1
中国图象图形学学会CSIG
0+阅读 · 2021年7月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
3+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员