linprog

Solve linear programming problems

Linear programming solver

Finds the minimum of a problem specified by

f, x, b, beq, lb, and ub are vectors, and A and Aeq are matrices.

Syntax

• ``x = linprog(f,A,b)``
example
• ``x = linprog(f,A,b,Aeq,beq)``
example
• ``x = linprog(f,A,b,Aeq,beq,lb,ub)``
example
• ``x = linprog(f,A,b,Aeq,beq,lb,ub,x0)``
• ``x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)``
example
• ``x = linprog(problem)``
• ``````[x,fval] = linprog(___)``````
example
• ``````[x,fval,exitflag,output] = linprog(___)``````
example
• ``````[x,fval,exitflag,output,lambda] = linprog(___)``````
example

Description

example

````x = linprog(f,A,b)` solves min `f'*x` such that `A*x `≤` b`.```

example

````x = linprog(f,A,b,Aeq,beq)` includes equality constraints `Aeq*x = beq`. Set `A = []` and `b = []` if no inequalities exist.```

example

````x = linprog(f,A,b,Aeq,beq,lb,ub)` defines a set of lower and upper bounds on the design variables, `x`, so that the solution is always in the range `lb ≤ x ≤ ub`. Set `Aeq = []` and `beq = []` if no equalities exist.Note:   If the specified input bounds for a problem are inconsistent, the output `x` is `x0` and the output `fval` is `[]`.```
````x = linprog(f,A,b,Aeq,beq,lb,ub,x0)` sets the starting point to `x0`.Note   `linprog` uses `x0` for only the `'active-set'` algorithm. For all other algorithms, `linprog` ignores `x0`.```

example

````x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)` minimizes with the optimization options specified by `options`. Use `optimoptions` to set these options.```
````x = linprog(problem)` finds the minimum for `problem`, where `problem` is a structure described in Input Arguments.Create the `problem` structure by exporting a problem from Optimization app, as described in Exporting Your Work. You can import a `problem` structure from an MPS file using `mpsread`.```

example

``````[x,fval] = linprog(___)```, for any input arguments, returns the value of the objective function `fun` at the solution `x`: `fval = f'*x`.```

example

``````[x,fval,exitflag,output] = linprog(___)``` additionally returns a value `exitflag` that describes the exit condition, and a structure `output` that contains information about the optimization process.```

example

``````[x,fval,exitflag,output,lambda] = linprog(___)``` additionally returns a structure `lambda` whose fields contain the Lagrange multipliers at the solution `x`.```

Examples

collapse all

Linear Program, Linear Inequality Constraints

Solve a simple linear program defined by linear inequalities.

For this example, use these linear inequality constraints:

```A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2]; ```

Use the objective function .

```f = [-1 -1/3]; ```

Solve the linear program.

```x = linprog(f,A,b) ```
```Optimization terminated. x = 0.6667 1.3333 ```

Linear Program with Linear Inequalities and Equalities

Solve a simple linear program defined by linear inequalities and linear equalities.

For this example, use these linear inequality constraints:

```A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2]; ```

Use the linear equality constraint .

```Aeq = [1 1/4]; beq = 1/2; ```

Use the objective function .

```f = [-1 -1/3]; ```

Solve the linear program.

```x = linprog(f,A,b,Aeq,beq) ```
```Optimization terminated. x = 0.0000 2.0000 ```

Linear Program with All Constraint Types

Solve a simple linear program with linear inequalities, linear equalities, and bounds.

For this example, use these linear inequality constraints:

```A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2]; ```

Use the linear equality constraint .

```Aeq = [1 1/4]; beq = 1/2; ```

Set these bounds:

```lb = [-1,-0.5]; ub = [1.5,1.25]; ```

Use the objective function .

```f = [-1 -1/3]; ```

Solve the linear program.

```x = linprog(f,A,b,Aeq,beq,lb,ub) ```
```Optimization terminated. x = 0.1875 1.2500 ```

Linear Program Using the Dual-Simplex Algorithm

Solve a linear program using the `'dual-simplex'` algorithm.

For this example, use these linear inequality constraints:

```A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2]; ```

Use the linear equality constraint .

```Aeq = [1 1/4]; beq = 1/2; ```

Set these bounds:

```lb = [-1,-0.5]; ub = [1.5,1.25]; ```

Use the objective function .

```f = [-1 -1/3]; ```

Set options to use the `'dual-simplex'` algorithm.

```options = optimoptions('linprog','Algorithm','dual-simplex'); ```

