# intlinprog

Mixed-integer linear programming (MILP)

## Syntax

``x = intlinprog(f,intcon,A,b)``
``x = intlinprog(f,intcon,A,b,Aeq,beq)``
``x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)``
``x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0)``
``x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options)``
``x = intlinprog(problem)``
``````[x,fval,exitflag,output] = intlinprog(___)``````

## Description

Mixed-integer linear programming solver.

Finds the minimum of a problem specified by

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

You can specify f, intcon, lb, and ub as vectors or arrays. See Matrix Arguments.

Note

`intlinprog` applies only to the solver-based approach. For a discussion of the two optimization approaches, see First Choose Problem-Based or Solver-Based Approach.

````x = intlinprog(f,intcon,A,b)` solves min `f'*x` such that the components of `x` in `intcon` are integers, and `A*x ≤ b`.```

example

````x = intlinprog(f,intcon,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 = intlinprog(f,intcon,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.```

example

````x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0)`optimizes using an initial feasible point `x0`. Set `lb = []` and `ub = []` if no bounds exist.```

example

````x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options)` minimizes using the optimization options specified in `options`. Use `optimoptions` to set these options. Set `x0 = []` if no initial point exists.```

example

````x = intlinprog(problem)` uses a `problem` structure to encapsulate all solver inputs. 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`.```

example

``````[x,fval,exitflag,output] = intlinprog(___)```, for any input arguments described above, returns `fval = f'*x`, a value `exitflag` describing the exit condition, and a structure `output` containing information about the optimization process.```

example

## Examples

collapse all

Solve the problem

`$\underset{x}{\mathrm{min}}8{x}_{1}+{x}_{2}\phantom{\rule{0.5em}{0ex}}subject\phantom{\rule{0.5em}{0ex}}to\phantom{\rule{0.5em}{0ex}}\left\{\begin{array}{l}{x}_{2}\phantom{\rule{0.5em}{0ex}}is\phantom{\rule{0.5em}{0ex}}an\phantom{\rule{0.5em}{0ex}}integer\\ {x}_{1}+2{x}_{2}\ge -14\\ -4{x}_{1}-{x}_{2}\le -33\\ 2{x}_{1}+{x}_{2}\le 20.\end{array}$`

Write the objective function vector and vector of integer variables.

```f = [8;1]; intcon = 2;```

Convert all inequalities into the form `A*x <= b` by multiplying “greater than” inequalities by `-1`.

```A = [-1,-2; -4,-1; 2,1]; b = [14;-33;20];```

Call `intlinprog`.

`x = intlinprog(f,intcon,A,b)`
```Running HiGHS 1.7.0: Copyright (c) 2024 HiGHS under MIT licence terms Coefficient ranges: Matrix [1e+00, 4e+00] Cost [1e+00, 8e+00] Bound [0e+00, 0e+00] RHS [1e+01, 3e+01] Presolving model 3 rows, 2 cols, 6 nonzeros 0s 3 rows, 2 cols, 6 nonzeros 0s Solving MIP model with: 3 rows 2 cols (0 binary, 1 integer, 0 implied int., 1 continuous) 6 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% -inf inf inf 0 0 0 0 0.0s T 0 0 0 0.00% -inf 59 Large 0 0 0 3 0.0s Solving report Status Optimal Primal bound 59 Dual bound 59 Gap 0% (tolerance: 0.01%) Solution status feasible 59 (objective) 0 (bound viol.) 1.7763568394e-15 (int. viol.) 0 (row viol.) Timing 0.00 (total) 0.00 (presolve) 0.00 (postsolve) Nodes 1 LP iterations 3 (total) 0 (strong br.) 0 (separation) 0 (heuristics) Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06. ```
```x = 2×1 6.5000 7.0000 ```

Solve the problem

`$\underset{x}{\mathrm{min}}\left(-3{x}_{1}-2{x}_{2}-{x}_{3}\right)\phantom{\rule{0.5em}{0ex}}subject\phantom{\rule{0.5em}{0ex}}to\left\{\begin{array}{l}{x}_{3}\phantom{\rule{0.5em}{0ex}}binary\\ {x}_{1},{x}_{2}\ge 0\\ {x}_{1}+{x}_{2}+{x}_{3}\le 7\\ 4{x}_{1}+2{x}_{2}+{x}_{3}=12.\end{array}$`

Write the objective function vector and vector of integer variables.

```f = [-3;-2;-1]; intcon = 3;```

Write the linear inequality constraints.

```A = [1,1,1]; b = 7;```

Write the linear equality constraints.

```Aeq = [4,2,1]; beq = 12;```

Write the bound constraints.

```lb = zeros(3,1); ub = [Inf;Inf;1]; % Enforces x(3) is binary```

Call `intlinprog`.

`x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)`
```Running HiGHS 1.7.0: Copyright (c) 2024 HiGHS under MIT licence terms Coefficient ranges: Matrix [1e+00, 4e+00] Cost [1e+00, 3e+00] Bound [1e+00, 1e+00] RHS [7e+00, 1e+01] Presolving model 2 rows, 3 cols, 6 nonzeros 0s 0 rows, 0 cols, 0 nonzeros 0s Presolve: Optimal Solving report Status Optimal Primal bound -12 Dual bound -12 Gap 0% (tolerance: 0.01%) Solution status feasible -12 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 0.00 (total) 0.00 (presolve) 0.00 (postsolve) Nodes 0 LP iterations 0 (total) 0 (strong br.) 0 (separation) 0 (heuristics) Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06. ```
```x = 3×1 0 6 0 ```

Compare the number of steps to solve an integer programming problem both with and without an initial feasible point. The problem has eight variables, four linear equality constraints, and has all variables restricted to be positive.

Define the linear equality constraint matrix and vector.

```Aeq = [22 13 26 33 21 3 14 26 39 16 22 28 26 30 23 24 18 14 29 27 30 38 26 26 41 26 28 36 18 38 16 26]; beq = [ 7872 10466 11322 12058];```

Set lower bounds that restrict all variables to be nonnegative.

```N = 8; lb = zeros(N,1);```

Specify that all variables are integer-valued.

`intcon = 1:N;`

Set the objective function vector `f`.

`f = [2 10 13 17 7 5 7 3];`

Solve the problem without using an initial point, and examine the display to see the number of branch-and-bound nodes.

`[x1,fval1,exitflag1,output1] = intlinprog(f,intcon,[],[],Aeq,beq,lb);`
```Running HiGHS 1.7.0: Copyright (c) 2024 HiGHS under MIT licence terms Coefficient ranges: Matrix [3e+00, 4e+01] Cost [2e+00, 2e+01] Bound [0e+00, 0e+00] RHS [8e+03, 1e+04] Presolving model 4 rows, 8 cols, 32 nonzeros 0s 4 rows, 8 cols, 27 nonzeros 0s Objective function is integral with scale 1 Solving MIP model with: 4 rows 8 cols (0 binary, 8 integer, 0 implied int., 0 continuous) 27 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s 0 0 0 0.00% 1554.047531 inf inf 0 0 4 4 0.0s T 20753 210 8189 98.04% 1783.696925 1854 3.79% 30 8 9884 19222 3.0s Solving report Status Optimal Primal bound 1854 Dual bound 1854 Gap 0% (tolerance: 0.01%) Solution status feasible 1854 (objective) 0 (bound viol.) 9.63673585375e-14 (int. viol.) 0 (row viol.) Timing 3.08 (total) 0.00 (presolve) 0.00 (postsolve) Nodes 21163 LP iterations 19608 (total) 223 (strong br.) 76 (separation) 1018 (heuristics) Optimal solution found. Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06. ```

For comparison, find the solution using an initial feasible point.

```x0 = [8 62 23 103 53 84 46 34]; [x2,fval2,exitflag2,output2] = intlinprog(f,intcon,[],[],Aeq,beq,lb,[],x0);```
```Running HiGHS 1.7.0: Copyright (c) 2024 HiGHS under MIT licence terms Coefficient ranges: Matrix [3e+00, 4e+01] Cost [2e+00, 2e+01] Bound [0e+00, 0e+00] RHS [8e+03, 1e+04] Assessing feasibility of MIP using primal feasibility and integrality tolerance of 1e-06 Solution has num max sum Col infeasibilities 0 0 0 Integer infeasibilities 0 0 0 Row infeasibilities 0 0 0 Row residuals 0 0 0 Presolving model 4 rows, 8 cols, 32 nonzeros 0s 4 rows, 8 cols, 27 nonzeros 0s MIP start solution is feasible, objective value is 3901 Objective function is integral with scale 1 Solving MIP model with: 4 rows 8 cols (0 binary, 8 integer, 0 implied int., 0 continuous) 27 nonzeros Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time 0 0 0 0.00% 0 3901 100.00% 0 0 0 0 0.0s 0 0 0 0.00% 1554.047531 3901 60.16% 0 0 4 4 0.0s T 6266 708 2644 73.61% 1662.791423 3301 49.63% 20 6 9746 10699 1.6s T 9340 919 3970 80.72% 1692.410008 2687 37.01% 29 6 9995 16120 2.4s T 21750 192 9514 96.83% 1791.542628 1854 3.37% 20 6 9984 40278 5.8s Solving report Status Optimal Primal bound 1854 Dual bound 1854 Gap 0% (tolerance: 0.01%) Solution status feasible 1854 (objective) 0 (bound viol.) 1.42108547152e-13 (int. viol.) 0 (row viol.) Timing 5.86 (total) 0.00 (presolve) 0.00 (postsolve) Nodes 22163 LP iterations 40863 (total) 538 (strong br.) 64 (separation) 2782 (heuristics) Optimal solution found. Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06. ```
• Without an initial point, `intlinprog` took about 30,000 branch-and-bound steps.

• Using an initial point, `intlinprog` took about 5,000 steps.

Giving an initial point does not always help. For this problem, giving an initial point saves time and computational steps. However, for some problems, giving an initial point can cause `intlinprog` to take more steps.

Solve the problem

`$\underset{x}{\mathrm{min}}\left(-3{x}_{1}-2{x}_{2}-{x}_{3}\right)\phantom{\rule{0.5em}{0ex}}subject\phantom{\rule{0.5em}{0ex}}to\left\{\begin{array}{l}{x}_{3}\phantom{\rule{0.5em}{0ex}}binary\\ {x}_{1},{x}_{2}\ge 0\\ {x}_{1}+{x}_{2}+{x}_{3}\le 7\\ 4{x}_{1}+2{x}_{2}+{x}_{3}=12\end{array}$`

without showing iterative display.

Specify the solver inputs.

```f = [-3;-2;-1]; intcon = 3; A = [1,1,1]; b = 7; Aeq = [4,2,1]; beq = 12; lb = zeros(3,1); ub = [Inf;Inf;1]; % enforces x(3) is binary x0 = [];```

Specify no display.

`options = optimoptions('intlinprog','Display','off');`

Run the solver.

`x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x0,options)`
```x = 3×1 0 6 0 ```

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

`$\underset{x}{\mathrm{min}}\left(-3{x}_{1}-2{x}_{2}-{x}_{3}\right)\phantom{\rule{0.5em}{0ex}}subject\phantom{\rule{0.5em}{0ex}}to\phantom{\rule{0.5em}{0ex}}\left\{\begin{array}{l}{x}_{3}\phantom{\rule{0.5em}{0ex}}binary\\ {x}_{1},{x}_{2}\ge 0\\ {x}_{1}+{x}_{2}+{x}_{3}\le 7\\ 4{x}_{1}+2{x}_{2}+{x}_{3}=12\end{array}$`

Create an `OptimizationProblem` object named `prob` to represent this problem. To specify a binary variable, create an optimization variable with integer type, a lower bound of 0, and an upper bound of 1.

```x = optimvar('x',2,'LowerBound',0); xb = optimvar('xb','LowerBound',0,'UpperBound',1,'Type','integer'); prob = optimproblem('Objective',-3*x(1)-2*x(2)-xb); cons1 = sum(x) + xb <= 7; cons2 = 4*x(1) + 2*x(2) + xb == 12; prob.Constraints.cons1 = cons1; prob.Constraints.cons2 = cons2;```

Convert the problem object to a problem structure.

`problem = prob2struct(prob);`

Solve the resulting problem structure.

`[sol,fval,exitflag,output] = intlinprog(problem)`
```Running HiGHS 1.7.0: Copyright (c) 2024 HiGHS under MIT licence terms Coefficient ranges: Matrix [1e+00, 4e+00] Cost [1e+00, 3e+00] Bound [1e+00, 1e+00] RHS [7e+00, 1e+01] Presolving model 2 rows, 3 cols, 6 nonzeros 0s 0 rows, 0 cols, 0 nonzeros 0s Presolve: Optimal Solving report Status Optimal Primal bound -12 Dual bound -12 Gap 0% (tolerance: 0.01%) Solution status feasible -12 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 0.00 (total) 0.00 (presolve) 0.00 (postsolve) Nodes 0 LP iterations 0 (total) 0 (strong br.) 0 (separation) 0 (heuristics) Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06. ```
```sol = 3×1 0 6 0 ```
```fval = -12 ```
```exitflag = 1 ```
```output = struct with fields: relativegap: 0 absolutegap: 0 numfeaspoints: 0 numnodes: 0 constrviolation: 0 algorithm: 'highs' message: 'Optimal solution found....' ```

Both `sol(1)` and `sol(3)` are binary-valued. Which value corresponds to the binary optimization variable `xb`?

`prob.Variables`
```ans = struct with fields: x: [2x1 optim.problemdef.OptimizationVariable] xb: [1x1 optim.problemdef.OptimizationVariable] ```

The variable `xb` appears last in the `Variables` display, so `xb` corresponds to `sol(3) = 1`. See Algorithms.

Call `intlinprog` with more outputs to see solution details and process.

The goal is to solve the problem

`$\underset{x}{\mathrm{min}}\left(-3{x}_{1}-2{x}_{2}-{x}_{3}\right)\phantom{\rule{0.5em}{0ex}}subject\phantom{\rule{0.5em}{0ex}}to\left\{\begin{array}{l}{x}_{3}\phantom{\rule{0.5em}{0ex}}binary\\ {x}_{1},{x}_{2}\ge 0\\ {x}_{1}+{x}_{2}+{x}_{3}\le 7\\ 4{x}_{1}+2{x}_{2}+{x}_{3}=12.\end{array}$`

Specify the solver inputs.

```f = [-3;-2;-1]; intcon = 3; A = [1,1,1]; b = 7; Aeq = [4,2,1]; beq = 12; lb = zeros(3,1); ub = [Inf;Inf;1]; % enforces x(3) is binary```

Call `intlinprog` with all outputs.

`[x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)`
```Running HiGHS 1.7.0: Copyright (c) 2024 HiGHS under MIT licence terms Coefficient ranges: Matrix [1e+00, 4e+00] Cost [1e+00, 3e+00] Bound [1e+00, 1e+00] RHS [7e+00, 1e+01] Presolving model 2 rows, 3 cols, 6 nonzeros 0s 0 rows, 0 cols, 0 nonzeros 0s Presolve: Optimal Solving report Status Optimal Primal bound -12 Dual bound -12 Gap 0% (tolerance: 0.01%) Solution status feasible -12 (objective) 0 (bound viol.) 0 (int. viol.) 0 (row viol.) Timing 0.00 (total) 0.00 (presolve) 0.00 (postsolve) Nodes 0 LP iterations 0 (total) 0 (strong br.) 0 (separation) 0 (heuristics) Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are integer within tolerance, options.ConstraintTolerance = 1e-06. ```
```x = 3×1 0 6 0 ```
```fval = -12 ```
```exitflag = 1 ```
```output = struct with fields: relativegap: 0 absolutegap: 0 numfeaspoints: 0 numnodes: 0 constrviolation: 0 algorithm: 'highs' message: 'Optimal solution found....' ```

The output structure shows `numnodes` is `0`. This means `intlinprog` solved the problem before branching. This is one indication that the result is reliable. Also, the `absolutegap` and `relativegap` fields are `0`. This is another indication that the result is reliable.

## Input Arguments

collapse all

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(:)`.

If you specify `f = []`, `intlinprog` tries to find a feasible point without trying to minimize an objective function.

Example: `f = [4;2;-1.7];`

Data Types: `double`

Vector of integer constraints, specified as a vector of positive integers. The values in `intcon` indicate the components of the decision variable `x` that are integer-valued. `intcon` has values from `1` through `numel(f)`.

`intcon` can also be an array. Internally, `intlinprog` converts an array `intcon` to the vector `intcon(:)`.

Example: `intcon = [1,2,7]` means `x(1)`, `x(2)`, and `x(7)` take only integer values.

Data Types: `double`

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, consider these inequalities:

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

Specify the inequalities by entering the following 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`

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, consider these inequalities:

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

Specify the inequalities by entering the following 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: `single` | `double`

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, consider these equalities:

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

Specify the equalities by entering the following 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`

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, consider these equalities:

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

Specify the equalities by entering the following 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: `single` | `double`

Lower bounds, specified as a vector or array of doubles. `lb` represents the lower bounds elementwise in `lb `` x `` ub`.

Internally, `intlinprog` converts an array `lb` to the vector `lb(:)`.

Example: `lb = [0;-Inf;4]` means ```x(1) ≥ 0```, `x(3) ≥ 4`.

Data Types: `double`

Upper bounds, specified as a vector or array of doubles. `ub` represents the upper bounds elementwise in `lb `` x `` ub`.

Internally, `intlinprog` converts an array `ub` to the vector `ub(:)`.

Example: `ub = [Inf;4;10]` means ```x(2) ≤ 4```, `x(3) ≤ 10`.

Data Types: `double`

Initial point, specified as a real array. The number of elements in `x0` is the same as the number of elements of `f`, when `f` exists. Otherwise, the number is the same as the number of columns of `A` or `Aeq`. Internally, the solver converts an array `x0` into a vector `x0(:)`.

Providing `x0` can change the amount of time `intlinprog` takes to converge. It is difficult to predict how `x0` affects the solver. For suggestions on using appropriate `Heuristics` with `x0`, see Tips.

For the `"legacy"` algorithm, `x0` must be feasible with respect to all constraints. If `x0` is not feasible, the solver warns and ignores `x0`. If you do not have a feasible `x0` for this algorithm, set ```x0 = []```.

The `"highs"` algorithm attempts to use any supplied `x0`, modifying the point if necessary for feasibility.

Example: `x0 = 100*rand(size(f))`

Data Types: `double`

Options for `intlinprog`, specified as the output of `optimoptions`.

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

All Algorithms
OptionDescriptionDefault
`AbsoluteGapTolerance`

Nonnegative real. `intlinprog` stops if the difference between the internally calculated upper (`U`) and lower (`L`) bounds on the objective function is less than or equal to `AbsoluteGapTolerance`:

```U – L <= AbsoluteGapTolerance```.

`1e-6` for `"highs"`, `0` for `"legacy"`
`Algorithm`

Choose the optimization algorithm:

• `"highs"` (default)

• `"legacy"`

`"highs"`
`ConstraintTolerance`

For the `"highs"` algorithm, a real value from `1e-10` through `1e-3` representing the maximum allowable violation of integer or linear constraints.

For the `"legacy"` algorithm, a real value from `1e-10` through `1e-3` that is the maximum discrepancy that linear constraints can have and still be considered satisfied.

`ConstraintTolerance` is not a stopping criterion.

`1e-6` for `"highs"`, `1e-4` for `"legacy"`
`Display`

Level of display (see Iterative Display):

• `"off"` or `"none"` — No iterative display

• `"final"` — Show final values only

• `"iter"` — Show iterative display

`"iter"`
`MaxFeasiblePoints`Strictly positive integer. `intlinprog` stops if it finds `MaxFeasiblePoints` integer feasible points.`Inf`
`MaxNodes`Strictly positive integer that is the maximum number of nodes `intlinprog` explores in its branch-and-bound process.`1e7`
`MaxTime`Nonnegative real that is the maximum time in seconds that `intlinprog` runs.`7200`
`ObjectiveCutOff`Real greater than `-Inf`. During the branch-and-bound calculation, `intlinprog` discards any node where the linear programming solution has an objective value exceeding `ObjectiveCutOff`.`Inf`
`OutputFcn`

One or more functions that an optimization function calls at events. Specify as `'savemilpsolutions'`, a function handle, or a cell array of function handles. For custom output functions, pass function handles. An output function can stop the solver.

• `'savemilpsolutions'` collects the integer-feasible points in the `xIntSol` matrix in your workspace, where each column is one integer feasible point.

For information on writing a custom output function, see intlinprog Output Function and Plot Function Syntax.

`[]`
`PlotFcn`

Plots various measures of progress while the algorithm executes; select from predefined plots or write your own. Pass `'optimplotmilp'`, a function handle, or a cell array of function handles. For custom plot functions, pass function handles. The default is none (`[]`):

• `'optimplotmilp'` plots the internally-calculated upper and lower bounds on the objective value of the solution.

For information on writing a custom plot function, see intlinprog Output Function and Plot Function Syntax.

`[]`
`RelativeGapTolerance`

Real from `0` through `1`. `intlinprog` stops if the relative difference between the internally calculated upper (`U`) and lower (`L`) bounds on the objective function is less than or equal to `RelativeGapTolerance`:

For the `"highs"` algorithm, the stopping test is

```(U – L)/|U| <= RelativeGapTolerance```.

When `U` = 0 and `L` = 0, the returned ratio ```(U – L)/|U|``` is 0. When `U` = 0 and `L` is not 0, the returned ratio is `Inf`.

For the `"legacy"` algorithm, the stopping test is

```(U – L)/(|U| + 1) <= RelativeGapTolerance```.

Note

Although you specify `RelativeGapTolerance` as a decimal number, the iterative display reports the gap as a percentage, meaning 100 times the measured relative gap. If the exit message refers to the relative gap, this value is the measured relative gap, not a percentage.

`1e-4`
Legacy Algorithm
`BranchRule`

Rule for choosing the component for branching:

• `'maxpscost'` — The fractional component with maximum pseudocost. See Branch and Bound.

• `'strongpscost'` — The fractional component with maximum pseudocost and a more accurate estimate of pseudocost than in `'maxpscost'`. See Branch and Bound.

• `'reliability'` — The fractional component with maximum pseudocost and an even more accurate estimate of pseudocost than in `'strongpscost'`. See Branch and Bound.

• `'mostfractional'` — The component whose fractional part is closest to `1/2`.

• `'maxfun'` — The fractional component with a maximal corresponding component in the absolute value of the objective vector `f`.

`'reliability'`
`CutGeneration`

Level of cut generation (see Cut Generation):

• `'none'` — No cuts. Makes `CutMaxIterations` irrelevant.

• `'basic'` — Normal cut generation.

• `'intermediate'` — Use more cut types.

• `'advanced'` — Use most cut types.

`'basic'`
`CutMaxIterations`Number of passes through all cut generation methods before entering the branch-and-bound phase, an integer from `1` through `50`. Disable cut generation by setting the `CutGeneration` option to `'none'`.`10`
`Heuristics`

Algorithm for searching for feasible points (see Heuristics for Finding Feasible Solutions):

• `'basic'`

• `'intermediate'`

• `'advanced'`

• `'rss'`

• `'rins'`

• `'round'`

• `'diving'`

• `'rss-diving'`

• `'rins-diving'`

• `'round-diving'`

• `'none'`

`'basic'`
`HeuristicsMaxNodes`Strictly positive integer that bounds the number of nodes `intlinprog` can explore in its branch-and-bound search for feasible points. Applies only to `'rss'` and `'rins'`. See Heuristics for Finding Feasible Solutions.`50`
`IntegerPreprocess`

Types of integer preprocessing (see Mixed-Integer Program Preprocessing):

• `'none'` — Use very few integer preprocessing steps.

• `'basic'` — Use a moderate number of integer preprocessing steps.

• `'advanced'` — Use all available integer preprocessing steps.

`'basic'`
`IntegerTolerance`Real from `1e-10` through `1e-3`, where the maximum deviation from integer that a component of the solution `x` can have and still be considered an integer. `IntegerTolerance` is not a stopping criterion.`1e-5`
`LPMaxIterations`Strictly positive integer, the maximum number of simplex algorithm iterations per node during the branch-and-bound process.

```max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables))```

In this expression, `numberOfEqualities` means the number of rows of `Aeq`, `numberOfInequalities` means the number of rows of `A`, and `numberOfVariables` means the number of elements of `f`.

`LPOptimalityTolerance`Nonnegative real where reduced costs must exceed `LPOptimalityTolerance` for a variable to be taken into the basis.`1e-7`
LPPreprocess

Type of preprocessing for the solution to the relaxed linear program (see Linear Program Preprocessing):

• `'none'` — No preprocessing.

• `'basic'` — Use preprocessing.

`'basic'`
`NodeSelection`

Choose the node to explore next.

• `'simplebestproj'` — Best projection. See Branch and Bound.

• `'minobj'` — Explore the node with the minimum objective function.

• `'mininfeas'` — Explore the node with the minimal sum of integer infeasibilities. See Branch and Bound.

`'simplebestproj'`
`ObjectiveImprovementThreshold`Nonnegative real. `intlinprog` changes the current feasible solution only when it locates another with an objective function value that is at least `ObjectiveImprovementThreshold` lower: (fold – fnew)/(1 + |fold|) > ObjectiveImprovementThreshold.`0`
`RootLPAlgorithm`

Algorithm for solving linear programs:

• `'dual-simplex'` — Dual simplex algorithm

• `'primal-simplex'` — Primal simplex algorithm

`'dual-simplex'`
`RootLPMaxIterations`Nonnegative integer that is the maximum number of simplex algorithm iterations to solve the initial linear programming problem.

```max(3e4, 10*(numberOfEqualities + numberOfInequalities + numberOfVariables))```

In this expression, `numberOfEqualities` means the number of rows of `Aeq`, `numberOfInequalities` means the number of rows of `A`, and `numberOfVariables` means the number of elements of `f`.

Example: `options = optimoptions("intlinprog",MaxTime=120)`

Structure encapsulating the inputs and options, specified with the following fields.

 `f` Vector representing objective `f'*x` (required) `intcon` Vector indicating variables that take integer values (required) `Aineq` Matrix in linear inequality constraints `Aineq*x `≤` bineq` `bineq` Vector in linear inequality constraints `Aineq*x `≤` bineq` `Aeq` Matrix in linear equality constraints `Aeq*x = beq` `beq` Vector in linear equality constraints `Aeq*x = beq` `lb` Vector of lower bounds `ub` Vector of upper bounds `x0` Initial point `solver` `'intlinprog'` (required) `options` Options created using `optimoptions` (required)

