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

Abstract: A nonlinear programming model maximizing profits is established for the traditional Multi- commodity network flow problem considering cost rising constraint.By introducing a node price variable,the nonlinear model is decomposed into a linear restricted master problem and a quadratic programming subproblem and then a column generation algorithm is designed to solve it.For the quadratic programming subproblem,redundant circles are eliminated by dynamically adding constraints.Computational results show that the algorithm has great potential in solving the Multi-commodity network flow problem considering cost rising constraint.

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