A mixed-integer linear program is a problem with
Linear objective function, fTx, where f is a column vector of constants, and x is the column vector of unknowns
Bounds and linear constraints, but no nonlinear constraints (for definitions, see Writing 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
intlinprog uses this basic strategy to
solve mixed-integer linear programs.
solve the problem in any of the stages. If it solves the problem in
intlinprog does not execute the later
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
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.
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 xLP the solution to the relaxed problem, and x the solution to the original problem with integer constraints. Clearly,
fTxLP ≤ fTx,
because xLP 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,
the linear inequalities
A*x ≤ b along with integrality restrictions to determine
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.
IPPreprocess option lets you choose whether
several steps, takes all of them, or takes almost none of them.
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 .
Cuts are additional linear inequality constraints that
to the problem. These inequalities attempt to restrict the feasible
region of the LP relaxations so that their solution are closer to
integers. You control the type of cuts that
'basic' cuts include:
Mixed-integer rounding cuts
Flow cover cuts
'intermediate' cuts include all
Simple lift-and-project cuts
Simple pivot-and-reduce cuts
'advanced' cuts include all
except reduce-and-split cuts, plus:
Strong Chvatal-Gomory cuts
an upper bound on the number of times
to generate cuts.
For details about cut generation algorithms (also called cutting plane methods), see Cornuéjols .
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 and/or during branch-and-bound.
These techniques are heuristic, meaning they are algorithms that can
succeed, but can also fail. You set the
Heuristics option. The options are:
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 .
a hybrid procedure combining ideas from
local branching to search for integer feasible solutions.
the LP solution to the relaxed problem at a node. It rounds the integer
components in a way that attempts to maintain feasibility.
not search for a feasible point. It simply takes any feasible point
it encounters in its branch-and-bound search.
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 fTx. 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 xfeas satisfies
fTxfeas ≥ fTx,
because fTx 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 xLP, corresponding to an integer specified in intcon, is not an integer. Here, xLP 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 fTxLP, 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
'maxpscost' — Choose the
fractional variable with maximal pseudocost.
'mostfractional' — Choose
the variable with fractional part closest to
'maxfun' — Choose the variable
with maximal corresponding absolute value in the objective vector
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 pi– and pi+,
pi– = x(i)
pi+ = 1 – pi–.
'simplebestproj' — Choose
the node with the best projection.
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
The difference between the lower and upper bounds
on the objective function is less than the
The number of explored nodes exceeds the
The number of integer feasible points exceeds the
 Andersen, E. D., and Andersen, K. D. Presolving in linear programming. Mathematical Programming 71, pp. 221–245, 1995.
 Cornuéjols, G. Valid inequalities for mixed integer linear programs. Mathematical Programming B, Vol. 112, pp. 3–44, 2008.
 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.
 Mészáros C., and Suhl, U. H. Advanced preprocessing techniques for linear and quadratic programming. OR Spectrum, 25(4), pp. 575–595, 2003.
 Nemhauser, G. L. and Wolsey, L. A. Integer and Combinatorial Optimization. Wiley-Interscience, New York, 1999.
 Savelsbergh, M. W. P. Preprocessing and Probing Techniques for Mixed Integer Programming Problems. ORSA J. Computing, Vol. 6, No. 4, pp. 445–454, 1994.
 Wolsey, L. A. Integer Programming. Wiley-Interscience, New York, 1998.