We consider a linear relaxation of a generalized minimum-cost network flow problem with binary input dependencies. In this model the flows through certain arcs are bounded by linear (or more generally, piecewise linear concave) functions of the flows through other arcs. This formulation can be used to model interrelated systems in which the components of one system require the delivery of material from another system in order to function (for example, components of a subway system may require delivery of electrical power from a separate system). We propose and study randomized rounding schemes for how this model can be used to approximate solutions to a related mixed integer linear program for modeling binary input dependencies. The introduction of side constraints prevents this problem from being solved using the well-known network simplex algorithm, however by characterizing its basis structure we develop a generalization of network simplex algorithm that can be used for its {computationally} efficient solution.


翻译:我们认为,在二元输入依赖性下,普遍的最低成本网络流量问题可以直线放松。在这个模型中,通过某些弧流的流量受通过其他弧流的线性(或更一般地说,小线性线性线性线性)功能的约束。这一配方可用于模拟相互关联的系统,其中,一个系统的部件需要从另一个系统交付材料才能运作(例如,地铁系统的部件可能需要从一个单独的系统交付电力)。我们建议并研究随机四舍五入的组合办法,以了解如何利用这一模型来大致解决一个相关的混合整数线性程序,以模拟二元输入依赖性。由于引入侧面限制,这一问题无法通过众所周知的网络简单算法来解决,然而,通过描述其基础结构,我们开发了网络简单算法的通用化,可用于[投入 有效解 。

0
下载
关闭预览

相关内容

【2021新书】高阶网络,150页pdf,Higher-Order Networks
专知会员服务
87+阅读 · 2021年11月26日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2022年1月24日
Arxiv
0+阅读 · 2022年1月24日
VIP会员
相关VIP内容
【2021新书】高阶网络,150页pdf,Higher-Order Networks
专知会员服务
87+阅读 · 2021年11月26日
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
相关资讯
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员