The expressive and computationally inexpensive bipartite Graph Neural Networks (GNN) have been shown to be an important component of deep learning based Mixed-Integer Linear Program (MILP) solvers. Recent works have demonstrated the effectiveness of such GNNs in replacing the branching (variable selection) heuristic in branch-and-bound (B&B) solvers. These GNNs are trained, offline and on a collection of MILPs, to imitate a very good but computationally expensive branching heuristic, strong branching. Given that B&B results in a tree of sub-MILPs, we ask (a) whether there are strong dependencies exhibited by the target heuristic among the neighboring nodes of the B&B tree, and (b) if so, whether we can incorporate them in our training procedure. Specifically, we find that with the strong branching heuristic, a child node's best choice was often the parent's second-best choice. We call this the "lookback" phenomenon. Surprisingly, the typical branching GNN of Gasse et al. (2019) often misses this simple "answer". To imitate the target behavior more closely by incorporating the lookback phenomenon in GNNs, we propose two methods: (a) target smoothing for the standard cross-entropy loss function, and (b) adding a Parent-as-Target (PAT) Lookback regularizer term. Finally, we propose a model selection framework to incorporate harder-to-formulate objectives such as solving time in the final models. Through extensive experimentation on standard benchmark instances, we show that our proposal results in up to 22% decrease in the size of the B&B tree and up to 15% improvement in the solving times.


翻译:显性且计算成本低廉的双面图形神经网络( GNN) 已被证明是深深学习的混合 Interger 线性程序( MILP) 解决方案的重要组成部分。 最近的工作已经证明这些GNN在替换分支和离线( B&B) 解决方案中分支( 可变选择) 的杂交。 这些 GNN是经过培训的, 离线的, 以及集成的 MILP 组合, 以模仿一个非常好但计算成本昂贵的分支超常、 强的分支。 鉴于 B&B在亚双向 MILP 树树上的结果, 我们问 (a) 这些G&B树的相邻节性点之间是否有很强的关联性( 可变式选择) 替换分支( 可变式选择) 。 具体地说, 我们发现, 随着强大的分流性, 儿童节制, 最优的选择往往是母体的第二最优框架。 我们称之为“ 向回看” 现象。 令人惊讶的是, 直观的BAT 目标在常规定义中往往将GNNS 格式显示“ 格式中的简单的版本” 格式 。

0
下载
关闭预览

相关内容

专知会员服务
123+阅读 · 2020年9月8日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
159+阅读 · 2020年3月18日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
76+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
【推荐】深度学习目标检测全面综述
机器学习研究会
21+阅读 · 2017年9月13日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
2+阅读 · 2009年12月31日
Deep Learning for Choice Modeling
Arxiv
0+阅读 · 2022年8月19日
Arxiv
0+阅读 · 2022年8月19日
Arxiv
21+阅读 · 2022年2月24日
Learning in the Frequency Domain
Arxiv
11+阅读 · 2020年3月12日
Arxiv
14+阅读 · 2019年9月11日
VIP会员
相关VIP内容
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
VCIP 2022 Call for Special Session Proposals
CCF多媒体专委会
1+阅读 · 2022年4月1日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
AIART 2022 Call for Papers
CCF多媒体专委会
1+阅读 · 2022年2月13日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
【推荐】深度学习目标检测全面综述
机器学习研究会
21+阅读 · 2017年9月13日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
2+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员