Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
1-1-1988
Abstract
Resource directive algorithms for multicommodity network flow problems are decomposition schemes that work by transforming the problem into one of finding the best possible allocation of capacities to the competing commodities. The transformed problem has a piecewise linear convex master program, with single commodity network flow subproblems, which can be solved fast. Resource directive algorithms presented in the literature have attempted to exploit the convexity of the objective. However, the best resource directive algorithm available, the subgradient algorithm, remains heuristic in nature. On the other hand, optimizing algorithms are usually computationally effective variants of the revised simplex algorithm; are roughly twice as slow as the subgradient algorithm, and require large amounts of storage space on the computer. We present a resource directive algorithm that takes advantage of the piecewise linearity of the objective for the transformed problem. Computational results demonstrate that the algorithm is efficient both in terms of execution speed and storage space requirements.
Keywords
Operations research, Network analysis (Planning), Mathematical optimization, Algorithms, Linear programming, Computer storage devices
Publication Title
Dissertation/Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 636 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Khot, Chandrashekhar Madhukar, "An Efficient Resource Directive Algorithm for Multicommodity Network Flow Problems" (1988). Research Reports from the Department of Operations. 181.
https://commons.case.edu/wsom-ops-reports/181
