Solution of Large-Scale Multicommodity Network Flow Problems via a Logarithmic Barrier Function Decomposition.
Abstract
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. Keywords: Multicommodity network flow problem, Large scale programming, Logarithmic barrier function, price directive decomposition.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1988
- Accession Number
- ADA195449
Entities
People
- Heinrich Lange
Organizations
- Naval Postgraduate School