Premium
A fast algorithm for bounded generalized processing networks
Author(s) -
Fuller J. David,
Lan B.
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240202
Subject(s) - bounded function , algorithm , minos , mathematics , mathematical optimization , sequence (biology) , linear programming , flow network , heuristic , computer science , mathematical analysis , physics , biology , nuclear physics , neutrino , genetics , neutrino oscillation
A bounded generalized processing network model has the structure of a cost‐minimizing generalized network, with additional side constraints that, for flows on some arcs, place upper and lower bounds that are proportional to flows on other arcs. We propose and test a heuristic algorithm that takes advantage of the near‐network structure by solving a sequence of generalized network LPs whose data are adjusted in a manner suggested by the solution at previous steps. The algorithm extends an earlier algorithm to achieve better solutions, at the cost of more computing effort. In tests, the algorithm is much faster than is application of the general purpose linear programming code MINOS, and the speed advantage increases with problem size: The algorithm is 27 times faster than MINOS on the largest test problem. The algorithm almost always obtains solutions within 0.05% of the optimum. The proportionality constraints are relaxed in the algorithm, yet the solutions to the test problems satisfy the proportionality constraints to within, at worst, 0.25% of the given proportionality limits. © 1994 John Wiley & Sons, Inc.