This paper addresses the problem of determining all optimal integer solutions of a linear integer network flow problem, which we call the all optimal integer flow (AOF) problem. We derive an O(F (m + n) + mn + M ) time algorithm to determine all F many optimal integer flows in a directed network with n nodes and m arcs, where M is the best time needed to find one minimum cost flow. We remark that stopping Hamacher's well-known method for the determination of the K best integer flows at the first sub-optimal flow results in an algorithm with a running time of O(F m(n log n + m) + M ) for solving the AOF problem. Our improvement is essentially made possible by replacing the shortest path sub-problem with a more efficient way to determine a so called proper zero cost cycle using a modified depth-first search technique. As a byproduct, our analysis yields an enhanced algorithm to determine the K best integer flows that runs in O(Kn3 + M ). Besides, we give lower and upper bounds for the number of all optimal integer and feasible integer solutions. Our bounds are based on the fact that any optimal solution can be obtained by an initial optimal tree solution plus a conical combination of incidence vectors of all induced cycles with bounded coefficients.


翻译:本文涉及确定线性整网流问题所有最佳整数解决方案的问题,我们称之为所有最佳整数流问题。我们用O(F(nlog n+m)+m +M)时间算法来确定有n节点和 m Arcs 的定向网络中所有F(m)+n+m+M)最佳整数流。M是找到一个最低成本流的最佳时间。我们指出,在第一个次最佳流中,阻止哈马赫确定K最佳整数流的著名方法的结果是,一种运行时间为O(F(nlog n+m)+M)的算法,用于解决AOO(F(nlog n+m)+m +M)的问题。我们之所以能够作出改进,基本上是通过以更有效的方法取代最短路径次整数的次整数,从而确定所谓的适当零费用循环,使用经修改的深度第一搜索技术。作为副产品,我们的分析产生一种更先进的算法,用以确定在O(K3+M)中运行的K最佳整数流。此外,我们对所有最佳整数的最佳整数和最可行的整数的混合的混合解决办法都具有约束性。

0
下载
关闭预览

相关内容

专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
81+阅读 · 2021年5月10日
专知会员服务
22+阅读 · 2021年4月10日
专知会员服务
12+阅读 · 2021年3月13日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Adversarial Variational Bayes: Unifying VAE and GAN 代码
CreateAMind
7+阅读 · 2017年10月4日
Arxiv
0+阅读 · 2021年7月11日
VIP会员
相关VIP内容
专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
81+阅读 · 2021年5月10日
专知会员服务
22+阅读 · 2021年4月10日
专知会员服务
12+阅读 · 2021年3月13日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
Top
微信扫码咨询专知VIP会员