Accession Number:

ADA148499

Title:

The Effect of Structure on the Solution Times of Minimum Cost Transportation and Multi-Echelon Network Flow Problems.

Descriptive Note:

Master's thesis,

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1984-06-01

Pagination or Media Count:

64.0

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

Subject Categories:

  • Information Science
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE