({{, (RefLink[LinearProgramming, paclet:ref/LinearProgramming])[c,m,b]
finds a vector x that minimizes the quantity c.x subject to the constraints m.x≥b and x≥0. }, {, (RefLink[LinearProgramming, paclet:ref/LinearProgramming])[c,m,{{(Subscript[b, 1]),(Subscript[s, 1])},{(Subscript[b, 2]),(Subscript[s, 2])},…}]
finds a vector x that minimizes c.x subject to x≥0 and linear constraints specified by the matrix m and the pairs {(Subscript[b, i]),(Subscript[s, i])}. For each row (Subscript[m, i]) of m, the corresponding constraint is (Subscript[m, i]).x≥(Subscript[b, i]) if (Subscript[s, i])==1, or (Subscript[m, i]).x==(Subscript[b, i]) if (Subscript[s, i])==0, or (Subscript[m, i]).x≤(Subscript[b, i]) if (Subscript[s, i])==-1. }, {, (RefLink[LinearProgramming, paclet:ref/LinearProgramming])[c,m,b,l]
minimizes c.x subject to the constraints specified by m and b and x≥l. }, {, (RefLink[LinearProgramming, paclet:ref/LinearProgramming])[c,m,b,{(Subscript[l, 1]),(Subscript[l, 2]),…}]
minimizes c.x subject to the constraints specified by m and b and (Subscript[x, i])≥(Subscript[l, i]). }, {, (RefLink[LinearProgramming, paclet:ref/LinearProgramming])[c,m,b,{{(Subscript[l, 1]),(Subscript[u, 1])},{(Subscript[l, 2]),(Subscript[u, 2])},…}]
minimizes c.x subject to the constraints specified by m and b and (Subscript[l, i])≤(Subscript[x, i])≤(Subscript[u, i]). }, {, (RefLink[LinearProgramming, paclet:ref/LinearProgramming])[c,m,b,lu,dom]
takes the elements of x to be in the domain dom, either (RefLink[Reals, paclet:ref/Reals]) or (RefLink[Integers, paclet:ref/Integers]).}, {, (RefLink[LinearProgramming, paclet:ref/LinearProgramming])[c,m,b,lu,{(Subscript[dom, 1]),(Subscript[dom, 2]),…}]
takes (Subscript[x, i]) to be in the domain (Subscript[dom, i]).}})

OpenersNotesSection(Spacer1)Details and Options

All entries in the vectors c and b and the matrix m must be real numbers.

The bounds (Subscript[l, i]) and (Subscript[u, i]) must be real numbers or (RefLink[Infinity, paclet:ref/Infinity]) or -(RefLink[Infinity, paclet:ref/Infinity]).

(RefLink[None, paclet:ref/None]) is equivalent to specifying no bounds.

(RefLink[LinearProgramming, paclet:ref/LinearProgramming]) gives exact rational number or integer results if its input consists of exact rational numbers.

(RefLink[LinearProgramming, paclet:ref/LinearProgramming]) returns unevaluated if no solution can be found.

(RefLink[LinearProgramming, paclet:ref/LinearProgramming]) finds approximate numerical results if its input contains approximate numbers. The option (RefLink[Tolerance, paclet:ref/Tolerance]) specifies the tolerance to be used for internal comparisons. The default is (RefLink[Tolerance, paclet:ref/Tolerance])->(RefLink[Automatic, paclet:ref/Automatic]), which does exact comparisons for exact numbers, and uses tolerance (10^(-6)) for approximate numbers.

(RefLink[SparseArray, paclet:ref/SparseArray]) objects can be used in (RefLink[LinearProgramming, paclet:ref/LinearProgramming]).

With (RefLink[Method, paclet:ref/Method])->"InteriorPoint", (RefLink[LinearProgramming, paclet:ref/LinearProgramming]) uses interior point methods.

OpenersPrimaryExamplesSection(Spacer1)Examples  (17)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

Minimize x+y, subject to constraint x+2 y≥3 and implicit non-negative constraints:

LinearProgramming[{1,1},{{1,2}},{3}]

