Solution of large-scale multicommodity network flow problems via a logarithmic barrier function decomposition
By: Heinrich Lange
Contributors: Naval Postgraduate School (U.S.)
Publisher: Naval Postgraduate School
Published: 1988
Place of publication: Monterey, California
Language: eng
Number of pages: 61
Subjects: Operations research
Description: 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.
Notes: Thesis advisor(s): Wood, R. Kevin.

"March 1988."

Thesis (M.S. in Operations Research)--Naval Postgraduate School, March 1988.

Includes bibliographical references (p. 58-60).

Approved for public release, distribution unlimited.

German Navy author.