The Effect of Structure on the Solution Times of Minimum Cost Transportation and Multi-Echelon Network Flow Problems.
Abstract
Researchers require benchmark test problems to evaluate the speed of computer codes designed to solve minimum cost network flow problems. To date, the only universally available test problems developed for that purpose are randomly generated. In practice, however, real-world network problems solve faster than random network problems. This thesis examines the effect on solution time resulting from applying structure, produced through simulation of real-world phenomena, to test networks. An efficient computer code, VSGEN, is developed which generates structured transportation and multi-echelon networks. Various types of structure, including unit flow cost, network topology and arc capacity, reduced the time required to solve the test networks and average of 26%, when using a primal network simplex solver, GNET. The parameter Big M used in primal simplex algorithms may affect solution times differently in structured versus unstructured networks. VSGEN is used to investigate this possibility. A bound on the minimum Big M is first developed for bipartite networks. This bound is sharper than the default bound used in GNET, but it does not reduce solution times in either structured or unstructured problems. Even the best possible bound reduces solution times by only 10%, on average. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1984
- Accession Number
- ADA148499
Entities
People
- W. R. Bonwit Jr
Organizations
- Naval Postgraduate School