Set the initial point to `[]`, because the `dual-simplex` algorithm does not accept an initial point `x0`.

```x0 = []; ```

Solve the linear program using the `'dual-simplex'` algorithm.

```x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) ```
```Optimal solution found. x = 0.1875 1.2500 ```

Return the Objective Function Value

Calculate the solution and objective function value for a simple linear program.

The inequality constraints are

```A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2]; ```

The objective function is .

```f = [-1 -1/3]; ```

Solve the problem and return the objective function value.

```[x,fval] = linprog(f,A,b) ```
```Optimization terminated. x = 0.6667 1.3333 fval = -1.1111 ```

Obtain More Output to Examine the Solution Process

Obtain the exit flag and output structure to better understand the solution process and quality.

For this example, use these linear inequality constraints:

```A = [1 1 1 1/4 1 -1 -1/4 -1 -1 -1 -1 1]; b = [2 1 2 1 -1 2]; ```

Use the linear equality constraint .

```Aeq = [1 1/4]; beq = 1/2; ```

Set these bounds:

```lb = [-1,-0.5]; ub = [1.5,1.25]; ```

Use the objective function .

```f = [-1 -1/3]; ```

Set options to use the `'dual-simplex'` algorithm.

```options = optimoptions('linprog','Algorithm','dual-simplex'); ```

Set the initial point to `[]`, because the `dual-simplex` algorithm does not accept an initial point `x0`.

```x0 = []; ```

Solve the linear program and request the function value, exit flag, and output structure.

```[x,fval,exitflag,output] = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) ```
```Optimal solution found. x = 0.1875 1.2500 fval = -0.6042 exitflag = 1 output = iterations: 0 constrviolation: 0 message: 'Optimal solution found.' algorithm: 'dual-simplex' firstorderopt: 0 ```
• `fval`, the objective function value, is larger than Return the Objective Function Value, because there are more constraints.

• `exitflag` = 1 indicates that the solution is reliable.

• `output.iterations` = 0 indicates that `linprog` found the solution during presolve, and did not have to iterate at all.

Obtain Solution and Lagrange Multipliers

Solve a simple linear program and examine the solution and the Lagrange multipliers.

Use the objective function

```f = [-5; -4; -6]; ```

Use the linear inequality constraints

```A = [1 -1 1 3 2 4 3 2 0]; b = [20;42;30]; ```

Constrain all variables to be positive:

```lb = zeros(3,1); ```

Set `Aeq` and `beq` to `[]`, indicating that there are no linear equality constraints.

```Aeq = []; beq = []; ```

Call `linprog`, obtaining the Lagrange multipliers.

```[x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb); ```
```Optimization terminated. ```

Examine the solution and Lagrange multipliers.

```x,lambda.ineqlin,lambda.lower ```
```x = 0.0000 15.0000 3.0000 ans = 0.0000 1.5000 0.5000 ans = 1.0000 0.0000 0.0000 ```

`lambda.ineqlin` is nonzero for the second and third components of `x`. This indicates that the second and third linear inequality constraints are satisfied with equalities:

Check that this is true:

```A*x ```
```ans = -12.0000 42.0000 30.0000 ```

`lambda.lower` is nonzero for the first component of `x`. This indicates that `x(1)` is at its lower bound of 0.

Input Arguments

collapse all

`f` — Objective functionreal vector

Objective function, specified as a real vector. `linprog` attempts to find an `x` that minimizes the objective function

`f'*x = f(1)*x(1) + ... + f(N)*x(N)`,

where `N` is the number of variables in the problem.

Example: `f = [1,3,5,-6]`

Data Types: `double`

`A` — Linear inequality constraintsreal matrix

Linear inequality constraints, specified as a real matrix. `A` is an `M`-by-`N` matrix, where `M` is the number of inequalities, and `N` is the number of variables (number of elements in `x0`). For large problems, pass `A` as a sparse matrix.

`A` encodes the `M` linear inequalities

`A*x <= b`,

where `x` is the column vector of `N` variables `x(:)`, and `b` is a column vector with `M` elements.

For example, to specify

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30,

give these constraints:

```A = [1,2;3,4;5,6]; b = [10;20;30];```

Example: To specify that the x-components add up to 1 or less, take `A = ones(1,N)` and `b = 1`

Data Types: `double`

`b` — Linear inequality constraintsreal vector

Linear inequality constraints, specified as a real vector. `b` is an `M`-element vector related to the `A` matrix. If you pass `b` as a row vector, solvers internally convert `b` to the column vector `b(:)`. For large problems, pass `b` as a sparse vector.