Solve the problem with equality constraint x+2 y==3 and implicit non-negative constraints:

LinearProgramming[{1,1},{{1,2}},{{3,0}}]

Solve the problem with equality constraint x+2 y≤3 and implicit non-negative constraints:

LinearProgramming[{1,1},{{1,2}},{{3,-1}}]

OpenersExampleSection1(Spacer1)Scope  (6)

Minimize x+y, subject to constraint x+2 y≥3 and lower bounds x≥-1, y≥-1:

LinearProgramming[{1,1},{{1,2}},{3},{-1,-1}]

Minimize x+y, subject to constraint x+2 y≥3 and bounds 2≥x≥-1, 1≥y≥-1:

LinearProgramming[{1,1},{{1,2}},{3},{{-1,2},{-1,1}}]

Minimize 2 x-3 y, subject to constraint -x-2 y≤3 and upper bounds x≤1, y≤1:

LinearProgramming[{2,-3},{{-1,-2}},{{3,-1}},{{-Infinity,1},{-Infinity,1}}]

Minimize x+y, subject to constraint 5 x+2 y≥3 and implicit non-negative constraints:

LinearProgramming[{1.,1.},{{5.,2.}},{3.}]

Minimize 2 x+3 y subject to bounds x≥-1 and y≥-2 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]];//Timing

Take[x,10]

OpenersExampleSection2(Spacer1)Generalizations & Extensions  (1)

Objective, constraints, and bounds can all be specified as (RefLink[SparseArray, paclet:ref/SparseArray]):

LinearProgramming[SparseArray[{{1}->1},{4}],{{1,1,1,1}},{1}]

OpenersExampleSection3(Spacer1)Options  (2)

OpenersExampleSubsection0(Spacer1)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"];]

OpenersExampleSubsection1(Spacer1)Tolerance  (1)

If an approximated solution is sufficient, a loose (RefLink[Tolerance, paclet:ref/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.];]

OpenersExampleSection4(Spacer1)Properties & Relations  (2)

A linear programming problem can also be solved using (RefLink[Minimize, paclet:ref/Minimize]):

LinearProgramming[{1,2},{{3,4}},{5}]

Minimize[{x+2y,{3x+4y≥5&&x≥0&&y≥0}},{x,y}]

(RefLink[NMinimize, paclet:ref/NMinimize]) or (RefLink[FindMinimum, paclet:ref/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]

OpenersExampleSection5(Spacer1)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 (1,0) and (0,1):

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"]

OpenersExampleSection6(Spacer1)Neat Examples  (1)

This expresses the Klee–Minty problem of dimension n in (RefLink[LinearProgramming, paclet:ref/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]]//Timing

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[NMinimize, paclet:ref/NMinimize])  ▪  (RefLink[Minimize, paclet:ref/Minimize])  ▪  (RefLink[FindMinimum, paclet:ref/FindMinimum])}})}})

({{DocumentationFooterIconsRelatedTutorial.png, ({{Tutorials}, {▪(RefLinkPlain[Numerical Optimization, paclet:tutorial/NumericalOptimization])}, {▪(RefLinkPlain[Constrained Optimization, paclet:tutorial/ConstrainedOptimizationOverview])}, {▪(RefLinkPlain[Unconstrained Optimization, paclet:tutorial/UnconstrainedOptimizationOverview])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Optimization, paclet:guide/Optimization])}, {▪(RefLinkPlain[Matrix-Based Minimization, paclet:guide/MatrixBasedMinimization])}, {▪(RefLinkPlain[Matrices and Linear Algebra, paclet:guide/MatricesAndLinearAlgebra])}, {▪(RefLinkPlain[Linear Systems, paclet:guide/LinearSystems])}, {▪(RefLinkPlain[Graph Programming, paclet:guide/GraphProgramming])}})}})

({{(Spacer1), ({{(Spacer1)Related Links}, {(Spacer1)▪(RefLinkPlain[(Spacer1)Implementation notes: Numerical and Related Functions, paclet:tutorial/SomeNotesOnInternalImplementation#17945])}})}})