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

摘要： 针对传统的多商品流问题,引入成本上涨因素,建立了最大化利润的非线性规划模型。通过引入节点价格变量,将非线性模型分解为线性主问题和二次规划子问题,设计相应的列生成算法来求解。对于二次规划子问题,通过动态添加破圈约束来消除冗余圈的存在。通过算例测试表明,该算法在解决考虑成本上涨的多商品流问题方面具有很大的潜力。

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