Elements of Large-Scale Mathematical Programming Part I: Concepts

TLDR

The paper introduces two main categories of concepts in large‑scale mathematical programming: problem manipulations that generate master problems (projection, inner and outer linearization) and solution strategies that produce subproblems (piecewise, restriction, relaxation). The study develops a unifying framework of concepts for large‑scale mathematical programming. The framework is presented through an introductory section, followed by chapters on problem manipulations, solution strategies, and synthesis of known algorithms, with algorithms classified by manipulation/strategy patterns and demonstrated by rederiving representative examples. The framework successfully classifies many existing algorithms and demonstrates its usefulness by rederiving a representative set of algorithms.

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.