You must specify at least these fields in the problem structure. Other fields are optional:

• `f`

• `intcon`

• `solver`

• `options`

Example: ```problem.f = [1,2,3]; problem.intcon = [2,3]; problem.options = optimoptions('intlinprog'); problem.Aineq = [-3,-2,-1]; problem.bineq = -20; problem.lb = [-6.1,-1.2,7.3]; problem.solver = 'intlinprog';```

Data Types: `struct`

## Output Arguments

collapse all

Solution, returned as a vector that minimizes `f'*x` subject to all bounds, integer constraints, and linear constraints.

When a problem is infeasible or unbounded, `x` is `[]`.

Objective value, returned as the scalar value `f'*x` at the solution `x`.

When a problem is infeasible or unbounded, `fval` is `[]`.

Algorithm stopping condition, returned as an integer identifying the reason the algorithm stopped. The following lists the values of `exitflag` and the corresponding reasons `intlinprog` stopped.

 `3` The solution is feasible with respect to the relative `ConstraintTolerance` tolerance, but is not feasible with respect to the absolute tolerance. `2` `intlinprog` stopped prematurely. Integer feasible point found. `1` `intlinprog` converged to the solution `x`. `0` `intlinprog` stopped prematurely. No integer feasible point found. `-1` `intlinprog` stopped by an output function or plot function. `-2` No feasible point found. `-3` Root LP problem is unbounded. `-9` Solver lost feasibility.

