4-02 15,934PVs
最近看网路优化方面的资料，有很多不清楚的名词。今天记录一下多商品流问题。英文叫做multicommodity flow problem/solution。多商品流问题是网络优化问题中的一个，网络优化对于研究Network领域的科研人员来说，我认为是比较有用的一个数学类别。
近期我会更新一些网络优化问题的文章，适合Computer Science和Network研究人员阅读。普通的人请忽略吧，因为阅读难度挺大的。今天主要记录网络优化问题。网路的主要作用是将业务从源端运送到目的端。为了充分利用网路资源，例如：线路、转接设备，人们总是希望合理地分配流量，以是从源端到目的端的流量尽可能大，传输的代价尽可能小。但网路内流量分配并不是任意的，它受限于网络的拓扑结构，边和端的容量及费用，另外还有其他的限制，例如时延、吞吐量等。在通信领域可能还要考虑Qos。
如果将网络中节点间业务看作是一个流的话，为满足一对接点之间的业务需求而涉及业务流路径带宽分配被称作为但商品流问题。然而，现实生活中，我们要面对的并不是特定的节点对，而是多节点对之间的最优话线性规划建模方法。
多商品流有多个研究方向，主要陈述多商品流的最佳路由负载均衡问题。多商品流的负载均衡问题可以描述为下：给定一个通信网络拓扑图G(V,E)，其中V表示的是所有节点的集合，E表示所有链路的集合，G(V,E)表示整个拓扑。接下来给定部分或者全部节点对之间的流量需求，(1)共计K个这样的需求，编号k=1,2,…,K (2)第k个需求的大小为hk,第k个需求下的源端点和宿端点分别为sk和dk。除了源宿端点外的其他节点，比如节点i,用vi表示；lij表示节点i和j之间的链路边；第k个需求下lij的边上的流量用xijk表示。另外，网络拓扑中每条边上的单位流量代价为Cij边的带宽即容量为uij。目标函数最小化最大链路利用率Z。
多商品流最佳路由一般问题（注意，并不是负载均衡问题）要求是为所有的需求寻找合适的路径，并且要求目标函数达到最优，这里的优化目标不是上述的链路利用率Z。而是所有K个业务的流量总代价，即最小化流量代价之和。
最佳路由一般问题的线性规划建模如下图:
f(x)等于下图所示的公式：
第一行的约束条件表示在认识k个业务需求hk下流出源点和流入宿点的流量约束。第三行是除了源点和宿点之外的其他节点在任意k个业务下的流入流量等于流出流量的约束。第四个表达式是每条边lij上在所有k个业务下的总流量满足小于等于这条边所对应的容量的约束。最后一行表达式是在任意k个业务下每条边的流量必须大于等于0的约束。求解出的x就是每条链路上应该分配的流量。这样就解决了多商品流最佳路由问题的线性规划。通过计算可得最佳路由。但是这个解未考虑负载均衡。
最佳路由负载均衡问题的线性规划模型改变了目标函数和约束条件。如下：
图中标红的部分为修改的部分，结合前文的叙述，不难理解这里的含义。
说到这里，我想起了13年的Infocomm《Traffic Engineering in Software Defined Networks》文中的数学模型。
和这个数学模型有异曲同工之妙。
下面叙述这个问题的对偶问题。引入对偶变量p(流守恒约束)和q(容量约束)。可将上述多商品流负载均衡问题的约束条件变为对偶形式，并化简如下：
添加对p和q的约束，即q《=0,p 任意。等式第一行为对偶问题的目标函数；第二行由于原问题中z为自由变量，所以该项系数必须等于0；第三行由于原问题xijk可以取正无穷大，来使等式左端达到最小，这显然是与原问题相悖的。令rij=-qij，可得：
假定主问题的最佳解中，xijk取值大于0，根据互补松弛定理可知，其对应对偶约束取等号，即：pjk-pik+rij=0。只考虑特定的需求k，其流变量取值大于0的边构成一些路径，如上第二图所示。只看其中一条路径，例如sabt可得中间的三个等式。对三个等式做求和，以rij为权重，该路径长度(权重之和)等于ps-pt。观察路径sbt可得后面两个式子，同样以rij为权重，路径长度(权重之和)大于等于ps-pt。对比两条路径，发现达到最优解的路径比其他路径的长度要短，也就是说该问题的最佳解实际上就在最短路上。而最短路的算法与负载均衡问题相比更容易实现。原本复杂的负载均衡问题，转化成对偶问题，只要给出合适的权重rij,原问题就能转化成对偶问题，然后通过最短路算法可求的最佳解。注意，即使得到了最佳权重，沿着最短路安排流量也不完全等价于原问题的最佳解。这是因为对偶问题其实并没有得到原问题所要求的分流比例信息，也就是并没有得到链路利用率。对偶解可以看作是对原最佳解的近似。
反观，13年infocomm问题，现在就能够理解作者的意图了。也是把流量分配比例，转化为流量分配，在转化为对偶问题（最短路问题）：
给定非负链路权重则可以利用松弛互补原理对应一个约束取等号。在忽略正确性验证的基础上，这篇INFOCOM的思路也就有了理解。
天啦，这是什么·····
科研。。哎，读博士的不归路。。。
多商品流问题的模型和求解 可以推荐几篇论文吗 现在正在做这个
我也看的比较少呢，抱歉
你好，同求推荐文章，你还在看这方面吗
已经不看了~抱歉
接触过一些凸优化问题，对进行对偶问题转化过程搞不懂。。。再应用到网络拓扑的建模上。。。。俨然从工程大牛转变成学术大牛了！
大牛什么呀，看这个我也头疼呢，但是还得硬着头皮看，哎
牛~~~~~~
Jevy 那个问题你最后看明白了？？
（我是rujie）
我大概看明白作者的意思和思路了。但是没有具体动手计算。:)
看到这些符号想起了之前的数学建模
就是数学建模呀。你以前弄过？
我最近也在尝试用NS2对这个问题进行仿真，能交流交流吗？我的QQ695852668
已添加~
膜拜大神
嘿嘿嘿，大神不敢当
已晕。。。 😕
确实很理论，13年的infocom
有没有这样的一类图论问题，将一个子图映射到一个大图上，满足一定的约束条件（节点约束，边约束），使得某个优化目标最优（比如图尽可能相似等）？在寻找这一类的模型
二部图匹配？
憋硕士论文正愁找不到多商品流的东西，感谢大佬的文章指点迷津
不客气，嘿嘿
发了一篇文章就是这方面的
是呀，如果想就交流可以和我邮箱联系
你好，我知道的有：MCF中的最大流问题可通过转换为最短路径问题，您这里提及的MCF中的最小代价问题经过转换为最佳负载均衡也可以转为最短路径问题，我想问的是如果我只是想求解MCF中的最小代价而不是最佳负载均衡问题，可以转为最短路径问题吗?可以的话怎么转？感激不尽。
理论上讲只要优化目标是加性的，都可以转化成最短路问题。
我想请教一下大牛，你讲的那个”引入对偶变量p(流守恒约束)和q(容量约束)。可将上述多商品流负载均衡问题的约束条件变为对偶形式，并化简如下：“这部分看不明白，有哪些资料介绍过这种方法吗？求推荐一下，本人硕士在读，对我来说这些问题好难啊，求大牛指点迷津~~ 😕 😕
我也是看一篇论文里提到的。。。
你好，看了你的这篇文章觉得收益很多，最近在研究这个问题头都打了，投石无路，随便搜搜之后看到你的文章，觉得眼前一亮瞬间已经绝望的心又澎湃了。不知道现在留言你还能看得到吗？想向你请教点问题，上述你的问题描述中x是流量是连续变量，而现在模型与约束条件基本一致，但是我的x是（0或者1）变量，是知道是否占用了链路的意思。不知道这个要怎么套用这个方法，请大神指教，谢谢，谢谢。
呀，如果是急事你可以给我发邮件，我会回复的更快一点，我好久没打理网站了。0-1变量这种情况是你要么选这条路要么不选，我感觉没有必要变为最短路问题，真篇文章的思想是要利用最短路的算法求解原对偶的优化问题。你的情况是，x可行域是整形，求解算法你甚至可以不用拉格朗日一类的。解空间不大的话，自己写个遍历算法就好了，个人感觉没必要生搬硬套一个高大上的算法。
哇，跟我们老师讲的很像哎，甚至你写的更细致
谢谢！
请问您对使用MIP解决MCF问题了解吗？如果可以，希望和您交流一下。我的QQ1642174485，谢谢您
最近也遇到一些MCF问题，表示无解，请问能和您交流一下嘛？我的qq1642174485,谢谢
好呀，我加你了
楼主，我最近在看这个算法，有问题想请教您一下，是转化成对偶权重 然后把流量放如网络中？然后就用放进去的流量除以容量求最大链路的利用率吗？ 这个就是最终的结果吗
嗯，很久以前看的了
第一个约束的第二项，求和符号下面的k应该是s^k。
第二个约束有类似的错误