`b` encodes the `M` linear inequalities

`A*x <= b`,

where `x` is the column vector of `N` variables `x(:)`, and `A` is a matrix of size `M`-by-`N`.

For example, to specify

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30,

give these constraints:

```A = [1,2;3,4;5,6]; b = [10;20;30];```

Example: To specify that the x-components sum to 1 or less, take ```A = ones(1,N)``` and `b = 1`

Data Types: `double`

`Aeq` — Linear equality constraintsreal matrix

Linear equality constraints, specified as a real matrix. `Aeq` is an `Me`-by-`N` matrix, where `Me` is the number of equalities, and `N` is the number of variables (number of elements in `x0`). For large problems, pass `Aeq` as a sparse matrix.

`Aeq` encodes the `Me` linear equalities

`Aeq*x = beq`,

where `x` is the column vector of `N` variables `x(:)`, and `beq` is a column vector with `Me` elements.

For example, to specify

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20,

give these constraints:

```Aeq = [1,2,3;2,4,1]; beq = [10;20];```

Example: To specify that the x-components sum to 1, take ```Aeq = ones(1,N)``` and `beq = 1`

Data Types: `double`

`beq` — Linear equality constraintsreal vector

Linear equality constraints, specified as a real vector. `beq` is an `Me`-element vector related to the `Aeq` matrix. If you pass `beq` as a row vector, solvers internally convert `beq` to the column vector `beq(:)`. For large problems, pass `beq` as a sparse vector.

`beq` encodes the `Me` linear equalities

`Aeq*x = beq`,

where `x` is the column vector of `N` variables `x(:)`, and `Aeq` is a matrix of size `Meq`-by-`N`.

For example, to specify

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20,

give these constraints:

```Aeq = [1,2,3;2,4,1]; beq = [10;20];```

Example: To specify that the x-components sum to 1, take ```Aeq = ones(1,N)``` and `beq = 1`

Data Types: `double`

`lb` — Lower boundsreal vector | real array

Lower bounds, specified as a real vector or real array. If the number of elements in `x0` is equal to that of `lb`, then `lb` specifies that

`x(i) >= lb(i)` for all `i`.

If `numel(lb) < numel(x0)`, then `lb` specifies that

`x(i) >= lb(i)` for ```1 <= i <= numel(lb)```.

In this case, solvers issue a warning.

Example: To specify that all x-components are positive, ```lb = zeros(size(x0))```

Data Types: `double`

`ub` — Upper boundsreal vector | real array

Upper bounds, specified as a real vector or real array. If the number of elements in `x0` is equal to that of `ub`, then `ub` specifies that

`x(i) <= ub(i)` for all `i`.

If `numel(ub) < numel(x0)`, then `ub` specifies that

`x(i) <= ub(i)` for ```1 <= i <= numel(ub)```.

In this case, solvers issue a warning.

Example: To specify that all x-components are less than one, ```ub = ones(size(x0))```

Data Types: `double`

`x0` — Initial pointreal vector | real array

Initial point, specified as a real vector or real array. Only the `'active-set'` algorithm uses `x0`, all other solvers ignore its value.

Example: `x0 = ones(size(f))`

Data Types: `double`

`options` — Optimization optionsoutput of `optimoptions` | structure as `optimset` returns

Optimization options, specified as the output of `optimoptions` or a structure as `optimset` returns.