The exit message can give more detailed information on the reason `intlinprog` stopped, such as exceeding a tolerance.

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.

Solution process summary, returned as a structure containing information about the optimization process.

 `relativegap` Relative percentage difference between upper (`U`) and lower (`L`) bounds of the objective function that `intlinprog` calculates in its branch-and-bound algorithm for the `"legacy"` algorithm, and relative difference for the `"highs"` algorithm. Specifically,For the `"legacy"` algorithm, ```relativegap = 100*(U - L) / (abs(U) + 1)```For the `"highs"` algorithm, ```relativegap = (U - L) / abs(U)```If ```intcon = []```, ```relativegap = []```.NoteAlthough you specify `RelativeGapTolerance` as a decimal number, the iterative display reports the gap as a percentage, meaning 100 times the measured relative gap. If the exit message refers to the relative gap, this value is the measured relative gap, not a percentage. `absolutegap` Difference between upper and lower bounds of the objective function that `intlinprog` calculates in its branch-and-bound algorithm.If ```intcon = []```, `absolutegap = []`. `numfeaspoints` Number of integer feasible points found.If `intcon = []`, `numfeaspoints = []`. Also, if the initial relaxed problem is infeasible, ```numfeaspoints = []```. `numnodes` Number of nodes in the branch-and-bound algorithm for the `"legacy"` algorithm; `numnodes = []` for the `"highs"` algorithm. If the solution was found during preprocessing or during the initial cuts, ```numnodes = 0```.If ```intcon = []```, ```numnodes = []```. `constrviolation` Constraint violation that is positive for violated constraints.```constrviolation = max([0; norm(Aeq*x-beq, inf); (lb-x); (x-ub); (Ai*x-bi)])``` `algorithm` Algorithm used, either `'highs'` or `'legacy'`. `message` Exit message.

