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