Accession Number : ADA195449

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

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Lange, Heinrich

PDF Url : ADA195449

Report Date : Mar 1988

Pagination or Media Count : 66

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.

Descriptors :   *NETWORK FLOWS, ALGORITHMS, BARRIERS, CAPACITY(QUANTITY), COMPUTATIONS, COMPUTER PROGRAMMING, DECOMPOSITION, LINEAR SYSTEMS, LOGARITHM FUNCTIONS, MATHEMATICAL PROGRAMMING, NONLINEAR SYSTEMS, PROBLEM SOLVING, THESES

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE