|Linear programming: Linear programming (LP) is a mathematical method for optimizing a linear function, subject to linear constraints. An LP problem typically consists of two parts, an objective function, and a set of constraints. See also Computer programming, Software, Computers._____________Annotation: The above characterizations of concepts are neither definitions nor exhausting presentations of problems related to them. Instead, they are intended to give a short introduction to the contributions below. – Lexicon of Arguments. |
Peter Norvig on Linear Programming - Dictionary of Arguments
Norvig I 155
Linear Programming/Norvig/Russell: Linear programming (LP) was first studied systematically by the Russian mathematician Leonid Kantorovich (1939)(1). It was one of the first applications of computers; the simplex algorithm (Dantzig, 1949)(2) is still used despite worst-case exponential complexity.
Karmarkar (1984)(3) developed the far more efficient family of interior-point methods, which was shown to have polynomial complexity for the more general class of convex optimization problems
by Nesterov and Nemirovski (1994)(4). Excellent introductions to convex optimization are provided by Ben-Tal and Nemirovski (2001)(5) and Boyd and Vandenberghe (2004)(6).
1. Kantorovich, L. V. (1939). Mathematical methods of organizing and planning production. Publishd in translation in Management Science, 6(4), 366–422, July 1960.
2. Dantzig, G. B. (1949). Programming of interdependent activities: II. Mathematical model. econometrica, 17, 200–211.
3. Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4,
4. Nesterov, Y. and Nemirovski, A. (1994). Interior-Point Polynomial Methods in Convex Programming.
SIAM (Society for Industrial and Applied Mathematics).
5. Ben-Tal, A. and Nemirovski, A. (2001). Lectures on Modern Convex Optimization: Analysis, algorithms, and Engineering Applications. SIAM (Society for Industrial and Applied Mathematics).
6. Boyd, S. and Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Concept/Author], [Author1]Vs[Author2] or [Author]Vs[term] resp. "problem:"/"solution:", "old:"/"new:" and "thesis:" is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010