Research Reports from the Department of Operations
Document Type
Report
Publication Date
6-1-1970
Abstract
The constraints of large linear programs can often be partitioned into independent subsets, except for relatively few coupling rows and coupling columns. The individual subsets may, for example, arise from constraints on the activity levels of subdivisions of a large corporation. Alternatively, such blocks may arise from activities in different time periods. The coupling rows may arise from limitations on shared resources or from combining the outputs of subdivisions to meet overall demands. The coupling columns arise from activities which involve different time periods (e.g storage), or which involve different subdivisions (e.g. transportation or assembly). The case with only coupling rows or coupling columns but not both has received much attention [8],[9]. A smaller amount of work has been done on the problem with both coupling rows and columns. Ritter has proposed a dual method [3], [7]. Except for the preliminary work of Wabber and White [10] and Lasserssohn [4], there is no primal algorithm which exploits the structure of this problem. There is a need for such an algorithm, since such problems occur often in practice. A primal method is desirable since in large problems slow convergence may force termination of the algorithm prior to optimality. The algorithm proposed here is an extension of the generalized upper bounding method for problems without coupling columns proposed in [5] and [6]. It produces the same sequence of extreme point solutions as the primal simplex method, and hence has the desirable convergence properties of that algorithm. However the operations within each simplex iteration are organized to take maximal advantage of problem structure.
Keywords
Operations research, Linear programming, Mathematical optimization, Algorithms, Computational complexity, Industrial management--Mathematical models, Decision making--Mathematical models
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 190
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Hartman, James K. and Lasdon, Leon S., "A generalized upper bounding method for doubly coupled linear programs" (1970). Research Reports from the Department of Operations. 226.
https://commons.case.edu/wsom-ops-reports/226