## Limitations

• Often, some supposedly integer-valued components of the solution `x(intCon)` are not precisely integers. `intlinprog` deems as integers all solution values within `ConstraintTolerance` of an integer (`IntegerTolerance` for the `"legacy"` algorithm).

To round all supposed integers to be exactly integers, use the `round` function.

`x(intcon) = round(x(intcon));`

Caution

Rounding solutions can cause the solution to become infeasible. Check feasibility after rounding:

```max(A*x - b) % See if entries are not too positive, so have small infeasibility max(abs(Aeq*x - beq)) % See if entries are near enough to zero max(x - ub) % Positive entries are violated bounds max(lb - x) % Positive entries are violated bounds```
• `intlinprog` does not enforce that solution components be integer-valued when their absolute values exceed `2.1e9`. When your solution has such components, `intlinprog` warns you. If you receive this warning, check the solution to see whether supposedly integer-valued components of the solution are close to integers.

• `intlinprog` does not allow components of the problem, such as coefficients in `f`, `b`, or `ub`, to exceed `1e20` in absolute value (`1e25` for the `"legacy"` algorithm), and does not allow the linear constraint matrices `A` and `Aeq` to exceed or equal `1e15` in absolute value. If you try to run `intlinprog` with such a problem, `intlinprog` issues an error.