Some options apply to all algorithms, and others are relevant for particular algorithms. See Optimization Options Reference for detailed information.

 All Algorithms `Algorithm` Choose the optimization algorithm:`'interior-point-legacy'` (default)`'interior-point'``'dual-simplex'``'active-set'``'simplex'`For information on choosing the algorithm, see Linear Programming Algorithms. `Diagnostics` Display diagnostic information about the function to be minimized or solved. Choose `'off'` (default) or `'on'`. `Display` Level of display (see Iterative Display):`'final'` (default) displays just the final output.`'off'` or `'none'` displays no output.`'iter'` displays output at each iteration. The `'iter'` option is unavailable for the `'active-set'` algorithm. `LargeScale`Use `Algorithm` instead Use the `'interior-point-legacy'` algorithm when set to `'on'` (default). Use a medium-scale algorithm when set to `'off'` (see `Simplex` in `options`). For more information, see Choosing the Algorithm. `MaxIter` Maximum number of iterations allowed, a positive integer. The default is:`85` for the `'interior-point-legacy'` algorithm`200` for the `'interior-point'` algorithm```10*(numberOfEqualities + numberOfInequalities + numberOfVariables)``` for the `'dual-simplex'` algorithm`10*numberOfVariables` for the `'simplex'` algorithm```10*max(numberOfVariables, numberOfInequalities + numberOfBounds)``` for the `'active-set'` algorithm `TolFun` Termination tolerance on the function value, a positive scalar. The default is:`1e-8` for the `'interior-point'` algorithm`1e-7` for the `'dual-simplex'` algorithm`1e-6` for the `'interior-point'` and `'simplex'` algorithmsThe option is not used for the `'active-set'` algorithm`TolFun` measures dual feasibility tolerance. interior-point Algorithm `Preprocess` Level of LP preprocessing prior to algorithm iterations. Specify `'basic'` (default) or `'none'`. `TolCon` Feasibility tolerance for constraints, a scalar from `1e-10` through `1e-3`. `TolCon` measures primal feasibility tolerance. The default is `1e-6`. Dual-Simplex Algorithm `MaxTime` Maximum amount of time in seconds that the algorithm runs. The default is `Inf`. `Preprocess` Level of LP preprocessing prior to dual simplex algorithm iterations. Specify `'basic'` (default) or `'none'`. `TolCon` Feasibility tolerance for constraints, a scalar from `1e-10` through `1e-3`. `TolCon` measures primal feasibility tolerance. The default is `1e-4`. Simplex Algorithm `Simplex`Use `Algorithm` instead If `'on'`, and if `LargeScale` is `'off'`, `linprog` uses the simplex algorithm. The simplex algorithm uses a built-in starting point, ignoring the starting point `x0` if supplied. The default is `'off'`, meaning `linprog` uses an active-set algorithm.

Example: `options = optimoptions('linprog','Algorithm','interior-point','Display','iter')`

`problem` — Problem structurestructure

Problem structure, specified as a structure with the following fields.

Field NameEntry

`f`

Linear objective function vector `f`

`Aineq`

Matrix for linear inequality constraints

`bineq`

Vector for linear inequality constraints

`Aeq`

Matrix for linear equality constraints

`beq`

Vector for linear equality constraints
`lb`Vector of lower bounds
`ub`Vector of upper bounds

`x0`

Initial point for `x`, active set algorithm only

`solver`

`'linprog'`

`options`

Options created with `optimoptions`

You must supply at least the `solver` field in the `problem` structure.

The simplest way to obtain a `problem` structure is to export the problem from the Optimization app.

Data Types: `struct`

Output Arguments

collapse all

`x` — Solutionreal vector | real array

Solution, returned as a real vector or real array. The size of `x` is the same as the size of `f` or `x0`.

`fval` — Objective function value at the solutionreal number

Objective function value at the solution, returned as a real number. Generally, `fval` = `f'*x`.

`exitflag` — Reason `linprog` stoppedinteger

Reason `linprog` stopped, returned as an integer.

 `1` Function converged to a solution `x`. `0` Number of iterations exceeded `options.MaxIter`. `-2` No feasible point was found. `-3` Problem is unbounded. `-4` `NaN` value was encountered during execution of the algorithm. `-5` Both primal and dual problems are infeasible. `-7` Search direction became too small. No further progress could be made.

`output` — Information about the optimization processstructure

Information about the optimization process, returned as a structure with these fields.

 `iterations` Number of iterations `algorithm` Optimization algorithm used `cgiterations` 0 (interior-point algorithm only, included for backward compatibility) `message` Exit message `constrviolation` Maximum of constraint functions `firstorderopt` First-order optimality measure

`lambda` — Lagrange multipliers at the solutionstructure

Lagrange multipliers at the solution, returned as a structure with these fields.

 `lower` Lower bounds corresponding to `lb` `upper` Upper bounds corresponding to `ub` `ineqlin` Linear inequalities corresponding to `A` and `b` `eqlin` Linear equalities corresponding to `Aeq` and `beq`

Limitations

• The `'active-set'` algorithm has only `'off'` and `'final'` as `Display` options; you cannot choose the iterative display option, `'iter'`.

expand all

Interior-Point-Legacy Algorithm

The `'interior-point-legacy'` method is based on LIPSOL (Linear Interior Point Solver, [3]), which is a variant of Mehrotra's predictor-corrector algorithm [2], a primal-dual interior-point method. A number of preprocessing steps occur before the algorithm begins to iterate. See Interior-Point-Legacy Linear Programming.

