关键词: 多商品流, 成本上涨, 列生成

Abstract: A nonlinear programming model maximizing profits was established for the traditional multi-commodity network flow problem by considering cost rising constraint.With introduction of a node price variable,the nonlinear model was decomposed into a linear restricted master problem and a quadratic programming subproblem,and a column generation algorithm was designed to solve it.For the quadratic programming subproblem,the redundant circles were eliminated by dynamic adding constraints.Computational results showed that the algorithm had great potential in solving the multi-commodity network flow problem by considering cost rising constraint.

Key words: multi-commodity network flow, cost rising, column generation