Elements of Large-Scale Mathematical Programming Part I: Concepts

Arthur M. Geoffrion
Additional contact information
Arthur M. Geoffrion: University of California, Los Angeles

Management Science, 1970, vol. 16, issue 11, 652-675

Abstract: A framework of concepts is developed which helps to unify a substantial portion of the literature on large-scale mathematical programming. These concepts fall into two categories. The first category consists of problem manipulations that can be used to derive what are often referred to as "master" problems; the principal manipulations discussed are Projection, Inner Linearization, and Outer Linearization. The second category consists of solution strategies that can be used to solve the master problems, often with the result that "subproblems" arise which can then be solved by specialized algorithms. The Piecewise, Restriction, and Relaxation strategies are the principal ones discussed. Numerous algorithms found in the literature are classified according to the manipulation/strategy pattern they can be viewed as using, and the usefulness of the framework is demonstrated by using it (see Part II of this paper) to rederive a representative selection of algorithms. The material presented is listed in the following order: The first section is introductory in nature, and discusses types of large-scale problems, the scope of discussion and the literature, and the notation used. The second section, entitled "Problem Manipulations: Source of `Master' Problems" covers the subjects of projection, inner linearization and outer linearization. The third section, "Solution Strategies: Source of `Subproblems'," discusses piecewise strategy, restriction and relaxation. The fourth section is entitled "Synthesizing Known Algorithms from Manipulations and Strategies," and is followed by a concluding section and an extensive bibliography.

Date: 1970
References: Add references at CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.16.11.652 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:16:y:1970:i:11:p:652-675

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().