Note: This page has been translated by MathWorks. Click here to see

To view all translated materials including this page, select Country from the country navigator on the bottom of this page.

To view all translated materials including this page, select Country from the country navigator on the bottom of this page.

A mixed-integer linear program is a problem with

Linear objective function,

*f*^{T}*x*, where*f*is a column vector of constants, and*x*is the column vector of unknownsBounds and linear constraints, but no nonlinear constraints (for definitions, see Write Constraints)

Restrictions on some components of

*x*to have integer values

In mathematical terms, given vectors *f*, *lb*,
and *ub*, matrices *A* and *Aeq*,
corresponding vectors *b* and *beq*, and a set of
indices `intcon`

, find a vector *x* to
solve

$$\underset{x}{\mathrm{min}}{f}^{T}x\text{subjectto}\{\begin{array}{l}x(\text{intcon})\text{areintegers}\hfill \\ A\cdot x\le b\hfill \\ Aeq\cdot x=beq\hfill \\ lb\le x\le ub.\hfill \end{array}$$

`intlinprog`

uses this basic strategy to solve
mixed-integer linear programs. `intlinprog`

can solve the
problem in any of the stages. If it solves the problem in a stage,
`intlinprog`

does not execute the later stages.

Reduce the problem size using Linear Program Preprocessing.

Solve an initial relaxed (noninteger) problem using Linear Programming.

Perform Mixed-Integer Program Preprocessing to tighten the LP relaxation of the mixed-integer problem.

Try Cut Generation to further tighten the LP relaxation of the mixed-integer problem.

Try to find integer-feasible solutions using heuristics.

Use a Branch and Bound algorithm to search systematically for the optimal solution. This algorithm solves LP relaxations with restricted ranges of possible values of the integer variables. It attempts to generate a sequence of updated bounds on the optimal objective function value.

According to the Mixed-Integer Linear Programming Definition,
there are matrices *A* and *Aeq* and
corresponding vectors *b* and *beq* that
encode a set of linear inequalities and linear equalities

$$\begin{array}{c}A\text{\hspace{0.05em}}\xb7\text{\hspace{0.05em}}x\le b\\ Aeq\text{\hspace{0.05em}}\xb7\text{\hspace{0.05em}}x=beq.\end{array}$$

These linear constraints restrict the solution *x*.

Usually, it is possible to reduce the number of variables in the problem (the
number of components of *x*), and reduce the number of linear
constraints. While performing these reductions can take time for the solver,
they usually lower the overall time to solution, and can make larger problems
solvable. The algorithms can make solution more numerically stable. Furthermore,
these algorithms can sometimes detect an infeasible problem.

Preprocessing steps aim to eliminate redundant variables and constraints, improve the scaling of the model and sparsity of the constraint matrix, strengthen the bounds on variables, and detect the primal and dual infeasibility of the model.

For details, see Andersen and Andersen [2] and Mészáros and Suhl [7].

The initial *relaxed* problem is the linear programming
problem with the same objective and constraints as Mixed-Integer Linear Programming Definition, but no integer
constraints. Call *x*_{LP} the solution to
the relaxed problem, and *x* the solution to the original
problem with integer constraints. Clearly,

*f*^{T}*x*_{LP}
≤
*f*^{T}*x*,

because *x*_{LP} minimizes the same
function but with fewer restrictions.

This initial relaxed LP (root node LP) and all generated LP relaxations during the branch-and-bound algorithm are solved using linear programming solution techniques.

During mixed-integer program preprocessing, `intlinprog`

analyzes the linear inequalities `A*x ≤ b`

along with
integrality restrictions to determine whether:

The problem is infeasible.

Some bounds can be tightened.

Some inequalities are redundant, so can be ignored or removed.

Some inequalities can be strengthened.

Some integer variables can be fixed.

The `IntegerPreprocess`

option lets you choose whether
`intlinprog`

takes several steps, takes all of them, or
takes almost none of them. If you include an `x0`

argument,
`intlinprog`

uses that value in preprocessing.

The main goal of mixed-integer program preprocessing is to simplify ensuing branch-and-bound calculations. Preprocessing involves quickly preexamining and eliminating some of the futile subproblem candidates that branch-and-bound would otherwise analyze.

For details about integer preprocessing, see Savelsbergh [9].

Cuts are additional linear inequality constraints that
`intlinprog`

adds to the problem. These inequalities
attempt to restrict the feasible region of the LP relaxations so that their
solutions are closer to integers. You control the type of cuts that
`intlinprog`

uses with the
`CutGeneration`

option.

`'basic'`

cuts include:

Mixed-integer rounding cuts

Gomory cuts

Clique cuts

Cover cuts

Flow cover cuts

Furthermore, if the problem is purely integer (all variables are
integer-valued), then `intlinprog`

also uses the following
cuts:

Strong Chvatal-Gomory cuts

Zero-half cuts

`'intermediate'`

cuts include all `'basic'`

cuts, plus:

Simple lift-and-project cuts

Simple pivot-and-reduce cuts

Reduce-and-split cuts

`'advanced'`

cuts include all
`'intermediate'`

cuts except reduce-and-split cuts,
plus:

Strong Chvatal-Gomory cuts

Zero-half cuts

For purely integer problems, `'intermediate'`

uses the most
cut types, because it uses reduce-and-split cuts, while
`'advanced'`

does not.

Another option, `CutMaxIterations`

, specifies an upper bound
on the number of times `intlinprog`

iterates to generate
cuts.

For details about cut generation algorithms (also called cutting plane methods), see Cornuéjols [5] and, for clique cuts, Atamtürk, Nemhauser, and Savelsbergh [3].

To get an upper bound on the objective function, the branch-and-bound
procedure must find feasible points. A solution to an LP relaxation during
branch-and-bound can be integer feasible, which can provide an improved upper
bound to the original MILP. There are techniques for finding feasible points
faster before or during branch-and-bound. Currently,
`intlinprog`

uses these techniques only at the root node,
not during the branch-and-bound iterations. These techniques are heuristic,
meaning they are algorithms that can succeed but can also fail.

Set the `intlinprog`

heuristics in the
`'Heuristics'`

option. The options are:

`'basic'`

(default) — Runs`'round'`

, then`'rss'`

. The solver does not run later heuristics when earlier heuristics lead to a sufficiently good integer-feasible solution.`'intermediate'`

— First runs`'round'`

, then`'rins'`

, then`'rss'`

. The solver does not run later heuristics when earlier heuristics lead to a sufficiently good integer-feasible solution.`'advanced'`

— First runs`'round'`

, then`'diving'`

, then`'rins'`

, then`'rss'`

. The solver does not run later heuristics when earlier heuristics lead to a sufficiently good integer-feasible solution. The solver uses only the fractional diving and guided diving heuristics for`'diving'`

.`'rins'`

—`intlinprog`

searches the neighborhood of the current best integer-feasible solution point (if available) to find a new and better solution. See Danna, Rothberg, and Le Pape [6].`'rss'`

—`intlinprog`

applies a hybrid procedure combining ideas from`'rins'`

and local branching to search for integer-feasible solutions.`'round'`

—`intlinprog`

takes the LP solution to the relaxed problem at a node. It rounds the integer components in a way that attempts to maintain feasibility.`'diving'`

—`intlinprog`

uses heuristics that are similar to branch-and-bound steps, but follow just one branch of the tree down, without creating the other branches. This single branch leads to a fast “dive” down the tree fragment, hence the name “diving.” Currently,`intlinprog`

uses six diving heuristics in this order, until it obtains an integer-feasible point with a relative gap of less than 5% or takes too much time:Vector length diving

Coefficient diving

Fractional diving

Pseudo cost diving

Line search diving

Guided diving (applies when

`intlinprog`

already found at least one integer-feasible point)

Diving heuristics generally select one variable that is supposed to be integer-valued, for which the current solution is fractional. They then introduce a bound that forces that variable to be integer-valued, and solve the associated relaxed LP again. The method of choosing the variable to bound is the main difference between the diving heuristics. See Berthold [4], Section 3.1.

`'rss-diving'`

or`'rins-diving'`

—`intlinprog`

tries`'diving'`

first, then (if necessary) the named heuristic method (`'rins'`

or`'rss'`

).`'round-diving'`

—`intlinprog`

tries`'round'`

first, then (if necessary) tries`'diving'`

.`'none'`

—`intlinprog`

does not search for a feasible point. It simply takes any feasible point it encounters in its branch-and-bound search.

The `'intermediate'`

and `'advanced'`

settings run the various heuristics in an order that is likely to save time.
Both `'round'`

and `'diving'`

are relatively
fast procedures, and the solver stops trying heuristics if one of these
succeeds.

Each heuristic can have its own stopping criteria. For example, the
`HeuristicsMaxNodes`

criterion applies only to the
`'rss'`

and `'rins'`

heuristics.

After each heuristic completes with a feasible solution,
`intlinprog`

calls output functions and plot functions.
See intlinprog Output Functions and Plot Functions.

If you include an `x0`

argument, `intlinprog`

uses that value in heuristics. In particular, improvement heuristics such as `rins`

and guided diving can start from `x0`

and attempt to improve the point. So setting the `'Heuristics'`

option to `'rins-diving'`

when you provide `x0`

can be effective. However, when the gap is small, heuristics do not run, so choosing `'rins-diving'`

does not always improve running time.

The branch-and-bound method constructs a sequence of subproblems that attempt
to converge to a solution of the MILP. The subproblems give a sequence of upper
and lower bounds on the solution *f*^{T}*x*. The first upper bound is any feasible solution, and the first
lower bound is the solution to the relaxed problem. For a discussion of the
upper bound, see Heuristics for Finding Feasible Solutions.

As explained in Linear Programming, any solution to the
linear programming relaxed problem has a lower objective function value than the
solution to the MILP. Also, any feasible point
*x*_{feas} satisfies

*f*^{T}*x*_{feas}
≥
*f*^{T}*x*,

because *f*^{T}*x* is the minimum among all feasible points.

In this context, a *node* is an LP with the same
objective function, bounds, and linear constraints as the original problem, but
without integer constraints, and with particular changes to the linear
constraints or bounds. The *root node* is the original
problem with no integer constraints and no changes to the linear constraints or
bounds, meaning the root node is the initial relaxed LP.

From the starting bounds, the branch-and-bound method constructs new
subproblems by branching from the root node. The branching step is taken
heuristically, according to one of several rules. Each rule is based on the idea
of splitting a problem by restricting one variable to be less than or equal to
an integer J, or greater than or equal to J+1. These two subproblems arise when
an entry in *x*_{LP}, corresponding to an
integer specified in intcon, is not an integer. Here,
*x*_{LP} is the solution to a relaxed
problem. Take J as the floor of the variable (rounded down), and J+1 as the
ceiling (rounded up). The resulting two problems have solutions that are larger
than or equal to
*f*^{T}*x*_{LP},
because they have more restrictions. Therefore, this procedure potentially
raises the lower bound.

The performance of the branch-and-bound method depends on the rule for
choosing which variable to split (the branching rule). The algorithm uses these
rules, which you can set in the `BranchRule`

option:

`'maxpscost'`

— Choose the fractional variable with maximal*pseudocost*.`'strongpscost'`

— Similar to`'maxpscost'`

, but instead of the pseudocost being initialized to`1`

for each variable, the solver attempts to branch on a variable only after the pseudocost has a more reliable estimate. To obtain a more reliable estimate, the solver does the following (see Achterberg, Koch, and Martin [1]).Order all potential branching variables (those that are currently fractional but should be integer) by their current pseudocost-based scores.

Run the two relaxed linear programs based on the current branching variable, starting from the variable with the highest score (if the variable has not yet been used for a branching calculation). The solver uses these two solutions to update the pseudocosts for the current branching variable. The solver can halt this process early to save time in choosing the branch.

Continue choosing variables in the list until the current highest pseudocost-based score does not change for

`k`

consecutive variables, where`k`

is an internally chosen value, usually between 5 and 10.Branch on the variable with the highest pseudocost-based score. The solver might have already computed the relaxed linear programs based on this variable during an earlier pseudocost estimation procedure.

Because of the extra linear program solutions, each iteration of

`'strongpscost'`

branching takes longer than the default`'maxpscost'`

. However, the number of branch-and-bound iterations typically decreases, so the`'strongpscost'`

method can save time overall.`'reliability'`

— Similar to`'strongpscost'`

, but instead of running the relaxed linear programs only for uninitialized pseudocost branches,`'reliability'`

runs the programs up to`k2`

times for each variable, where`k2`

is a small integer such as 4 or 8. Therefore,`'reliability'`

has even slower branching, but potentially fewer branch-and-bound iterations, compared to`'strongpscost'`

.`'mostfractional'`

— Choose the variable with fractional part closest to`1/2`

.`'maxfun'`

— Choose the variable with maximal corresponding absolute value in the objective vector`f`

.

After the algorithm branches, there are two new nodes to explore. The algorithm chooses which node to explore among all that are available using one of these rules:

`'minobj'`

— Choose the node that has the lowest objective function value.`'mininfeas'`

— Choose the node with the minimal sum of integer infeasibilities. This means for every integer-infeasible component*x*(*i*) in the node, add up the smaller of*p*and_{i}^{–}*p*, where_{i}^{+}*p*=_{i}^{–}*x*(*i*) – ⌊*x*(*i*)⌋

*p*= 1 –_{i}^{+}*p*._{i}^{–}`'simplebestproj'`

— Choose the node with the*best projection*.

`intlinprog`

skips the analysis of some subproblems by
considering information from the original problem such as the objective
function’s greatest common divisor (GCD).

The branch-and-bound procedure continues, systematically generating subproblems to analyze and discarding the ones that won’t improve an upper or lower bound on the objective, until one of these stopping criteria is met:

The algorithm exceeds the

`MaxTime`

option.The difference between the lower and upper bounds on the objective function is less than the

`AbsoluteGapTolerance`

or`RelativeGapTolerance`

tolerances.The number of explored nodes exceeds the

`MaxNodes`

option.The number of integer feasible points exceeds the

`MaxFeasiblePoints`

option.

For details about the branch-and-bound procedure, see Nemhauser and Wolsey [8] and Wolsey [10].

[1] Achterberg, T., T. Koch
and A. Martin. *Branching rules revisited.* Operations Research
Letters 33, 2005, pp. 42–54. Available at `https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.pdf`

.

[2] Andersen, E. D., and Andersen, K. D. *Presolving
in linear programming.* Mathematical Programming 71, pp. 221–245,
1995.

[3] Atamtürk, A., G. L.
Nemhauser, M. W. P. Savelsbergh. *Conflict graphs in solving integer
programming problems.* European Journal of Operational Research 121,
2000, pp. 40–55.

[4] Berthold, T. *Primal Heuristics for Mixed
Integer Programs.* Technischen Universität Berlin, September 2006.
Available at `https://www.zib.de/groetschel/students/Diplom-Berthold.pdf`

.

[5] Cornuéjols, G. *Valid inequalities for
mixed integer linear programs.* Mathematical Programming B, Vol. 112,
pp. 3–44, 2008.

[6] Danna, E., Rothberg, E., Le Pape, C. *Exploring
relaxation induced neighborhoods to improve MIP solutions.*
Mathematical Programming, Vol. 102, issue 1, pp. 71–90, 2005.

[7] Mészáros C., and Suhl, U. H. *Advanced
preprocessing techniques for linear and quadratic programming.* OR
Spectrum, 25(4), pp. 575–595, 2003.

[8] Nemhauser, G. L. and Wolsey, L. A. *Integer and
Combinatorial Optimization.* Wiley-Interscience, New York,
1999.

[9] Savelsbergh, M. W. P. *Preprocessing and Probing
Techniques for Mixed Integer Programming Problems.* ORSA J.
Computing, Vol. 6, No. 4, pp. 445–454, 1994.

[10] Wolsey, L. A. *Integer Programming.*
Wiley-Interscience, New York, 1998.