collapse all

### Enhanced Exit Messages

The next few items list the possible enhanced exit messages from `intlinprog`. Enhanced exit messages give a link for more information as the first sentence of the message.

### Solver stopped prematurely. Integer feasible point found.

`intlinprog` did not necessarily find an optimal solution. However, it did find at least one integer feasible point. An integer feasible point is a point that satisfies all constraints, including bounds, linear constraints, and integer constraints.

### Reached the maximum number of nodes

`intlinprog` uses a branch-and-bound algorithm, whose details are in Branch and Bound. Each branch in the algorithm creates a new node. `intlinprog` uses the `MaxNodes` option (a tolerance) as a stopping criterion.

You can change the value of an option using dot notation:

`options.MaxNodes = 5e4;`

You can also change the value using `optimoptions`:

`options = optimoptions(options,'MaxNodes',5e4);`

### Exceeded the time limit

`intlinprog` uses the `MaxTime` option (a tolerance) as a stopping criterion.

You can change the value of an option using dot notation:

`options.MaxTime = 5e4;`

You can also change the value using `optimoptions`:

`options = optimoptions(options,'MaxTime',5e4);`

### Exceeded the iteration limit at a node

`intlinprog` exceeded the iteration limit. `intlinprog` uses the `LPMaxIterations` option (a tolerance) as a stopping criterion.

