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

$$\underset{x}{\min }{f}^{T}x\text{ subject to }\{\begin{array}{l}x(\text{intcon})\text{ are integers or extended integers}\hfill \\ \text{bl}\le A\cdot x\le b\hfill \\ \text{Aeq}\cdot x=\text{beq}\hfill \\ \text{lb}\le x\le \text{ub}.\hfill \end{array}$$

f, x, b, bl, beq, lb, and ub are vectors, intcon is a vector or an integerConstraint object, 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. Use solve for the problem-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 or Extended Integer Variables, and A*x ≤ b, or, if b is a 2-element cell array {bl,b}, bl ≤ A*x ≤ b.

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.

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.

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.

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.

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

Examples

Solve an MILP with Linear Inequalities

Solve the problem

$$\underset{x}{\min }\left(8x_1+x_2\right)subjectto\{\begin{array}{l}{x}_{2}isaninteger\\ x_1+2x_2\ge -14\\ -4x_1-x_2\le -33\\ 2x_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.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP  has 3 rows; 2 cols; 6 nonzeros; 1 integer variables (0 binary)
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, 0 domain fixed)
   6 nonzeros

Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
     H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
     I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
     z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
Src  Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

 J       0       0         0   0.00%   -inf            80                 Large        0      0      0         0     0.0s
 T       0       0         0   0.00%   -inf            59                 Large        0      0      0         3     0.0s
         1       0         1 100.00%   59              59                 0.00%        0      0      0         3     0.0s

Solving report
  Status            Optimal
  Primal bound      59
  Dual bound        59
  Gap               0% (tolerance: 0.01%)
  P-D integral      0
  Solution status   feasible
                    59 (objective)
                    0 (bound viol.)
                    1.7763568394e-15 (int. viol.)
                    0 (row viol.)
  Timing            0.01 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 0
  Nodes             1
  Repair LPs        0 (0 feasible; 0 iterations)
  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 an MILP with All Types of Constraints

Solve the problem

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_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.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP  has 2 rows; 3 cols; 6 nonzeros; 1 integer variables (1 binary)
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

Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
     H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
     I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
     z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
Src  Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -12             -12                0.00%        0      0      0         0     0.0s

Solving report
  Status            Optimal
  Primal bound      -12
  Dual bound        -12
  Gap               0% (tolerance: 0.01%)
  P-D integral      0
  Solution status   feasible
                    -12 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 0
  Nodes             0
  Repair LPs        0 (0 feasible; 0 iterations)
  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

Use Initial Point

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 and LP iterations in the solution process.

[x1,fval1,exitflag1,output1] = intlinprog(f,intcon,[],[],Aeq,beq,lb);

Running HiGHS 1.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP  has 4 rows; 8 cols; 32 nonzeros; 8 integer variables (0 binary)
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, 0 domain fixed)
   27 nonzeros

Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
     H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
     I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
     z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
Src  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   14284    1214      5620  78.42%   1690.169125     2849              40.68%       39      5   9987     17146     1.6s
 T   21917    1000      8515  86.43%   1736.378236     2113              17.82%       36      5   9873     24182     2.4s
 T   26514     250     10328  96.20%   1778.832142     1854               4.05%       31      5   4853     28216     2.7s
     26903       0     10609 100.00%   1854            1854               0.00%       39     11   3699     28606     2.7s

