intlinprog - Mixed-integer linear programming (MILP) - MATLAB (original) (raw)

Mixed-integer linear programming (MILP)

Syntax

Description

Mixed-integer linear programming solver.

Finds the minimum of a problem specified by

f, x, b, 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.

[x](#bts3f9f-x) = intlinprog([f](#bts3f9f-f),[intcon](#bts3f9f-intcon),[A](#bts3f9f%5Fsep%5Fbuusznx-A),[b](#bts3f9f%5Fsep%5Fshared-b),[Aeq](#bts3f9f%5Fsep%5Fbuusznx-Aeq),[beq](#bts3f9f%5Fsep%5Fshared-beq)) solves the problem above while additionally satisfying the equality constraints Aeq*x = beq. Set A = [] and b = [] if no inequalities exist.

[x](#bts3f9f-x) = intlinprog([f](#bts3f9f-f),[intcon](#bts3f9f-intcon),[A](#bts3f9f%5Fsep%5Fbuusznx-A),[b](#bts3f9f%5Fsep%5Fshared-b),[Aeq](#bts3f9f%5Fsep%5Fbuusznx-Aeq),[beq](#bts3f9f%5Fsep%5Fshared-beq),[lb](#bts3f9f-lb),[ub](#bts3f9f-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](#bts3f9f-x) = intlinprog([f](#bts3f9f-f),[intcon](#bts3f9f-intcon),[A](#bts3f9f%5Fsep%5Fbuusznx-A),[b](#bts3f9f%5Fsep%5Fshared-b),[Aeq](#bts3f9f%5Fsep%5Fbuusznx-Aeq),[beq](#bts3f9f%5Fsep%5Fshared-beq),[lb](#bts3f9f-lb),[ub](#bts3f9f-ub),[x0](#d126e120780))optimizes using an initial feasible point x0. Setlb = [] andub = [] if no bounds exist.

example

[x](#bts3f9f-x) = intlinprog([f](#bts3f9f-f),[intcon](#bts3f9f-intcon),[A](#bts3f9f%5Fsep%5Fbuusznx-A),[b](#bts3f9f%5Fsep%5Fshared-b),[Aeq](#bts3f9f%5Fsep%5Fbuusznx-Aeq),[beq](#bts3f9f%5Fsep%5Fshared-beq),[lb](#bts3f9f-lb),[ub](#bts3f9f-ub),[x0](#d126e120780),[options](#btv2x05)) minimizes using the optimization options specified inoptions. Use optimoptions to set these options. Set x0 = [] if no initial point exists.

example

[x](#bts3f9f-x) = intlinprog([problem](#bts3f9f-problem)) uses aproblem structure to encapsulate all solver inputs. You can import a problem structure from an MPS file usingmpsread. You can also create aproblem structure from anOptimizationProblem object by using prob2struct.

example

[[x](#bts3f9f-x),[fval](#bts3f9f-fval),[exitflag](#bts3f9f-exitflag),[output](#bts3f9f-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

minx(8x1+x2)subjectto{x2isanintegerx1+2x2≥-14-4x1-x2≤-332x1+x2≤20.

Write the objective function vector and vector of integer variables.

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.1: 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.01 (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.

Solve the problem

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12.

Write the objective function vector and vector of integer variables.

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

Write the linear inequality constraints.

Write the linear equality constraints.

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.1: 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.

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.

Specify that all variables are integer-valued.

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.1: 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 2.9s

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 2.92 (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.1: 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.5s T 9340 919 3970 80.72% 1692.410008 2687 37.01% 29 6 9995 16120 2.2s T 21750 192 9514 96.83% 1791.542628 1854 3.37% 20 6 9984 40278 5.3s

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.39 (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.

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

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12

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)

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

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12

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',-3x(1)-2x(2)-xb); cons1 = sum(x) + xb <= 7; cons2 = 4x(1) + 2x(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.1: 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.

output = struct with fields: relativegap: 0 absolutegap: 0 numfeaspoints: 1 numnodes: 0 constrviolation: 0 algorithm: 'highs' 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?

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

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

The goal is to solve the problem

minx(-3x1-2x2-x3)subjectto{x3binaryx1,x2≥0x1+x2+x3≤74x1+2x2+x3=12.

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.1: 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.

output = struct with fields: relativegap: 0 absolutegap: 0 numfeaspoints: 1 numnodes: 0 constrviolation: 0 algorithm: 'highs' 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

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

Integer variable indices, specified as a vector of positive integers or an IntegerConstraint object created with theintegerConstraint function. The"legacy" algorithm does not support extended integer variables. 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 from1 through numel(f).

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

Note

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

Example: intcon = [1,2,7] meansx(1), x(2), andx(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) andx(3) are integers.

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:

_x_1 + 2_x_2 ≤ 10
3_x_1 + 4_x_2 ≤ 20
5_x_1 + 6_x_2 ≤ 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

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:

_x_1 + 2_x_2 + 3_x_3 = 10
2_x_1 + 4_x_2 +_x_3 = 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) andbeq = 1.

Data Types: double

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 inx0 is the same as the number of elements off, when f exists. Otherwise, the number is the same as the number of columns ofA or Aeq. Internally, the solver converts an array x0 into a vectorx0(:).

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

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

The "highs" algorithm attempts to use any suppliedx0, 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 theoptimoptions display. These options appear in italics in the following table. For details, see View Optimization Options.

All Algorithms
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 toAbsoluteGapTolerance: 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 from1e-10 through1e-3 representing the maximum allowable violation of integer or linear constraints.For the"legacy" algorithm, a real value from 1e-10 through1e-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 findsMaxFeasiblePoints 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 thexIntSol 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 toRelativeGapTolerance:For the "highs" algorithm, the stopping test is(U – L)/|U <= RelativeGapTolerance.WhenU = 0 and L = 0, the returned ratio (U – L)/
Legacy Algorithm
BranchRule Rule for choosing the component for branching:'maxpscost' — The fractional component with maximum pseudocost. SeeBranch 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'. SeeBranch and Bound.'mostfractional' — The component whose fractional part is closest to1/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 theCutGeneration 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 through1e-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, andnumberOfVariables means the number of elements of f.
LPOptimalityTolerance Nonnegative real where reduced costs must exceedLPOptimalityTolerance 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 leastObjectiveImprovementThreshold lower: (fold – fnew)/(1 + |fold ) >ObjectiveImprovementThreshold.
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, andnumberOfVariables 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, 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
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:

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 relativeConstraintTolerance 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.Ifintcon = [],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

More About

collapse all

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

The intlinprog solver with the default"highs" algorithm 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:

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

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

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.

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 theMaxNodes option (a tolerance) as a stopping criterion.

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

You can also change the value using optimoptions:

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

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

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

You can also change the value using optimoptions:

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

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

intlinprog found at leastMaxNumFeasPoints 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);

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 theTolGapAbs option (a tolerance on the gap) and theTolGapRel option (a tolerance on the relative gap) as stopping criteria.

The intcon argument was empty, sointlinprog solved a linear programming problem.

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.

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

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

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.

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.

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.

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

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.

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

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. SeeSome “Integer” Solutions Are Not Integers.

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

Alternative Functionality

App

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

Version History

Introduced in R2014a

expand all

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.

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 oflowerbound. 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 andBranch/bound LB.

The "highs" algorithm now supports theMaxFeasiblePoints option. Theoutput structure for the "highs" algorithm now supports the numfeaspoints field.

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 theAlgorithm option will be removed. Also at that time, thealgorithm field of the output structure will be removed.

intlinprog gains an algorithm, anAlgorithm 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" usingoptimoptions.

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.

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