You can change the value of an option using dot notation:

`options.LPMaxIterations = 5e4;`

You can also change the value using `optimoptions`:

`options = optimoptions(options,'LPMaxIterations',5e4);`

### Reached the maximum number of feasible points

`intlinprog` found at least `MaxNumFeasPoints` integer feasible points. `intlinprog` did not necessarily find an optimal solution.

An integer feasible point is a point that satisfies all constraints, including bounds, linear constraints, and integer constraints.

`intlinprog` uses the `MaxNumFeasPoints` option (a tolerance) as a stopping criterion.

You can change the value of an option using dot notation:

`options.MaxNumFeasPoints = 5e4;`

You can also change the value using `optimoptions`:

`options = optimoptions(options,'MaxNumFeasPoints',5e4);`

### Objective value is within a gap tolerance

`intlinprog` internally calculates both upper and lower bounds on the value of the objective function at the solution. The gap between these internally-calculated bounds is the difference between the upper and lower bounds. The relative gap is the ratio of the gap to one plus the absolute value of the lower bound. `intlinprog` uses the `TolGapAbs` option (a tolerance on the gap) and the `TolGapRel` option (a tolerance on the relative gap) as stopping criteria.

### No integer variables specified.

The `intcon` argument was empty, so `intlinprog` solved a linear programming problem.