Solving report
  Status            Optimal
  Primal bound      1854
  Dual bound        1854
  Gap               0% (tolerance: 0.01%)
  P-D integral      0.352619102888
  Solution status   feasible
                    1854 (objective)
                    0 (bound viol.)
                    9.63673585375e-14 (int. viol.)
                    0 (row viol.)
  Timing            2.71 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 3
  Nodes             26903
  Repair LPs        0 (0 feasible; 0 iterations)
  LP iterations     28606 (total)
                    240 (strong br.)
                    77 (separation)
                    2156 (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 = [16 60 12 0 0 86 34 219];
[x2,fval2,exitflag2,output2] = intlinprog(f,intcon,[],[],Aeq,beq,lb,[],x0);

Running HiGHS 1.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP  has 4 rows; 8 cols; 32 nonzeros; 8 integer variables (0 binary)
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 2113
Objective function is integral with scale 1

Solving MIP model with:
   4 rows
   8 cols (0 binary, 8 integer, 0 implied int., 0 continuous, 0 domain fixed)
   27 nonzeros

Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
     H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
     I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
     z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
Src  Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   0               2113             100.00%        0      0      0         0     0.0s
         0       0         0   0.00%   1554.047531     2113              26.45%        0      0      4         4     0.0s
 T    3313     105      1293  95.83%   1687.4271       1854               8.98%       56      6   9402      6902     0.5s
      3996       0      1630 100.00%   1854            1854               0.00%       30      6   9989      8272     0.6s

Solving report
  Status            Optimal
  Primal bound      1854
  Dual bound        1854
  Gap               0% (tolerance: 0.01%)
  P-D integral      0.116495047223
  Solution status   feasible
                    1854 (objective)
                    0 (bound viol.)
                    1.13686837722e-13 (int. viol.)
                    0 (row viol.)
  Timing            0.60 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 3
  Nodes             3996
  Repair LPs        0 (0 feasible; 0 iterations)
  LP iterations     8272 (total)
                    240 (strong br.)
                    79 (separation)
                    565 (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 takes roughly 25,000 LP iterations and 25,000 branch-and-bound nodes.

• Using an initial point, intlinprog takes less than 1/3 of the LP iterations and an even smaller fraction of the nodes. The time to solution is also much faster.

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 an MILP with Nondefault Options

Solve the problem

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_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

Solve MILP Using Problem-Based Approach

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}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_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.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP  has 2 rows; 3 cols; 6 nonzeros; 1 integer variables (1 binary)
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

Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
     H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
     I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
     z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
Src  Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -12             -12                0.00%        0      0      0         0     0.0s

Solving report
  Status            Optimal
  Primal bound      -12
  Dual bound        -12
  Gap               0% (tolerance: 0.01%)
  P-D integral      0
  Solution status   feasible
                    -12 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 0
  Nodes             0
  Repair LPs        0 (0 feasible; 0 iterations)
  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: 1
           numnodes: 0
    constrviolation: 0
            message: '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.'

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: [2×1 optim.problemdef.OptimizationVariable]
    xb: [1×1 optim.problemdef.OptimizationVariable]

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

Examine the MILP Solution and Process

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

The goal is to solve the problem

$$\underset{x}{\min }\left(-3x_1-2x_2-x_3\right)subjectto\{\begin{array}{l}{x}_{3}binary\\ x_1,x_2\ge 0\\ x_1+x_2+x_3\le 7\\ 4x_1+2x_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.11.0: Copyright (c) 2025 HiGHS under MIT licence terms
MIP  has 2 rows; 3 cols; 6 nonzeros; 1 integer variables (1 binary)
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

Src: B => Branching; C => Central rounding; F => Feasibility pump; J => Feasibility jump;
     H => Heuristic; L => Sub-MIP; P => Empty MIP; R => Randomized rounding; Z => ZI Round;
     I => Shifting; S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution;
     z => Trivial zero; l => Trivial lower; u => Trivial upper; p => Trivial point

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work      
Src  Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -12             -12                0.00%        0      0      0         0     0.0s

Solving report
  Status            Optimal
  Primal bound      -12
  Dual bound        -12
  Gap               0% (tolerance: 0.01%)
  P-D integral      0
  Solution status   feasible
                    -12 (objective)
                    0 (bound viol.)
                    0 (int. viol.)
                    0 (row viol.)
  Timing            0.01 (total)
                    0.00 (presolve)
                    0.00 (solve)
                    0.00 (postsolve)
  Max sub-MIP depth 0
  Nodes             0
  Repair LPs        0 (0 feasible; 0 iterations)
  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: 1
           numnodes: 0
    constrviolation: 0
            message: '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.'

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

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

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

intcon — Integer variable indices

vector of integers | IntegerConstraint object

Integer variable indices, specified as a vector of positive integers or an IntegerConstraint object created with the integerConstraint function. The values in intcon indicate the components of the decision variable x that are integer-valued or extended-integer-valued (see Extended Integer Variables). Indices in intcon have values from 1 through numel(f).

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

Note

Semi-integer and semicontinuous variables must have strictly positive bounds that do not exceed 1e5.

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

Example: intcon = integerConstraint(SemiContinuous=[1,4],Integer=[2,3]) specifies that x(1) and x(4) are semicontinuous, and x(2) and x(3) are integers.

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 (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 vector with M elements.

When b is a two-element cell array {bl,b}, A encodes the linear inequalities

bl <= A*x <= b.

(1)

For example, consider these inequalities:

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

Specify the inequalities by entering the following constraints.

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

Similarly, if you have the additional constraint

4x1 – x2 ≥2,

(2)

then specify

bb = {[-inf;-inf;-inf;2] [b;inf]};
AA = [A;[4 -1]];

and pass AA and bb as the linear inequality constraints.

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

Data Types: single | double

b — Linear inequality constraints

real vector | two-element cell array of real arrays

Linear inequality constraints, specified as a real vector or a two-element cell array of real arrays.

• If b is an M-element vector, b encodes the M linear inequalities

  A*x <= b,

  (3)

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

• If b is a two-element cell array {bl,b}, either bl or b, or both, must be nonempty. The nonempty entries in b contain M elements that encode the linear inequalities

  bl <= A*x <= b,

  (4)

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

If you pass b or bl as a row vector, solvers internally convert it to the column vector b(:) or bl(:).

For example, consider these inequalities:

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

Specify the inequalities by entering the following constraints.

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

Consider this additional constraint

4x1 – x2 ≥2,

(5)

Specify the constraint as the linear inequality matrices AA and bb that extend A and b.

bb = {[-inf;-inf;-inf;2] [b;inf]};
AA = [A;[4 -1]];

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

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

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

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 it to the column vector beq(:).

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:

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

lb — Lower bounds

[] (default) | real vector or array

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

ub — Upper bounds

[] (default) | real vector or array

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

x0 — Initial point

[] (default) | real array

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

intlinprog attempts to use any supplied x0, modifying the point if necessary for feasibility.

Providing x0 can change the amount of time intlinprog takes to converge. It is difficult to predict how x0 affects the solver.

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

Data Types: double

options — Options for intlinprog

options created using optimoptions

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.

Option	Description	Default
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
ConstraintTolerance	A real value from 1e-10 through 1e-3 representing the maximum allowable violation of integer or linear constraints. ConstraintTolerance is not a stopping criterion.	1e-6
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: 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. 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

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

problem — Structure encapsulating inputs and options

structure

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, or integerConstraint object specifying extended integer constraints (required)
Aineq	Matrix in linear inequality constraints Aineq*x ≤ bineq
bineq	Vector in linear inequality constraints Aineq*x ≤ bineq or cell array {bl,b} for bl ≤Aineq*x ≤ b. If you use a cell array, ensure that the array is in a single 1-by-1 cell, such as bcons = {bl b}; problem.bineq = {bcons};
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

Caution

The problem argument must be a scalar structure. If you create linear constraints as a cell array {bl,b}, the resulting problem structure can be a nonscalar structure array. To ensure that problem is scalar, pass {{bl,b}}.

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

x — Solution

real vector

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

fval — Objective value

real scalar

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

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

exitflag — Algorithm stopping condition

integer

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.

output — Solution process summary

structure

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

relativegap	Relative difference between upper (U) and lower (L) bounds of the objective function that intlinprog calculates in its branch-and-bound algorithm . Specifically, relativegap = (U - L) / abs(U). If intcon = [], relativegap = []. 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.
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. 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)])
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.

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

