WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

LinearProgramming
✖
LinearProgramming

As of Version 13.0, LinearProgramming has been superseded by LinearOptimization.

✖
LinearProgramming[c,m,b]

finds a vector x that minimizes the quantity c.x subject to the constraints m.x≥b and x≥0.

✖
LinearProgramming[c,m,{{b1,s1},{b2,s2},…}]

finds a vector x that minimizes c.x subject to x≥0 and linear constraints specified by the matrix m and the pairs {bi,si}. For each row mi of m, the corresponding constraint is mi.x≥bi if si==1, or mi.x==bi if si==0, or mi.x≤bi if si==-1.

✖
LinearProgramming[c,m,b,l]

minimizes c.x subject to the constraints specified by m and b and x≥l.

✖
LinearProgramming[c,m,b,{l1,l2,…}]

minimizes c.x subject to the constraints specified by m and b and xi≥li.

✖
LinearProgramming[c,m,b,{{l1,u1},{l2,u2},…}]

minimizes c.x subject to the constraints specified by m and b and li≤xi≤ui.

✖
LinearProgramming[c,m,b,lu,dom]

takes the elements of x to be in the domain dom, either Reals or Integers.

✖
LinearProgramming[c,m,b,lu,{dom1,dom2,…}]

takes xi to be in the domain domi.

Details and Options

  • All entries in the vectors c and b and the matrix m must be real numbers.
  • The bounds li and ui must be real numbers or Infinity or -Infinity.
  • None is equivalent to specifying no bounds.
  • LinearProgramming gives exact rational number or integer results if its input consists of exact rational numbers.
  • LinearProgramming returns unevaluated if no solution can be found.
  • LinearProgramming finds approximate numerical results if its input contains approximate numbers. The option Tolerance specifies the tolerance to be used for internal comparisons. The default is Tolerance->Automatic, which does exact comparisons for exact numbers, and uses tolerance for approximate numbers.
  • SparseArray objects can be used in LinearProgramming.
  • With Method->"InteriorPoint", LinearProgramming uses interior point methods.

Examples

open allclose all

Basic Examples  (3)Summary of the most common use cases

Minimize , subject to constraint and implicit non-negative constraints:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-h12435
Out[1]=1

LinearProgramming has been superseded by LinearOptimization:

In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-zmihwg
Out[2]=2

Solve the problem with equality constraint and implicit non-negative constraints:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-hlzeu3
Out[1]=1

Use LinearOptimization to solve the problem:

In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-6tbtgn
Out[2]=2

Solve the problem with equality constraint and implicit non-negative constraints:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-465e7g
Out[1]=1

Use LinearOptimization to solve the problem:

In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-0opb4
Out[2]=2

Scope  (6)Survey of the scope of standard use cases

Minimize , subject to constraint and lower bounds , :

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-4u7ro7
Out[1]=1

Minimize , subject to constraint and bounds , :

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-lyiasg
Out[1]=1

Minimize , subject to constraint and upper bounds , :

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-7ipnd7
Out[1]=1

Minimize , subject to constraint and implicit non-negative constraints:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-yikwa7
Out[1]=1

Minimize subject to bounds and only:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-5wq1px
Out[1]=1

Solve the same kind of problem, but with both variables integers:

In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-5bf8jy
Out[2]=2

Solve the same problem, but with the first variable an integer:

In[3]:=3
✖
https://wolfram.com/xid/0i1qy6weq-yu3u6t
Out[3]=3

Solve larger LPs, in this case 200,000 variables and 10,000 constraints:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-fw34id
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-bgvwyr
Out[2]=2

Options  (2)Common values & functionality for each option

Method  (1)

"InteriorPoint" is faster than "Simplex" or "RevisedSimplex", though it only works for machine-precision problems:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-wti4rc
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-zlt2wi
Out[2]=2

Tolerance  (1)

If an approximated solution is sufficient, a loose Tolerance option makes the solution process faster:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-bia08o
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-5kr4qr
Out[2]=2

Properties & Relations  (2)Properties of the function, and connections to other functions

A linear programming problem can also be solved using Minimize:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-1hjz1k
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-vfps0s
Out[2]=2

NMinimize or FindMinimum can be used to solve inexact linear programming problems:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-d4j1il
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-1jt1gv
Out[2]=2

Possible Issues  (4)Common pitfalls and unexpected behavior

The integer programming algorithm is limited to the machine-number problems:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-1s04v2
Out[1]=1

The "InteriorPoint" method only works for machine numbers:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-kgidfc
Out[1]=1

The "InteriorPoint" method may return a solution in the middle of the optimal solution set:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-7op6n8
Out[1]=1

The "Simplex" method always returns a solution at a corner of the optimal solution set:

In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-6lgj4b
Out[2]=2

In this case the optimal solution set is the set of all points on the line segment between and :

In[3]:=3
✖
https://wolfram.com/xid/0i1qy6weq-c5p781
Out[3]=3

The "InteriorPoint" method may not always be able to tell if a problem is infeasible or unbounded:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-lxuygb
Out[1]=1

Neat Examples  (1)Surprising or curious use cases

This expresses the Klee–Minty problem of dimension n in LinearProgramming syntax:

In[1]:=1
✖
https://wolfram.com/xid/0i1qy6weq-cge34o

Because scaling is applied internally, the simplex algorithm converges very quickly:

In[2]:=2
✖
https://wolfram.com/xid/0i1qy6weq-75a3i2
Out[2]=2
Wolfram Research (1991), LinearProgramming, Wolfram Language function, https://reference.wolfram.com/language/ref/LinearProgramming.html (updated 2007).
✖
Wolfram Research (1991), LinearProgramming, Wolfram Language function, https://reference.wolfram.com/language/ref/LinearProgramming.html (updated 2007).

Text

Wolfram Research (1991), LinearProgramming, Wolfram Language function, https://reference.wolfram.com/language/ref/LinearProgramming.html (updated 2007).

✖
Wolfram Research (1991), LinearProgramming, Wolfram Language function, https://reference.wolfram.com/language/ref/LinearProgramming.html (updated 2007).

CMS

Wolfram Language. 1991. "LinearProgramming." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2007. https://reference.wolfram.com/language/ref/LinearProgramming.html.

✖
Wolfram Language. 1991. "LinearProgramming." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2007. https://reference.wolfram.com/language/ref/LinearProgramming.html.

APA

Wolfram Language. (1991). LinearProgramming. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/LinearProgramming.html

✖
Wolfram Language. (1991). LinearProgramming. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/LinearProgramming.html

BibTeX

@misc{reference.wolfram_2025_linearprogramming, author="Wolfram Research", title="{LinearProgramming}", year="2007", howpublished="\url{https://reference.wolfram.com/language/ref/LinearProgramming.html}", note=[Accessed: 07-July-2025 ]}

✖
@misc{reference.wolfram_2025_linearprogramming, author="Wolfram Research", title="{LinearProgramming}", year="2007", howpublished="\url{https://reference.wolfram.com/language/ref/LinearProgramming.html}", note=[Accessed: 07-July-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_linearprogramming, organization={Wolfram Research}, title={LinearProgramming}, year={2007}, url={https://reference.wolfram.com/language/ref/LinearProgramming.html}, note=[Accessed: 07-July-2025 ]}

✖
@online{reference.wolfram_2025_linearprogramming, organization={Wolfram Research}, title={LinearProgramming}, year={2007}, url={https://reference.wolfram.com/language/ref/LinearProgramming.html}, note=[Accessed: 07-July-2025 ]}