A generalized upper bounding method for doubly coupled linear programs

James K. Hartman, Leon S. Lasdon

Naval Research Logistics Quarterly · 1970 · 15 citations · 3 references

DOIFull text

Open access

Concepts

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.

References

3