Premium
An algorithm for generating minimum cost network flow problems with specific structure and known optimal solutions
Author(s) -
Arthur Jeffrey L.,
Frendewey James O.
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.3230240805
Subject(s) - minimum cost flow problem , flow network , mathematical optimization , computer science , transshipment (information security) , shortest path problem , generator (circuit theory) , algorithm , path (computing) , basis (linear algebra) , degree (music) , maximum flow problem , flow (mathematics) , out of kilter algorithm , dijkstra's algorithm , mathematics , graph , theoretical computer science , power (physics) , physics , geometry , computer security , quantum mechanics , acoustics , programming language
A new algorithm for generating structured, minimum cost network flow problems (transshipment, transportation, assignment, and shortest path) with known optimal solutions is described. The procedure is based on developing problems around an optimal basis so that the characteristics of solutions can be controlled. Computational tests show that the problems generated are as difficult to solve as are those produced by the commonly used generator NETGEN, while allowing the user a much greater degree of control over the resulting problems. © 1994 by John Wiley & Sons, Inc.