### Solver stopped prematurely. No integer feasible point found.

`intlinprog` did not find any integer feasible points, and could not proceed. This does not necessarily mean that the problem is infeasible, only that `intlinprog` failed to find an integer feasible point. An integer feasible point is a point that satisfies all constraints, including bounds, linear constraints, and integer constraints.

### Exceeded the iteration limit while solving the root LP problem

`intlinprog` was unable to solve the relaxed LP because it reached the `RootLPMaxIterations` iteration limit. `intlinprog` uses the `RootLPMaxIterations` option (a tolerance) as a stopping criterion.

### Exceeded its allocated memory

`intlinprog` ran out of memory. It is possible that reformulating the problem could lead to a solution; see Williams [1].

### No Feasible Solution Found

`intlinprog` stopped because there is no solution to the problem. Either the bounds and linear constraints are inconsistent, or the integer constraints are inconsistent with the bounds and linear constraints.

To determine the cause, rerun the problem with `intcon = []`. If the resulting linear program has no solution, then the bounds and linear constraints are inconsistent. Otherwise, the integer constraints in the original problem are inconsistent with the bounds and linear constraints.

### Root LP problem is unbounded

The root linear programming (LP) problem is the original MILP problem but with no integer constraints. `intlinprog` stopped because the root LP problem is unbounded.

