A PRIMAL PARTITIONING SOLUTION FOR THE ARC-CHAIN FORMULATION OF A MULTICOMMODITY NETWORK FLOW PROBLEM
成果类型：
Article
署名作者：
FARVOLDEN, JM; POWELL, WB; LUSTIG, IJ
署名单位：
Princeton University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.41.4.669
发表日期：
1993
页码：
669-693
关键词：
摘要：
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.