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

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.