linprog

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

x = linprog(f,A,b,Aeq,beq) includes 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.

Note

If the specified input bounds for a problem are inconsistent, the output fval is [].

x = linprog(f,A,b,Aeq,beq,lb,ub,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. You can also create a problem structure from an OptimizationProblem object by using prob2struct.

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

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

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

Examples

Linear Program, Linear Inequality Constraints

Solve a simple linear program defined by linear inequalities.

For this example, use these linear inequality constraints:

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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 $- x (1) - x (2) / 3$ .

f = [-1 -1/3];

Solve the linear program.

x = linprog(f,A,b)

Optimal solution found.

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:

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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 $x (1) + x (2) / 4 = 1 / 2$ .

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

Use the objective function $- x (1) - x (2) / 3$ .

f = [-1 -1/3];

Solve the linear program.

x = linprog(f,A,b,Aeq,beq)

Optimal solution found.

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:

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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 $x (1) + x (2) / 4 = 1 / 2$ .

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

Set these bounds:

$- 1 \leq x (1) \leq 1.5$

$- 0.5 \leq x (2) \leq 1.25 .$

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

Use the objective function $- x (1) - x (2) / 3$ .

f = [-1 -1/3];

Solve the linear program.

x = linprog(f,A,b,Aeq,beq,lb,ub)

Optimal solution found.

Linear Program Using the `'interior-point'` Algorithm

Solve a linear program using the 'interior-point' algorithm.

For this example, use these linear inequality constraints:

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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 $x (1) + x (2) / 4 = 1 / 2$ .

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

Set these bounds:

$- 1 \leq x (1) \leq 1.5$

$- 0.5 \leq x (2) \leq 1.25 .$

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

Use the objective function $- x (1) - x (2) / 3$ .

f = [-1 -1/3];

Set options to use the 'interior-point' algorithm.

options = optimoptions('linprog','Algorithm','interior-point');

Solve the linear program using the 'interior-point' algorithm.

x = linprog(f,A,b,Aeq,beq,lb,ub,options)

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the selected value of the function tolerance,
and constraints are satisfied to within the selected value of the constraint
tolerance.

Solve LP Using Problem-Based Approach for `linprog`

This example shows how to set up a problem using the problem-based approach and then solve it using the solver-based approach. The problem is

$\max_{x} (x + y / 3) s u b j e c t t o {\begin{array}{llllllllllllllllllll} x + y \leq 2 \\ x + y / 4 \leq 1 \\ x - y \leq 2 \\ x / 4 + y \geq - 1 \\ x + y \geq 1 \\ - x + y \leq 2 \\ x + y / 4 = 1 / 2 \\ - 1 \leq x \leq 1.5 \\ - 1 / 2 \leq y \leq 1.25 \end{array}$

Create an OptimizationProblem object named prob to represent this problem.

x = optimvar('x','LowerBound',-1,'UpperBound',1.5);
y = optimvar('y','LowerBound',-1/2,'UpperBound',1.25);
prob = optimproblem('Objective',x + y/3,'ObjectiveSense','max');
prob.Constraints.c1 = x + y <= 2;
prob.Constraints.c2 = x + y/4 <= 1;
prob.Constraints.c3 = x - y <= 2;
prob.Constraints.c4 = x/4 + y >= -1;
prob.Constraints.c5 = x + y >= 1;
prob.Constraints.c6 = -x + y <= 2;
prob.Constraints.c7 = x + y/4 == 1/2;

Convert the problem object to a problem structure.

problem = prob2struct(prob);

Solve the resulting problem structure.

[sol,fval,exitflag,output] = linprog(problem)

Optimal solution found.

sol = 2×1

    0.1875
    1.2500

fval = -0.6042

exitflag = 1

output = struct with fields:
         iterations: 0
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex'
      firstorderopt: 0

The returned fval is negative, even though the solution components are positive. Internally, prob2struct turns the maximization problem into a minimization problem of the negative of the objective function. See Maximizing an Objective.

Which component of sol corresponds to which optimization variable? Examine the Variables property of prob.

prob.Variables

ans = struct with fields:
    x: [1x1 optim.problemdef.OptimizationVariable]
    y: [1x1 optim.problemdef.OptimizationVariable]

As you might expect, sol(1) corresponds to x, and sol(2) corresponds to y. See Algorithms.

Return the Objective Function Value

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

The inequality constraints are

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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 $- x (1) - x (2) / 3$ .

f = [-1 -1/3];

Solve the problem and return the objective function value.

[x,fval] = linprog(f,A,b)

Optimal solution found.

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:

$x (1) + x (2) \leq 2$

$x (1) + x (2) / 4 \leq 1$

$x (1) - x (2) \leq 2$

$- x (1) / 4 - x (2) \leq 1$

$- x (1) - x (2) \leq - 1$

$- x (1) + x (2) \leq 2 .$

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 $x (1) + x (2) / 4 = 1 / 2$ .

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

Set these bounds:

$- 1 \leq x (1) \leq 1.5$

$- 0.5 \leq x (2) \leq 1.25 .$

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

Use the objective function $- x (1) - x (2) / 3$ .

f = [-1 -1/3];

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

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

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,options)

Optimal solution found.

fval = -0.6042

exitflag = 1

output = struct with fields:
         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 (x) = - 5 x_{1} - 4 x_{2} - 6 x_{3} .$

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

Use the linear inequality constraints

$x_{1} - x_{2} + x_{3} \leq 20$

$3 x_{1} + 2 x_{2} + 4 x_{3} \leq 42$

$3 x_{1} + 2 x_{2} \leq 30 .$

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

Constrain all variables to be positive:

$x_{1} \geq 0$

$x_{2} \geq 0$

$x_{3} \geq 0 .$

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);

