Solution of Large-Scale Multicommodity Network Flow Problems via a Logarithmic Barrier Function Decomposition

摘要

A new algorithm is presented using a logarithmic barrier function decomposition for the solution of the large-scale multicommodity network flow problem. Placing the complicating joint capacity constraints of the multicommodity network flow problem into a logarithmic barrier term of the objective function creates a nonlinear mathematical program with linear network flow constraints. Using the technique of restricted simplicial decomposition, we generate a sequence of extreme points by solving independent pure network problems for each commodity in a linear subproblem and optimize a nonlinear master problem over the convex hull of a fixed number of retained extreme points and the previous master problem solution. Computational results on a network with 3,300 nodes and 10,400 arcs are reported for four, ten and 100 commodities.