LinearProgramming
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 all close allBasic Examples (3)
Minimize 
, subject to constraint 
and implicit non-negative constraints:
LinearProgramming[{1, 1}, {{1, 2}}, {3}]LinearProgramming has been superseded by LinearOptimization:
LinearOptimization[x + y, {x + 2y >= 3, x >= 0, y >= 0}, {x, y}]Solve the problem with equality constraint 
and implicit non-negative constraints:
LinearProgramming[{1, 1}, {{1, 2}}, {{3, 0}}]Use LinearOptimization to solve the problem:
LinearOptimization[x + y, {x + 2y == 3, x >= 0, y >= 0}, {x, y}]Solve the problem with equality constraint 
and implicit non-negative constraints:
LinearProgramming[{1, 1}, {{1, 2}}, {{3, -1}}]Use LinearOptimization to solve the problem:
LinearOptimization[x + y, {x + 2y <= 3, x >= 0, y >= 0}, {x, y}]Scope (6)
Minimize 
, subject to constraint 
and lower bounds 
, 
:
LinearProgramming[{1, 1}, {{1, 2}}, {3}, {-1, -1}]Minimize 
, subject to constraint 
and bounds 
, 
:
LinearProgramming[{1, 1}, {{1, 2}}, {3}, {{-1, 2}, {-1, 1}}]Minimize 
, subject to constraint 
and upper bounds 
, 
:
LinearProgramming[{2, -3}, {{-1, -2}}, {{3, -1}}, {{-Infinity, 1}, {-Infinity, 1}}]Minimize 
, subject to constraint 
and implicit non-negative constraints:
LinearProgramming[{1., 1.}, {{5., 2.}}, {3.}]Minimize 
subject to bounds 
and 
only:
LinearProgramming[{2, 3}, {{}}, {}, {-1, -2}]Solve the same kind of problem, but with both variables integers:
LinearProgramming[{1., 1.}, {{5., 2.}}, {3.}, Automatic, Integers]Solve the same problem, but with the first variable an integer:
LinearProgramming[{1., 1.}, {{5., 2.}}, {3.}, Automatic, {Integers, Reals}]Solve larger LPs, in this case 200,000 variables and 10,000 constraints:
x = LinearProgramming[Range[2 10 ^ 5], SparseArray[{Band[{1, 1}] -> 1., Band[{1, 2}] -> 2.}, {10 ^ 4, 2 10 ^ 5}], Range[10 ^ 4]];//TimingTake[x, 10]Options (2)
Method (1)
"InteriorPoint" is faster than "Simplex" or "RevisedSimplex", though it only works for machine-precision problems:
Timing[LinearProgramming[Range[200], SparseArray[{Band[{1, 1}] -> 1., Band[{1, 2}] -> 2.}, {100, 200}], Range[100], Method -> "Simplex"];]Timing[LinearProgramming[Range[200], SparseArray[{Band[{1, 1}] -> 1., Band[{1, 2}] -> 2.}, {100, 200}], Range[100], Method -> "InteriorPoint"];]Tolerance (1)
If an approximated solution is sufficient, a loose Tolerance option makes the solution process faster:
Timing[LinearProgramming[Range[20000], SparseArray[{Band[{1, 1}] -> 1., Band[{1, 2}] -> 2.}, {10000, 20000}], Range[10000], Method -> "InteriorPoint"];]Timing[LinearProgramming[Range[20000], SparseArray[{Band[{1, 1}] -> 1., Band[{1, 2}] -> 2.}, {10000, 20000}], Range[10000], Method -> "InteriorPoint", Tolerance -> 1.];]Properties & Relations (2)
A linear programming problem can also be solved using Minimize:
LinearProgramming[{1, 2}, {{3, 4}}, {5}]Minimize[{x + 2y, {3x + 4y ≥ 5 && x ≥ 0 && y ≥ 0}}, {x, y}]NMinimize or FindMinimum can be used to solve inexact linear programming problems:
FindMinimum[{x + 2y, {3x + 4y ≥ 5 && x ≥ 0 && y ≥ 0}}, {x, y}]NMinimize[{x + 2y, {3x + 4y ≥ 5 && x ≥ 0 && y ≥ 0}}, {x, y}, WorkingPrecision -> 30]Possible Issues (4)
The integer programming algorithm is limited to the machine-number problems:
LinearProgramming[{1, 1}, {{5, 2}}, {3}, Automatic, Integers]
The "InteriorPoint" method only works for machine numbers:
LinearProgramming[{1, 1}, {{5, 2}}, {3}, Method -> "InteriorPoint"]
The "InteriorPoint" method may return a solution in the middle of the optimal solution set:
LinearProgramming[{-1., -1}, {{1., 1.}}, {{1., -1}}, Method -> "InteriorPoint"]The "Simplex" method always returns a solution at a corner of the optimal solution set:
LinearProgramming[{-1., -1}, {{1., 1.}}, {{1., -1}}, Method -> "Simplex"]In this case the optimal solution set is the set of all points on the line segment between 
and 
:
Plot3D[-x - y, {x, 0, 1}, {y, 0, 1}, RegionFunction -> Function[{x, y, z}, x + y ≤ 1 && x ≥ 0 && y ≥ 0]]The "InteriorPoint" method may not always be able to tell if a problem is infeasible or unbounded:
LinearProgramming[{-1., -1.}, {{1., 1.}}, {1.}, Method -> "InteriorPoint"]
Neat Examples (1)
This expresses the Klee–Minty problem of dimension 
in LinearProgramming syntax:
KleeMinty[n_] := Module[{a, b, c, m, rhs}, c = Table[-10^n - i, {i, n}];a[i_] := Join[Table[2 10^i - j, {j, i - 1}], {1}, Table[0, {n - i}]];rhs[i_] := {100^i - 1, -1};m = Table[a[i], {i, n}];b = Table[rhs[i], {i, n}];{c, m, b}]Because scaling is applied internally, the simplex algorithm converges very quickly:
Apply[LinearProgramming, KleeMinty[16]]//TimingText
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.
APA
Wolfram Language. (1991). LinearProgramming. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/LinearProgramming.html