More About

Extended Integer Variables

An extended integer variable is a variable that is integer-valued, semicontinuous, or semi-integer.

• An integer-valued variable can take any integer value represented in a standard double-precision variable, such as –12 or 1234567. You do not need to specify any bounds for an integer variable.

• A semicontinuous variable can take the value 0 or any real value from the lower bound to the upper bound. The bounds must be strictly positive and no more than 1e5.

• A semi-integer variable is integer-valued and can take the value 0 or any integer value from the lower bound to the upper bound. The bounds must be strictly positive and no more than 1e5.

The intlinprog solver supports integer variables and extended integer variables, all of which have the MATLAB^® type double. Specify the variable types using the integerConstraint function. Specify the variable indices that are integer or extended integer using these names:

• Integer — Integer variable indices

• SemiContinuous — Semicontinuous variable indices

• SemiInteger — Semi-integer variable indices

The default type for unspecified variable indices is continuous, meaning variables that can take any real value.

For example, to specify that variables 1 through 5 are integer, 11 through 20 are semicontinuous, and the remainder are continuous:

intcon = integerConstraint(Integer=1:5,SemiContinuous=11:20);

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 (see 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

• 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

R2026a: intlinprog "legacy" algorithm removed

The intlinprog "legacy" algorithm has been removed. All options specific to the "legacy" algorithm have also been removed:

• BranchRule

• CutGeneration

• CutMaxIterations

• Heuristics

• HeuristicsMaxNodes

• IntegerPreprocess

• IntegerTolerance

• LPMaxIterations

• LPOptimalityTolerance

• LPPreprocess

• NodeSelection

• ObjectiveImprovementThreshold

• RootLPAlgorithm

• RootLPMaxIterations

Also, because there is only one intlinprog algorithm, the Algorithm option has been removed. Similarly, the intlinprog output structure no longer includes an algorithm field.

The optimValues structure, used in output functions or plot functions (see intlinprog Output Function and Plot Function Syntax), no longer includes a phase field because that field was used only by the "legacy" algorithm.

R2026a: Solve using linear range constraints

The intlinprog solver supports linear range constraints, meaning upper and lower linear constraints:

$$\text{bl}\le Ax\le b.$$

Specify the linear constraint vector as a cell array {bl b}. For an example, see Linear Range Constraints.

R2025a: Extended integer variable support

intlinprog with the "highs" algorithm supports semicontinuous and semi-integer variables, which you specify by using the integerConstraint function. For example, to specify that variables 10 through 20 are semi-integer, and variables 1 through 9 are semicontinuous, enter:

intcon = integerConstraint(SemiInteger=10:20,SemiContinuous=1:9);

For more information, see Extended Integer Variables.

R2024b: "highs" algorithm supports output functions, plot functions, and the MaxFeasiblePoints option

The "highs" algorithm now supports output functions and plot functions. For details, see intlinprog Output Function and Plot Function Syntax. For an example using a built-in plot function, see Factory, Warehouse, Sales Allocation Model: Solver-Based.

The optimValues Structure for output functions and plot functions now uses the field name dualbound instead of lowerbound. The meaning of dualbound is the global lower bound for minimization problems, or the global upper bound for maximization problems. The optimplotmilp plot function now uses the labels Primal Bound and Dual Bound instead of Branch/bound UB and Branch/bound LB.

The "highs" algorithm now supports the MaxFeasiblePoints option. The output structure for the "highs" algorithm now supports the numfeaspoints field.

R2024b: "legacy" algorithm will be removed

The intlinprog "legacy" algorithm will be removed in a future release. At that time, all options that are valid only for the "legacy" algorithm will be removed, and the Algorithm option will be removed. Also at that time, the algorithm field of the output structure will be removed.

R2024a: New "highs" algorithm is the default

intlinprog gains an algorithm, an Algorithm option, and a new default algorithm. The "highs" algorithm is based on the open-source HiGHS code. Currently, the "highs" algorithm does not support output functions or plot functions.

To use the previous algorithm, set Algorithm="legacy" using optimoptions.

The allowable range of the ConstraintTolerance option values is now 1e-10 to 1e-3 for both algorithms, as is the allowable range of the IntegerTolerance option values for the "legacy" algorithm.

R2019a: Default BranchRule is 'reliability'

The default value of the BranchRule option is 'reliability' instead of 'maxpscost'. In testing, this value gave better performance on many problems, both in solution times and in number of explored branching nodes.

On a few problems, the previous branch rule performs better. To get the previous behavior, set the BranchRule option to 'maxpscost'.