x = intlinprog(f,intcon,A,b) solves
min f'*x such that the components of x in intcon are
integers, and 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,options) minimizes
using the optimization options specified in options.
Use optimoptions to set these
options. Set lb = [] and ub = [] if no bounds exist.

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

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)

LP: Optimal objective value is 59.000000.
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value;
options.TolGapAbs = 0 (the default value). The intcon variables are integer within tolerance,
options.TolInteger = 1e-05 (the default value).
x =
6.5000
7.0000

LP: Optimal objective value is -12.000000.
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value;
options.TolGapAbs = 0 (the default value). The intcon variables are integer within tolerance,
options.TolInteger = 1e-05 (the default value).
x =
0
5.5000
1.0000

LP: Optimal objective value is -12.000000.
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value;
options.TolGapAbs = 0 (the default value). The intcon variables are integer within tolerance,
options.TolInteger = 1e-05 (the default value).
x =
0
5.5000
1.0000
fval =
-12.0000
exitflag =
1
output =
relativegap: 0
absolutegap: 0
numfeaspoints: 1
numnodes: 0
constrviolation: 1.7764e-15
message: 'Optimal solution found.
Intlinprog stopped at the root node because the objective v...'

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.

Coefficient vector, specified as a vector of doubles representing
the objective function, f'*x. The notation assumes
that f is a column vector, but you are free to
use a row vector.

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

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

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.

Linear inequality constraint matrix, specified as a matrix of
doubles. A represents the linear coefficients in
the constraints A*x ≤ b. A has size M-by-N,
where M is the number of constraints and N = numel(f).
To save memory, A can be sparse.

Example: A = [4,3;2,0;4,-1]; means three linear
inequalities (three rows) for two decision variables (two columns).

Linear inequality constraint vector, specified as a vector of
doubles. b represents the constant vector in the
constraints A*x ≤ b. b has length M,
where A is M-by-N.

Linear equality constraint matrix, specified as a matrix of
doubles. Aeq represents the linear coefficients
in the constraints Aeq*x = beq. Aeq has size Meq-by-N,
where Meq is the number of constraints and N = numel(f).
To save memory, Aeq can be sparse.

Example: A = [4,3;2,0;4,-1]; means three linear
inequalities (three rows) for two decision variables (two columns).

Linear equality constraint vector, specified as a vector of
doubles. beq represents the constant vector in
the constraints Aeq*x = beq. beq has length Meq,
where Aeq is Meq-by-N.

'none' — No cuts. Makes CutGenerationMaxIter irrelevant.

'basic' — Normal cut generation.

'intermediate' — Use more
cut types.

'advanced' — Use most cut
types.

'basic'

CutGenMaxIter

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

Strictly positive integer that bounds the number of nodes intlinprog can
explore in its branch-and-bound search for feasible points. See Heuristics for Finding Feasible Solutions.

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

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

RelObjThreshold

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

1e-4

RootLPAlgorithm

Algorithm for solving linear programs:

'dual-simplex' — Dual simplex
algorithm

'primal-simplex' — Primal
simplex algorithm

'dual-simplex'

RootLPMaxIter

Nonnegative integer that is the maximum number of simplex algorithm
iterations to solve the initial linear programming problem.

3e4

TolCon

Real from 1e-9 through 1e-3 that
is the maximum discrepancy that linear constraints can have and still
be considered satisfied. TolCon is not a stopping
criterion.

1e-4

TolFunLP

Nonnegative real where reduced costs must exceed TolFunLP for
a variable to be taken into the basis.

1e-7

TolGapAbs

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 TolGapAbs:

U
– L <= TolGapAbs.

0

TolGapRel

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 TolGapRel:

(U
– L) / (abs(U) + 1) <= TolGapRel.

1e-4

TolInteger

Real from 1e-6 through 1e-3,
where the maximum deviation from integer that a component of the solution x can
have and still be considered an integer. TolInteger is
not a stopping criterion.

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.

2

intlinprog stopped
prematurely. Integer feasible point found.

1

intlinprog converged
to the solution x.

0

intlinprog stopped
prematurely. No integer feasible point found.

-2

No feasible point found.

-3

Root LP problem is unbounded.

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

Often, some supposedly integer-valued components of
the solution x(intCon) are not precisely integers. intlinprog deems
as integers all solution values within the TolInteger tolerance
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, A,
or ub, to exceed 1e25 in absolute
value. If you try to run intlinprog with such
a problem, intlinprog issues an error.

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,