The first stage of the algorithm might involve some preprocessing of the constraints (see Interior-Point-Legacy Linear Programming). Several conditions might cause `linprog` to exit with an infeasibility message. In each case, `linprog` returns a negative `exitflag`, indicating to indicate failure.

• If a row of all zeros is detected in `Aeq`, but the corresponding element of `beq` is not zero, then the exit message is

```Exiting due to infeasibility: An all-zero row in the constraint matrix does not have a zero in corresponding right-hand-side entry.```
• If one of the elements of `x` is found not to be bounded below, then the exit message is

`Exiting due to infeasibility: Objective f'*x is unbounded below.`
• If one of the rows of `Aeq` has only one nonzero element, then the associated value in `x` is called a singleton variable. In this case, the value of that component of `x` can be computed from `Aeq` and `beq`. If the value computed violates another constraint, then the exit message is

```Exiting due to infeasibility: Singleton variables in equality constraints are not feasible.```
• If the singleton variable can be solved for, but the solution violates the upper or lower bounds, then the exit message is

```Exiting due to infeasibility: Singleton variables in the equality constraints are not within bounds.```
 Note   The preprocessing steps are cumulative. For example, even if your constraint matrix does not have a row of all zeros to begin with, other preprocessing steps can cause such a row to occur.

When the preprocessing finishes, the iterative part of the algorithm begins until the stopping criteria are met. (For more information about residuals, the primal problem, the dual problem, and the related stopping criteria, see Interior-Point-Legacy Linear Programming.) If the residuals are growing instead of getting smaller, or the residuals are neither growing nor shrinking, one of the two following termination messages is displayed, respectively,

```One or more of the residuals, duality gap, or total relative error has grown 100000 times greater than its minimum value so far:```

or

```One or more of the residuals, duality gap, or total relative error has stalled:```

After one of these messages is displayed, it is followed by one of the following messages indicating that the dual, the primal, or both appear to be infeasible.

• ```The dual appears to be infeasible (and the primal unbounded). (The primal residual < TolFun.)```

• ```The primal appears to be infeasible (and the dual unbounded). (The dual residual < TolFun.)```

• ```The dual appears to be infeasible (and the primal unbounded) since the dual residual > sqrt(TolFun). (The primal residual < 10*TolFun.)```

• ```The primal appears to be infeasible (and the dual unbounded) since the primal residual > sqrt(TolFun). (The dual residual < 10*TolFun.)```

• ```The dual appears to be infeasible and the primal unbounded since the primal objective < -1e+10 and the dual objective < 1e+6.```

• ```The primal appears to be infeasible and the dual unbounded since the dual objective > 1e+10 and the primal objective > -1e+6.```

• ```Both the primal and the dual appear to be infeasible.```

For example, the primal (objective) can be unbounded and the primal residual, which is a measure of primal constraint satisfaction, can be small.

Interior-Point Algorithm

The `'interior-point'` algorithm is similar to `'interior-point-legacy'`, but with a more efficient factorization routine, and with different preprocessing. See Interior-Point `linprog` Algorithm.

Dual-Simplex Algorithm

For a description, see Dual-Simplex Algorithm.

Active-Set and Simplex Algorithms

The `'active-set'` algorithm uses a projection method as used in the `quadprog` algorithm. `linprog` is an active set method and is thus a variation of the well-known simplex method for linear programming [1]. The algorithm finds an initial feasible solution by first solving another linear programming problem. For details, see Active-Set `linprog` Algorithm.

For a description of the `'simplex'` algorithm, see `linprog` Simplex Algorithm.

`linprog` gives a warning when the problem is infeasible.

```Warning: The constraints are overly stringent; there is no feasible solution.```

In this case, `linprog` produces a result that minimizes the worst-case constraint violation.

When the equality constraints are inconsistent, `linprog` gives

```Warning: The equality constraints are overly stringent; there is no feasible solution.```

Unbounded solutions result in the warning

```Warning: The solution is unbounded and at infinity; the constraints are not restrictive enough.```

In this case, `linprog` returns a value of `x` that satisfies the constraints.

References

[1] Dantzig, G.B., A. Orden, and P. Wolfe. "Generalized Simplex Method for Minimizing a Linear Form Under Linear Inequality Restraints." Pacific Journal Math., Vol. 5, 1955, pp. 183–195.

[2] Mehrotra, S. "On the Implementation of a Primal-Dual Interior Point Method." SIAM Journal on Optimization, Vol. 2, 1992, pp. 575–601.

[3] Zhang, Y., "Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment." Technical Report TR96-01, Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, July 1995.