Name Brief info
CPLEX Popular solver with an API for several programming language, and also has a modelling language and works with TOMLAB
EXCEL Solver Function
IMSL Numerical Libraries Collections of math and statistical algorithms available in C/C++, Fortran, Java and C#/.NET. Optimization routines in the IMSL Libraries include unconstrained, linearly and nonlinearly constrained minimizations, and linear programming algorithms.
MATLAB A general-purpose and matrix-oriented programming-language for numerical computing. Linear programming in MATLAB equires the Optimization Toolbox in addition to the base MATLAB product; available routines include BINTPROG and LINPROG
Mathematica A general-purpose programming-language for mathematics, including symbolic and numerical capabilities.
MOSEK A solver for large scale optimization with API for several languages (C++,java,.net, Matlab and python).
NMath Stats A general-purpose .NET statistical library containing a simplex solver.[12]
Solver Foundation A .NET platform for modeling, scheduling, and optimization.
VisSim A visual block diagram language for simulation of dynamical systems.
YALMIP MATLAB based modeling system for convex optimization, including linear programs; relies on external solvers. For LP, it can call free solvers, such as CDD, glpk, LP_Solve, and QSOPT, or it can call commercial solvers such as MATLAB’s BINTPROG or LINPROG (it can also call more general purpose solvers, such as SDPT3 or SeDuMi, which are also able to solve LP)(Free for non-commercial use)

See also

Search Wikibooks Wikibooks has a book on the topic of

  • see also the “External links” section below


  1. ^ Vazirani (2001, p. 112)
  2. ^ Dantzig and Thapa, Padberg.
  3. ^ Padberg.
  4. ^ Bland; Fukuda and Terlaky. See also Murty, Dantzig and Thapa, Padberg, Papadimitriou and Steiglitz.
  5. ^ Dantzig and Thapa, Todd.
  6. ^ Dantzig and Thapa, Papadimitriou and Steiglitz, Murty.
  7. ^ Beasley, Todd.
  8. ^ For solving network-flow problms in transportation networks, specialized implementations of the simplex algorithm can dramatically improve its efficiency. See Dantzig and Thapa.
  9. ^ See Fukuda and Terlaky.
  10. ^
  11. ^
  12. ^ name=”Linear programming page at CenterSpace Software”>

Further reading

A reader may consider beginning with Nering and Tucker, with the first volume of Dantzig and Thapa, or with Williams.

  • Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Extensions, Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)
  • A. Bachem and W. Kern. Linear Programming Duality: An Introdution to Oriented Matroids. Universitext. Springer-Verlag, 1992. (Combinatorial)
  • J. E. Beasley, editor. Advances in Linear and Integer Programing. Oxford Science, 1996. (Collection of surveys)
  • Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised ed.). Springer-Verlag. ISBN 3-540-65620-0. Chapter 4: Linear Programming: pp. 63–94. Describes a randomized half-plane intersection algorithm for linear programming.
  • R.G. Bland, New finite pivoting rules for the simplex method, Math. Oper. Res. 2 (1977) 103–107.
  • Karl-Heinz Borgwardt, The Simplex Algorithm: A Probabilistic Analysis, Algorithms and Combinatorics, Volume 1, Springer-Verlag, 1987. (Average behavior on random problems)
  • V. Chandru and M.R.Rao, Linear Programming, Chapter 31 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 31-1 to 31-37.
  • V. Chandru and M.R.Rao, Integer Programming, Chapter 32 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 32-1 to 32-45.[1]
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 29: Linear Programming, pp. 770–821. (computer science)
  • Richard W. Cottle, ed. The Basic George B. Dantzig. Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Selected papers by George B. Dantzig)
  • George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
  • George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag. (Comprehensive, covering e.g. pivoting and interior-point algorithms, large-scale problems, decomposition following Dantzig-Wolfe and Benders, and introducing stochastic programming.)
  • Komei Fukuda and Tamás Terlaky, Criss-cross methods: A fresh view on pivot algorithms. (1997) Mathematical Programming Series B, Vol 79, Nos. 1—3, 369—395. (Invited survey, from the International Symposium on Mathematical Programming.)
  • Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A6: MP1: INTEGER PROGRAMMING, pg.245. (computer science, complexity theory)
  • Bernd Gärtner, Jiří Matoušek (2006). Understanding and Using Linear Programming, Berlin: Springer. ISBN 3-540-30697-8 (introduction for mathematicians and computer scientists)
  • Kattta G. Murty, Linear Programming, Wiley, 1983. (comprehensive reference to classical approaches)
  • Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)
  • M. Padberg, Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999. (carefully written account of primal and dual simplex algorithms and projective algorithms, with an introduction to integer linear programming — featuring the traveling salesman problem for Odysseus.)
  • Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Corrected republication with a new preface, Dover. (computer science)
  • Cornelis Roos, Tamás Terlaky, Jean-Philippe Vial, Interior Point Methods for Linear Optimization, Second Edition, Springer-Verlag, 2006. (Graduate level)
  • Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6 (mathematical)
  • Michael J. Todd (February 2002). “The many facets of linear programming”. Mathematical Programming 91 (3). (Invited survey, from the International Symposium on Mathematical Programming.)
  • Robert J. Vanderbei, Linear Programming: Foundations and Extensions, 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. ISBN 978-0-387-74387-5. (An on-line second edition was formerly available. Vanderbei’s site still contains extensive materials.)
  • Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 3-540-65367-8. (Computer science)
  • H. P. Williams, Model Buildiing in Mathematical Programming, Third revised Edition, 1990. (Modeling)
  • Stephen J. Wright, 1997, Primal-Dual Interior-Point Methods, SIAM. (Graduate level)
  • Yinyu Ye, 1997, Interior Point Algorithms: Theory and Analysis, Wiley. (Advanced graduate-level)
  • Ziegler, Günter M., Chapters 1-3 and 6-7 in Lectures on Polytopes, Springer-Verlag, New York, 1994. (Geometry)

External links

This article’s use of external links may not follow Wikipedia’s policies or guidelines. Please improve this article by removing excessive and inappropriate external links or by converting links into references.
  1. ^