When solving hard multicommodity network flow problems using an LP-based approach, the number of commodities is a driving factor in the speed at which the LP can be solved, as it is linear in the number of constraints and variables. The conventional approach to improve the solve time of the LP relaxation of a Mixed Integer Programming (MIP) model that encodes such an instance is to aggregate all commodities that have the same origin or the same destination. However, the bound of the resulting LP relaxation can significantly worsen, which tempers the efficiency of aggregating techniques. In this paper, we introduce the concept of partial aggregation of commodities that aggregates commodities over a subset of the network instead of the conventional aggregation over the entire underlying network. This offers a high level of control on the trade-off between size of the aggregated MIP model and quality of its LP bound. We apply the concept of partial aggregation to two different MIP models for the multicommodity network design problem. Our computational study on benchmark instances confirms that the trade-off between solve time and LP bound can be controlled by the level of aggregation, and that choosing a good trade-off can allow us to solve the original large-scale problems faster than without aggregation or with full aggregation.


翻译:在采用基于LP的方法解决硬多通性网络流动问题时,商品的数量是一个驱动因素,因为它是制约和变量数量的线性,因此是解决LP速度的一个驱动因素,因为它是限制和变量数量的线性。改进LP放松混合整数编程模式(混合整数编程模式)的解决时间的常规办法,将这种模式编码起来,就是将所有来源相同或目的地相同的商品合并起来。然而,由此产生的LP放松的界限会大大恶化,从而抑制集成技术的效率。在本文中,我们引入了将商品比网络的一个子集成起来,而不是对整个基本网络进行常规集成的商品部分合并的概念。这为综合综合的MIP模式的大小与LP所约束的质量之间的权衡提供了高度的控制。我们对多通度网络设计问题的两个不同的MIP模式适用部分合并的概念。我们对基准实例的计算研究证实,解决时间和LP约束之间的权衡可以受集成水平的控制,而选择一个良好的贸易模式可以使我们不比全面合并更快地解决原型或总合。

0
下载
关闭预览

相关内容

Networking:IFIP International Conferences on Networking。 Explanation:国际网络会议。 Publisher:IFIP。 SIT: http://dblp.uni-trier.de/db/conf/networking/index.html
商业数据分析,39页ppt
专知会员服务
160+阅读 · 2020年6月2日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
【推荐】Python机器学习生态圈(Scikit-Learn相关项目)
机器学习研究会
6+阅读 · 2017年8月23日
Arxiv
0+阅读 · 2021年3月4日
Arxiv
4+阅读 · 2019年1月14日
Arxiv
4+阅读 · 2018年2月19日
VIP会员
相关VIP内容
商业数据分析,39页ppt
专知会员服务
160+阅读 · 2020年6月2日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Top
微信扫码咨询专知VIP会员