Optimal solution found.

Examine the solution and Lagrange multipliers.

x,lambda.ineqlin,lambda.lower

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:

$3 x_{1} + 2 x_{2} + 4 x_{3} = 42$

$3 x_{1} + 2 x_{2} = 30 .$

Check that this is true:

A*x

ans = 3×1

  -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

`f` — Coefficient vector
real vector | real array

Coefficient vector, specified as a real vector or real array. The coefficient vector represents the objective function f'*x. The notation assumes that f is a column vector, but you are free to use a row vector or array. Internally, linprog converts f to the column vector f(:).

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

Data Types: double

`A` — Linear inequality constraints
real 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 (length of f). 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

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 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

`Aeq` — Linear equality constraints
real 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 (length of f). 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

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 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

`b` — Linear inequality constraints
real 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

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30,

enter 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, use A = ones(1,N) and b = 1.

Data Types: double

`beq` — Linear equality constraints
real 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 Me-by-N.

For example, to specify

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20,

enter these constraints:

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

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

Data Types: double

`lb` — Lower bounds
real vector | real array

Lower bounds, specified as a real vector or real array. If the length of f is equal to that of lb, then lb specifies that

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

If numel(lb) < numel(f), 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(f))

Data Types: double

`ub` — Upper bounds
real vector | real array

Upper bounds, specified as a real vector or real array. If the length of f is equal to that of ub, then ub specifies that

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

If numel(ub) < numel(f), 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(f))

Data Types: double

`options` — Optimization options
output 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.

Some options are absent from the optimoptions display. These options appear in italics in the following table. For details, see View Options.

All Algorithms
`Algorithm`	Choose the optimization algorithm: `'dual-simplex'` (default) `'interior-point-legacy'` `'interior-point'` 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.
`MaxIterations`	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 See Tolerances and Stopping Criteria and Iterations and Function Counts. For `optimset`, the name is `MaxIter`. See Current and Legacy Option Name Tables.
`OptimalityTolerance`	Termination tolerance on the dual feasibility, a positive scalar. The default is: `1e-8` for the `'interior-point-legacy'` algorithm `1e-7` for the `'dual-simplex'` algorithm `1e-6` for the `'interior-point'` algorithm For `optimset`, the name is `TolFun`. See Current and Legacy Option Name Tables.
interior-point Algorithm
`ConstraintTolerance`	Feasibility tolerance for constraints, a scalar from `1e-10` through `1e-3`. `ConstraintTolerance` measures primal feasibility tolerance. The default is `1e-6`. For `optimset`, the name is `TolCon`. See Current and Legacy Option Name Tables.
Preprocess	Level of LP preprocessing prior to algorithm iterations. Specify `'basic'` (default) or `'none'`.
Dual-Simplex Algorithm
`ConstraintTolerance`	Feasibility tolerance for constraints, a scalar from `1e-10` through `1e-3`. `ConstraintTolerance` measures primal feasibility tolerance. The default is `1e-4`. For `optimset`, the name is `TolCon`. See Current and Legacy Option Name Tables.
`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'`.

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

`problem` — Problem structure
structure

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

Field Name	Entry
`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
`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

`x` — Solution
real vector | real array

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

`fval` — Objective function value at the solution
real number

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

`exitflag` — Reason `linprog` stopped
integer

Reason linprog stopped, returned as an integer.

`3`	The solution is feasible with respect to the relative `ConstraintTolerance` tolerance, but is not feasible with respect to the absolute tolerance.
`1`	Function converged to a solution `x`.
`0`	Number of iterations exceeded `options.MaxIterations` or solution time in seconds exceeded `options.MaxTime`.
`-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.
`-9`	Solver lost feasibility.

Exitflags 3 and -9 relate to solutions that have large infeasibilities. These usually arise from linear constraint matrices that have large condition number, or problems that have large solution components. To correct these issues, try to scale the coefficient matrices, eliminate redundant linear constraints, or give tighter bounds on the variables.

`output` — Information about the optimization process
structure

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 solution
structure

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`

Algorithms