Solution of large-scale multicommodity network flow problems via a logarithmic barrier function decomposition
Wood, R. Kevin
Brown, Gerald G.
MetadataShow full item record
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.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Kang, Shian Chin (Monterey, California: Naval Postgraduate School, 2015-09);Resource allocation problems occur in many applications. One example is bike-sharing systems, which encourage the use of public transport by making it easy to rent and return bicycles for short transits. With large numbers ...
Dumlao, Marcial B. (Monterey, California. Naval Postgraduate School, 1995-03);Within DOD, there exists many different network platforms and configurations. Managing multiple platforms with different protocols, configurations, and applications is a challenging task for a network manager. A possible ...
Wong, Eric Gregory Wen Wie (Monterey, California. Naval Postgraduate School, 2006-12);The security of a network depends on how its design fulfills the organization's security policy. One aspect of security is reachability: whether two hosts can communicate. Network designers and operators face a very ...