# linprog

Solve linear programming problems

## Equation

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)x = linprog(f,A,b,Aeq,beq)x = linprog(f,A,b,Aeq,beq,lb,ub)x = linprog(f,A,b,Aeq,beq,lb,ub,x0)x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)x = linprog(problem)[x,fval] = linprog(...)[x,fval,exitflag] = linprog(...)[x,fval,exitflag,output] = linprog(...)[x,fval,exitflag,output,lambda] = linprog(...)`

## Description

`linprog` solves linear programming problems.

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

`x = linprog(f,A,b,Aeq,beq)` solves the problem above while additionally satisfying the equality constraints `Aeq*x = beq`. Set `A = []` and `b = []` if no inequalities exist.

`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.

`x = linprog(f,A,b,Aeq,beq,lb,ub,x0)` sets the starting point to `x0`. `linprog` uses `x0` only with the `active-set` algorithm. `linprog` ignores `x0` with the `interior-point` and `simplex` algorithms.

`x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)` minimizes with the optimization options specified in `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.

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

`[x,fval,exitflag] = linprog(...)` returns a value `exitflag` that describes the exit condition.

`[x,fval,exitflag,output] = linprog(...)` returns a structure `output` that contains information about the optimization.

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

 Note:   If the specified input bounds for a problem are inconsistent, the output `x` is `x0` and the output `fval` is `[]`.

## Input Arguments

Function Arguments contains general descriptions of arguments passed into `linprog`. Options provides the function-specific details for the `options` values.

 `problem` `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`

## Output Arguments

Function Arguments contains general descriptions of arguments returned by `linprog`. This section provides function-specific details for `exitflag`, `lambda`, and `output`:

 `exitflag` Integer identifying the reason the algorithm terminated. The following lists the values of `exitflag` and the corresponding reasons the algorithm terminated. `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. `lambda` Structure containing the Lagrange multipliers at the solution `x` (separated by constraint type). The fields of the structure are: `lower` Lower bounds `lb` `upper` Upper bounds `ub` `ineqlin` Linear inequalities `eqlin` Linear equalities `output` Structure containing information about the optimization. The fields of the structure are: `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

## Options

Optimization options used by `linprog`. Some options apply to all algorithms, and others are only relevant when using the interior-point algorithm. Use `optimoptions` to set or change `options`. See Optimization Options Reference for detailed information.

### All Algorithms

All `linprog` algorithms use the following options:

 `Algorithm` Choose the optimization algorithm:`'interior-point'` (default)`'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. The choices are `'on'` or the default `'off'`. `Display` Level of display.`'off'` or `'none'` displays no output.`'iter'` displays output at each iteration. The `'iter'` option is unavailable for the `'active-set'` algorithm.`'final'` (default) displays just the final output. `LargeScale`Use `Algorithm` instead Use the `'interior-point'` algorithm when set to `'on'` (default). Use a medium-scale algorithm when set to `'off'` (see `Simplex` in `simplex` Algorithm Only). For information on choosing the algorithm, see Choosing the Algorithm. `MaxIter` Maximum number of iterations allowed, a positive integer. The default is:`85` 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 `'simplex'` algorithmThe option is not used for the `'active-set'` algorithm`TolFun` measures dual feasibility tolerance.

### `simplex` Algorithm Only

The `'simplex'` algorithm uses the following option:

 `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. See Active-Set and Simplex Algorithms for more information and an example.

### `dual-simplex` Algorithm Only

The `'dual-simplex'` algorithm uses the following options:

 `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. Choices are `'none'` or the default `'basic'`. `TolCon` Feasibility tolerance for constraints, a scalar from `1e-10` through `1e-3`. `TolCon` measures primal feasibility tolerance. The default is `1e-4`.

## Examples

Find `x` that minimizes

f(x) = –5x1 – 4x2 –6x3,

subject to

x1x2 + x3 ≤ 20
3x1 + 2x2 + 4x3 ≤ 42
3x1 + 2x2 ≤ 30
0 ≤ x1, 0 ≤ x2, 0 ≤ x3.

First, enter the coefficients

```f = [-5; -4; -6]; A = [1 -1 1 3 2 4 3 2 0]; b = [20; 42; 30]; lb = zeros(3,1);```

Next, call a linear programming routine.

`[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb);`

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```

Nonzero elements of the vectors in the fields of `lambda` indicate active constraints at the solution. In this case, the second and third inequality constraints (in `lambda.ineqlin`) and the first lower bound constraint (in `lambda.lower`) are active constraints (i.e., the solution is on their constraint boundaries).

## Diagnostics

### Interior-Point Algorithm

The first stage of the algorithm might involve some preprocessing of the constraints (see Interior-Point Linear Programming). Several possible conditions might occur that cause `linprog` to exit with an infeasibility message. In each case, the `exitflag` argument returned by `linprog` is set to a negative value to indicate failure.

If a row of all zeros is detected in `Aeq` but the corresponding element of `beq` is not zero, 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, 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, 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, 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, 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 may cause such a row to occur.

Once the preprocessing has finished, the iterative part of the algorithm begins until the stopping criteria are met. (See Interior-Point Linear Programming for more information about residuals, the primal problem, the dual problem, and the related stopping criteria.) 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 six messages indicating that the dual, the primal, or both appear to be infeasible. The messages differ according to how the infeasibility or unboundedness was measured.

```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.```

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

### Active-Set and Simplex Algorithms

`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.

## Limitations

### Active-Set Algorithm

At this time, the only levels of display, using the `Display` option in `options`, are `'off'` and `'final'`; iterative output using `'iter'` is not available.

### Interior-Point Algorithm

Coverage and Requirements

For Large Problems

A and Aeq should be sparse.

collapse all

### Interior-Point Algorithm

The interior-point 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 Linear Programming.

### Dual Simplex Algorithm

For a description of the `'dual-simplex'` algorithm, see Dual-Simplex Algorithm.

### Active-Set and Simplex Algorithms

`linprog` 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.

Alternatively, you can use the simplex algorithm, described in `linprog` Simplex Algorithm, by entering

`options = optimoptions('linprog','Algorithm','simplex')`

and passing `options` as an input argument to `linprog`. The simplex algorithm returns a vertex optimal solution.

 Note   `linprog` uses `x0` only for the `'active-set'` algorithm. For all other algorithms, `linprog` ignores `x0`.

## 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, pp. 183–195, 1955.

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

[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.