A Primal Partitioning Solution for the Arc-Chain Formulation of a Multicommodity Network Flow Problem
A Primal Partitioning Solution for the Arc-Chain Formulation of a Multicommodity Network Flow Problem
复制标题
DOI：
10.1287/opre.41.4.669
复制
发表时间：
1993-07
期刊：
影响因子：
--
通讯作者：
J. Farvolden;Warrren B Powell;I. Lustig
中科院分区：
文献类型：
--
作者：
J. Farvolden;Warrren B Powell;I. Lustig
提出了一种新的基于原始划分和分解技术的多商品网络流问题的求解方法，简化了单纯形法所需的计算量。这种划分是在MCNF的弧链关联矩阵上进行的，类似于在Dantzig-Wolfe分解中产生的主问题的约束矩阵的变量变化，以分离出一个非常稀疏的、维度大大降低的近三角工作基。在分区的基础上执行的大多数单工操作只是针对所确定的九种可能的数据透视表类型的加法和网络操作。弧链关联矩阵的列由对偶网络单纯形法生成，用于在链路成本变化时更新最短路径。
We present a new solution approach for the multicommodity network flow problem (MCNF) based upon both primal partitioning and decomposition techniques, which simplifies the computations required by the simplex method. The partitioning is performed on an arc-chain incidence matrix of the MCNF, similar within a change of variables to the constraint matrix of the master problem generated in a Dantzig-Wolfe decomposition, to isolate a very sparse, near-triangular working basis of greatly reduced dimension. The majority of the simplex operations performed on the partitioned basis are simply additive and network operations specialized for the nine possible pivot types identified. The columns of the arc-chain incidence matrix are generated by a dual network simplex method for updating shortest paths when link costs change.