Machine Learning (ML) can help solve combinatorial optimization (CO) problems better. A popular approach is to use a neural net to compute on the parameters of a given CO problem and extract useful information that guides the search for good solutions. Many CO problems of practical importance can be specified in a matrix form of parameters quantifying the relationship between two groups of items. There is currently no neural net model, however, that takes in such matrix-style relationship data as an input. Consequently, these types of CO problems have been out of reach for ML engineers. In this paper, we introduce Matrix Encoding Network (MatNet) and show how conveniently it takes in and processes parameters of such complex CO problems. Using an end-to-end model based on MatNet, we solve asymmetric traveling salesman (ATSP) and flexible flow shop (FFSP) problems as the earliest neural approach. In particular, for a class of FFSP we have tested MatNet on, we demonstrate a far superior empirical performance to any methods (neural or not) known to date.


翻译:机器学习(ML) 能够帮助更好地解决组合优化(CO)问题。 流行的方法是使用神经网来计算特定CO问题参数,并提取有用的信息来指导寻找好的解决办法。 许多具有实际重要性的CO问题可以以矩阵形式具体列出,以量化两组项目之间的关系。 但是,目前还没有神经网模型,以这种矩阵式关系数据作为输入。因此,ML工程师无法接触到这些类型的CO问题。 在本文中,我们引入了矩阵编码网络(MatNet),并展示它如何方便地进入和处理复杂的CO问题的参数。我们使用基于 MatNet 的端到端模型,解决不对称旅行销售员(ATSP)和灵活的流动商店(FFSP)问题,作为最早的神经学方法。 特别是,我们测试了某类FFSP的MatNet,我们对已知的任何方法(神经或非神经学方法)都表现出非常优秀的经验性。

0
下载
关闭预览

相关内容

【图与几何深度学习】Graph and geometric deep learning,49页ppt
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
AI/ML/DNN硬件加速设计怎么入门?
StarryHeavensAbove
10+阅读 · 2018年12月4日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
NIPS 2017:贝叶斯深度学习与深度贝叶斯学习(讲义+视频)
机器学习研究会
36+阅读 · 2017年12月10日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】卷积神经网络类间不平衡问题系统研究
机器学习研究会
6+阅读 · 2017年10月18日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年12月23日
Arxiv
6+阅读 · 2021年6月4日
Arxiv
19+阅读 · 2020年7月13日
Arxiv
27+阅读 · 2020年6月19日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Arxiv
26+阅读 · 2018年2月27日
VIP会员
相关资讯
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
AI/ML/DNN硬件加速设计怎么入门?
StarryHeavensAbove
10+阅读 · 2018年12月4日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
NIPS 2017:贝叶斯深度学习与深度贝叶斯学习(讲义+视频)
机器学习研究会
36+阅读 · 2017年12月10日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】卷积神经网络类间不平衡问题系统研究
机器学习研究会
6+阅读 · 2017年10月18日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】TensorFlow手把手CNN实践指南
机器学习研究会
5+阅读 · 2017年8月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Arxiv
0+阅读 · 2021年12月23日
Arxiv
6+阅读 · 2021年6月4日
Arxiv
19+阅读 · 2020年7月13日
Arxiv
27+阅读 · 2020年6月19日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Arxiv
26+阅读 · 2018年2月27日
Top
微信扫码咨询专知VIP会员