The original problem might be infeasible. `intlinprog` does not check feasibility when the root LP problem is unbounded.

### Problem is Unbounded

`intlinprog` stopped because there is no solution to the linear programming problem. For any target value there are feasible points with objective value smaller than the target.

### Definitions for Exit Messages

The next few items contain definitions for terms in the `intlinprog` exit messages.

### tolerance

Generally, a tolerance is a threshold which, if crossed, stops the iterations of a solver. For more information on tolerances, see Tolerances and Stopping Criteria.

### Node

A node in a branch-and-bound or branch-and-cut tree is a value of `x`, and a component `j` of `x` where `x(j)` has a fractional part. The branch-and-bound node has two subproblems: evaluate the linear programming problem with the restriction `x(j)` ≥ `ceil(x(j))`, and evaluate the linear programming problem with the restriction `x(j)` ≤ `floor(x(j))`. For more information, see Branch-and-Bound.

### Integer Within Tolerance

`intlinprog` does not guarantee that the variables you specify in `intcon` are exactly integers, only that they are within the `TolInteger` tolerance of an integer value. See Some “Integer” Solutions Are Not Integers.

### Root Node

When `intlinprog` stops at the root node, it did not have to execute any branch-and-bound search. Either `intlinprog` solved the problem during presolve, or it solved the problem during subsequent processing, but without needing to branch.

The root node is the relaxed linear programming problem based on the original MILP. For details, see Branch-and-Bound.

## Tips

• To specify binary variables, set the variables to be integers in `intcon`, and give them lower bounds of `0` and upper bounds of `1`.

• Save memory by specifying sparse linear constraint matrices `A` and `Aeq`. However, you cannot use sparse matrices for `b` and `beq`.

• To provide logical indices for integer components, meaning a binary vector with `1` indicating an integer, convert to `intcon` form using `find`. For example,

```logicalindices = [1,0,0,1,1,0,0]; intcon = find(logicalindices)```
```intcon = 1 4 5```
• This tip applies to the `"legacy"` algorithm.

If you include an `x0` argument, `intlinprog` uses that value in the `'rins'` and guided diving heuristics until it finds a better integer-feasible point. So when you provide `x0`, you can obtain good results by setting the `'Heuristics'` option to `'rins-diving'` or another setting that uses `'rins'`.

• `intlinprog` replaces `bintprog`. To update old `bintprog` code to use `intlinprog`, make the following changes:

• Set `intcon` to `1:numVars`, where `numVars` is the number of variables in your problem.

• Set `lb` to `zeros(numVars,1)`.

• Set `ub` to `ones(numVars,1)`.

• Update any relevant options. Use `optimoptions` to create options for `intlinprog`.

• Change your call to `bintprog` as follows:

```[x,fval,exitflag,output] = bintprog(f,A,b,Aeq,Beq,x0,options) % Change your call to: [x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,x0,options)```

## Alternative Functionality

### App

The Optimize Live Editor task provides a visual interface for `intlinprog`.

## Version History

Introduced in R2014a

expand all