Research Reports from the Department of Operations
Document Type
Report
Publication Date
5-1-1981
Abstract
This thesis proposes an approach for improving the efficiency of the Out-of-Kilter algorithm for solving minimum-cost circulation problems which arise in network flow theory. Two alternative schemes are presented for solving the problem by starting with infeasible initial flows. Various heuristics for choosing the initial flows are considered, and their impact on the computational performance of the proposed alternatives is investigated. Based on computational experimentation with random minimum-cost circulation problems, there is reason to suspect that for certain types of circulation problems, significant computational savings can be achieved by judiciously choosing initial flows. The method also performed well when tested on maximum flow problems and on a real-world test problem.
Keywords
Operations research, Algorithms, Mathematical optimization, Heuristic algorithms, Computational complexity, Linear programming
Publication Title
Master's thesis/Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 505 ; Submitted in partial fulfillment of the requirements for the Degree of Master of Science.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Javaheri-Khoei, Gitta, "Computational Study of a Network Algorithm Which Can Start with a Non-Zero Flow" (1981). Research Reports from the Department of Operations. 87.
https://commons.case.edu/wsom-ops-reports/87