A Decomposition-Based Pricing Procedure for Large-Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem
提出并测试了一种新的定价过程，通过交互求解松弛子问题来识别进入基的列，减少求解大规模结构化线性规划所需的枢轴次数，并在两组多商品流问题（电信路由和物流）上验证了效果。
We propose and test a new pricing procedure for solving large-scale structured linear programs. The procedure interactively solves a relaxed subproblem to identify potential entering basic columns. The subproblem is chosen to exploit special structure, rendering it easy to solve. The effect of the procedure is the reduction of the number of pivots needed to solve the problem. Our approach is motivated by the column-generation approach of Dantzig-Wolfe decomposition. We test our procedure on two sets of multicommodity flow problems. One group of test problems arises in routing telecommunications traffic and the second group is a set of logistics problem which have been widely used to test multicommodity flow algorithms.