Linear programming - Revision history

~2026-34472-21: /* Ellipsoid algorithm, following Khachiyan */ More details

2026-07-05T14:28:17Z

Ellipsoid algorithm, following Khachiyan: More details

imported>Citation bot: Added bibcode. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

2025-12-25T09:28:28Z

Added bibcode. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar

← Previous revision		Revision as of 09:28, 25 December 2025
Line 17:		Line 17:
	Here the components of <math>\mathbf{x}</math> are the variables to be determined, <math>\mathbf{c}</math> and <math>\mathbf{b}</math> are given [[vector space\|vectors]], and <math>A</math> is a given [[Matrix (mathematics)\|matrix]]. The function whose value is to be maximized (<math>\mathbf x\mapsto\mathbf{c}^\mathsf{T}\mathbf{x}</math> in this case) is called the [[objective function]]. The constraints <math>A \mathbf{x} \le \mathbf{b}</math> and <math>\mathbf{x} \geq \mathbf{0}</math> specify a [[convex polytope]] over which the objective function is to be optimized.		Here the components of <math>\mathbf{x}</math> are the variables to be determined, <math>\mathbf{c}</math> and <math>\mathbf{b}</math> are given [[vector space\|vectors]], and <math>A</math> is a given [[Matrix (mathematics)\|matrix]]. The function whose value is to be maximized (<math>\mathbf x\mapsto\mathbf{c}^\mathsf{T}\mathbf{x}</math> in this case) is called the [[objective function]]. The constraints <math>A \mathbf{x} \le \mathbf{b}</math> and <math>\mathbf{x} \geq \mathbf{0}</math> specify a [[convex polytope]] over which the objective function is to be optimized.

	Linear programming can be applied to various fields of study. It is widely used in mathematics and, to a lesser extent, in business, [[economics]], and some engineering problems. There is a close connection between linear programs, eigenequations, [[John von Neumann]]'s general equilibrium model, and structural equilibrium models (see [[dual linear program]] for details).<ref>{{cite journal \|last=von Neumann \|first=J. \|year=1945 \|title=A Model of General Economic Equilibrium \|journal=The Review of Economic Studies \|volume=13 \|issue=1 \|pages=1–9\|doi=10.2307/2296111 \|jstor=2296111 }}</ref>		Linear programming can be applied to various fields of study. It is widely used in mathematics and, to a lesser extent, in business, [[economics]], and some engineering problems. There is a close connection between linear programs, eigenequations, [[John von Neumann]]'s general equilibrium model, and structural equilibrium models (see [[dual linear program]] for details).<ref>{{cite journal \|last=von Neumann \|first=J. \|year=1945 \|title=A Model of General Economic Equilibrium \|journal=The Review of Economic Studies \|volume=13 \|issue=1 \|pages=1–9\|doi=10.2307/2296111 \|jstor=2296111 \|bibcode=1945RvES...13....1N }}</ref>
	<ref>{{Cite journal		<ref>{{Cite journal
	\| last1 = Kemeny		\| last1 = Kemeny
Line 430:		Line 430:
	\|[[NAG Numerical Library]]\|\| A collection of mathematical and statistical routines developed by the [[Numerical Algorithms Group]] for multiple programming languages (C, C++, Fortran, Visual Basic, Java and C#) and packages (MATLAB, Excel, R, LabVIEW). The Optimization chapter of the NAG Library includes routines for linear programming problems with both sparse and non-sparse linear constraint matrices, together with routines for the optimization of quadratic, nonlinear, sums of squares of linear or nonlinear functions with nonlinear, bounded or no constraints. The NAG Library has routines for both local and global optimization, and for continuous or integer problems.		\|[[NAG Numerical Library]]\|\| A collection of mathematical and statistical routines developed by the [[Numerical Algorithms Group]] for multiple programming languages (C, C++, Fortran, Visual Basic, Java and C#) and packages (MATLAB, Excel, R, LabVIEW). The Optimization chapter of the NAG Library includes routines for linear programming problems with both sparse and non-sparse linear constraint matrices, together with routines for the optimization of quadratic, nonlinear, sums of squares of linear or nonlinear functions with nonlinear, bounded or no constraints. The NAG Library has routines for both local and global optimization, and for continuous or integer problems.
	\|-		\|-
	\|[[OptimJ]]\|\| A Java-based modeling language for optimization with a free version available.<ref>http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ used in an optimization model for mixed-model assembly lines, University of Münster</ref><ref>http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 {{Webarchive\|url=https://web.archive.org/web/20110629022829/http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 \|date=2011-06-29 }} OptimJ used in an Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games</ref>		\|[[OptimJ]]\|\| A Java-based modeling language for optimization with a free version available.<ref>http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf {{Webarchive\|url=https://web.archive.org/web/20110720163402/http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated%20Production-Distribution%20Planning.pdf \|date=2011-07-20 }} OptimJ used in an optimization model for mixed-model assembly lines, University of Münster</ref><ref>http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 {{Webarchive\|url=https://web.archive.org/web/20110629022829/http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 \|date=2011-06-29 }} OptimJ used in an Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games</ref>
	\|-		\|-
	\|[[SAS System\|SAS]]/OR\|\| A suite of solvers for Linear, Integer, Nonlinear, Derivative-Free, Network, Combinatorial and Constraint Optimization; the [[Algebraic modeling language]] OPTMODEL; and a variety of vertical solutions aimed at specific problems/markets, all of which are fully integrated with the [[SAS System]].		\|[[SAS System\|SAS]]/OR\|\| A suite of solvers for Linear, Integer, Nonlinear, Derivative-Free, Network, Combinatorial and Constraint Optimization; the [[Algebraic modeling language]] OPTMODEL; and a variety of vertical solutions aimed at specific problems/markets, all of which are fully integrated with the [[SAS System]].

imported>OrangeYellowTree: /* Solvers and scripting (programming) languages */

2025-11-17T14:28:47Z

Solvers and scripting (programming) languages

← Previous revision		Revision as of 14:28, 17 November 2025
Line 354:		Line 354:
	\|-		\|-
	\| [[JuMP]]\|\|[[MPL License]]\|\|Open-source modeling language with solvers for large-scale LP, [[Quadratic programming\|QP]], [[Quadratically constrained quadratic program\|QCQP]], [[Semidefinite programming\|SDP]], [[Second-order cone programming\|SOCP]], [[Nonlinear programming\|NLP]], and [[Mixed integer programming\|MIP]] optimization		\| [[JuMP]]\|\|[[MPL License]]\|\|Open-source modeling language with solvers for large-scale LP, [[Quadratic programming\|QP]], [[Quadratically constrained quadratic program\|QCQP]], [[Semidefinite programming\|SDP]], [[Second-order cone programming\|SOCP]], [[Nonlinear programming\|NLP]], and [[Mixed integer programming\|MIP]] optimization
			\|-
			\| [[ojAlgo]]\|\|[[MIT License]]\|\|oj! Algorithms - ojAlgo - is Open Source Java code that has to do with mathematics, linear algebra and optimisation.
	\|-		\|-
	\| [[Pyomo]]\|\|[[BSD licenses\|BSD]]\|\|An open-source modeling language for large-scale linear, mixed integer and nonlinear optimization		\| [[Pyomo]]\|\|[[BSD licenses\|BSD]]\|\|An open-source modeling language for large-scale linear, mixed integer and nonlinear optimization
Line 377:		Line 379:
	\|[[GNU Linear Programming Kit\|glpk]]\|\|GPL\|\| GNU Linear Programming Kit, an LP/MILP solver with a native C [[API]] and numerous (15) third-party wrappers for other languages. Specialist support for [[flow network]]s. Bundles the [[AMPL]]-like [[GNU MathProg]] modelling language and translator.		\|[[GNU Linear Programming Kit\|glpk]]\|\|GPL\|\| GNU Linear Programming Kit, an LP/MILP solver with a native C [[API]] and numerous (15) third-party wrappers for other languages. Specialist support for [[flow network]]s. Bundles the [[AMPL]]-like [[GNU MathProg]] modelling language and translator.
	\|-		\|-
	\|[[lp solve]]\|\|LGPL v2.1\|\|An LP and [[Mixed-integer programming\|MIP]] solver featuring support for the [[MPS (format)\|MPS format]] and its own "lp" format, as well as custom formats through its "eXternal Language Interface" (XLI).<ref>{{cite web\|url=https://web.mit.edu/lpsolve/doc/index.htm\|title=lp_solve reference guide (5.5.2.5)\|work=mit.edu\|access-date=2023-08-10}}</ref><ref>{{cite web \|url=~~http~~://lpsolve.sourceforge.net/5.5/XLI.htm \|access-date=3 December 2021\|title=External Language Interfaces}}</ref> Translating between model formats is also possible.<ref>{{cite web \|url=http://lpsolve.sourceforge.net/5.5/lp_solve.htm \|access-date=3 December 2021\|title=lp_solve command}}</ref>		\|[[lp solve]]\|\|LGPL v2.1\|\|An LP and [[Mixed-integer programming\|MIP]] solver featuring support for the [[MPS (format)\|MPS format]] and its own "lp" format, as well as custom formats through its "eXternal Language Interface" (XLI).<ref>{{cite web\|url=https://web.mit.edu/lpsolve/doc/index.htm\|title=lp_solve reference guide (5.5.2.5)\|work=mit.edu\|access-date=2023-08-10}}</ref><ref>{{cite web \|url=https://lpsolve.sourceforge.net/5.5/XLI.htm \|access-date=3 December 2021\|title=External Language Interfaces}}</ref> Translating between model formats is also possible.<ref>{{cite web \|url=http://lpsolve.sourceforge.net/5.5/lp_solve.htm \|access-date=3 December 2021\|title=lp_solve command}}</ref>
	\|-		\|-
	\|[[Qoca]]\|\|GPL\|\|A library for incrementally solving systems of linear equations with various goal functions		\|[[Qoca]]\|\|GPL\|\|A library for incrementally solving systems of linear equations with various goal functions
Line 509:		Line 511:
	*[http://people.brunel.ac.uk/~mastjjb/jeb/or/lp.html Guidance On Formulating LP Problems]		*[http://people.brunel.ac.uk/~mastjjb/jeb/or/lp.html Guidance On Formulating LP Problems]
	*[http://glossary.computing.society.informs.org/ Mathematical Programming Glossary]		*[http://glossary.computing.society.informs.org/ Mathematical Programming Glossary]
	*[~~http~~://lpsolve.sourceforge.net/4.0/LinearProgrammingFAQ.htm The Linear Programming FAQ]		*[https://lpsolve.sourceforge.net/4.0/LinearProgrammingFAQ.htm The Linear Programming FAQ]
	*[http://plato.asu.edu/bench.html Benchmarks For Optimisation Software]		*[http://plato.asu.edu/bench.html Benchmarks For Optimisation Software]

imported>Jochen Burghardt: Undid revision 1289124755 by Bewbew2029 (talk)

2025-05-06T17:57:47Z

Undid revision 1289124755 by Bewbew2029 (talk)

Show changes