LinearProgramming

LinearProgramming[c,m,b]

finds a vector x that minimizes the quantity c.x subject to the constraints m.xb and x0.

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

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

LinearProgramming[c,m,b,l]

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

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

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

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

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

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  (1)

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

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

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

Scope  (6)

Minimize , subject to constraint and lower bounds , :

Minimize , subject to constraint and bounds , :

Minimize , subject to constraint and upper bounds , :

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

Minimize subject to bounds and only:

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

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

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

Generalizations & Extensions  (1)

Objective, constraints, and bounds can all be specified as SparseArray:

Options  (2)

Method  (1)

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

Tolerance  (1)

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

Properties & Relations  (2)

A linear programming problem can also be solved using Minimize:

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

Possible Issues  (4)

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

The "InteriorPoint" method only works for machine numbers:

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

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

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

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

Neat Examples  (1)

This expresses the KleeMinty problem of dimension n in LinearProgramming syntax:

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

Introduced in 1991
 (2.0)
 |
Updated in 2003
 (5.0)
2007
 (6.0)