MixedInteger Linear Programming Algorithms
MixedInteger Linear Programming Definition
A mixedinteger linear program (MILP) 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 unknowns
Bounds 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 Algorithm
Algorithm Overview
intlinprog
uses this basic strategy to solve
mixedinteger 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 MixedInteger Program Preprocessing to tighten the LP relaxation of the mixedinteger problem.
Try Cut Generation to further tighten the LP relaxation of the mixedinteger problem.
Try to find integerfeasible 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.
Linear Program Preprocessing
According to the MixedInteger 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 [8].
Linear Programming
The initial relaxed problem is the linear programming problem with the same objective and constraints as MixedInteger 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 branchandbound algorithm are solved using linear programming solution techniques.
MixedInteger Program Preprocessing
During mixedinteger 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 mixedinteger program preprocessing is to simplify ensuing branchandbound calculations. Preprocessing involves quickly preexamining and eliminating some of the futile subproblem candidates that branchandbound would otherwise analyze.
For details about integer preprocessing, see Savelsbergh [10].
Cut Generation
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:
Mixedinteger rounding cuts
Gomory cuts
Clique cuts
Cover cuts
Flow cover cuts
Furthermore, if the problem is purely integer (all variables are
integervalued), then intlinprog
also uses the following
cuts:
Strong ChvatalGomory cuts
Zerohalf cuts
'intermediate'
cuts include all 'basic'
cuts, plus:
Simple liftandproject cuts
Simple pivotandreduce cuts
Reduceandsplit cuts
'advanced'
cuts include all
'intermediate'
cuts except reduceandsplit cuts,
plus:
Strong ChvatalGomory cuts
Zerohalf cuts
For purely integer problems, 'intermediate'
uses the most
cut types, because it uses reduceandsplit 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].
Heuristics for Finding Feasible Solutions
To get an upper bound on the objective function, the branchandbound
procedure must find feasible points. A solution to an LP relaxation during
branchandbound can be integer feasible, which can provide an improved upper
bound to the original MILP. Certain techniques find feasible points faster
before or during branchandbound. intlinprog
uses these
techniques at the root node and during some branchandbound iterations. These
techniques are heuristic, meaning they are algorithms that can succeed but can
also fail.
Heuristics can be start heuristics, which help the
solver find an initial or new integerfeasible solution. Or heuristics can be
improvement heuristics, which start at an
integerfeasible point and attempt to find a better integerfeasible point,
meaning one with lower objective function value. The
intlinprog
improvement heuristics are
'rins'
, 'rss'
, 1opt, 2opt, and
guided diving.
Set the intlinprog
heuristics using the
'Heuristics'
option. The options are:
Option  Description 

'basic' (default)  The solver runs rounding heuristics twice with
different parameters, runs diving heuristics twice with
different parameters, then runs 
'intermediate'  The solver runs rounding heuristics twice with
different parameters, then runs diving heuristics twice with
different parameters. If there is an integerfeasible
solution, the solver then runs 
'advanced'  The solver runs rounding heuristics twice with
different parameters, then runs diving heuristics twice with
different parameters. If there is an integerfeasible
solution, the solver then runs 
'rins' or the equivalent
'rinsdiving' 

'rss' or the equivalent
'rssdiving' 

'round' 

'rounddiving'  The solver works in a similar way to

'diving' 
Diving heuristics generally select one variable that should be integervalued, for which the current solution is fractional. The heuristics then introduce a bound that forces the variable to be integervalued, 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. 
'none' 

The main difference between 'intermediate'
and
'advanced'
is that 'advanced'
runs
heuristics more frequently during branchandbound iterations.
In addition to the previous table, the following heuristics run when the
Heuristics
option is 'basic'
,
'intermediate'
, or 'advanced'
.
ZI round — This heuristic runs whenever an algorithm solves a relaxed LP. The heuristic goes through each fractional integer variable to attempt to shift it to a neighboring integer without affecting the feasibility with respect to other constraints. For details, see Hendel [7].
1opt — This heuristic runs whenever an algorithm finds a new integerfeasible solution. The heuristic goes through each integer variable to attempt to shift it to a neighboring integer without affecting the feasibility with respect to other constraints, while lowering the objective function value.
2opt — This heuristic runs whenever an algorithm finds a new integerfeasible solution. 2opt finds all pairs of integer variables that affect the same constraint, meaning they have nonzero entries in the same row of an
A
orAeq
constraint matrix. For each pair, 2opt takes an integerfeasible solution and moves the values of the variable pairs up or down using all four possible moves (upup, updown, downup, and downdown), looking for a feasible neighboring solution that has a better objective function value. The algorithm tests each integer variable pair by calculating the largest size (same magnitude) of shifts for each variable in the pair that satisfies the constraints and also improves the objective function value.
At the beginning of the heuristics phase, intlinprog
runs
the trivial heuristic unless
Heuristics
is 'none'
or you provide an
initial integerfeasible point in the x0
argument. The
trivial heuristic checks the following points for feasibility:
All zeros
Upper bound
Lower bound (if nonzero)
"Lock" point
The "lock" point is defined only for problems with finite upper and lower
bounds for all variables. The "lock" point for each variable is its upper or
lower bound, chosen as follows. For each variable j
, count
the number of corresponding positive entries in the linear constraint matrix
A(:,j)
and subtract the number corresponding negative
entries. If the result is positive, use the lower bound for that variable,
lb(j)
. Otherwise, use the upper bound for that variable,
ub(j)
. The "lock" point attempts to satisfy the largest
number of linear inequality constraints for each variable, but is not
necessarily feasible.
After each heuristic completes with a feasible solution,
intlinprog
calls output functions and plot functions.
See intlinprog Output Function and Plot Function Syntax.
If you include an
x0
argument, intlinprog
uses that value in the
'rins'
and guided diving heuristics until it finds a better
integerfeasible point. So when you provide x0
, you can obtain good results
by setting the 'Heuristics'
option to 'rinsdiving'
or
another setting that uses 'rins'
.
Branch and Bound
The branchandbound 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 branchandbound 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 branchandbound 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 to1
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 pseudocostbased 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 pseudocostbased score does not change for
k
consecutive variables, wherek
is an internally chosen value, usually between 5 and 10.Branch on the variable with the highest pseudocostbased 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 branchandbound 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 tok2
times for each variable, wherek2
is a small integer such as 4 or 8. Therefore,'reliability'
has even slower branching, but potentially fewer branchandbound iterations, compared to'strongpscost'
.'mostfractional'
— Choose the variable with fractional part closest to1/2
.'maxfun'
— Choose the variable with maximal corresponding absolute value in the objective vectorf
.
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 integerinfeasible component x(i) in the node, add up the smaller of p_{i}^{–} and p_{i}^{+}, wherep_{i}^{–} = x(i) – ⌊x(i)⌋
p_{i}^{+} = 1 – 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 branchandbound 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
orRelativeGapTolerance
tolerances.The number of explored nodes exceeds the
MaxNodes
option.The number of integer feasible points exceeds the
MaxFeasiblePoints
option.
For details about the branchandbound procedure, see Nemhauser and Wolsey [9] and Wolsey [11].
References
[1] Achterberg, T., T. Koch
and A. Martin. Branching rules revisited. Operations Research
Letters 33, 2005, pp. 42–54. Available at https://wwwm9.ma.tum.de/downloads/felixklein/20B/AchterbergKochMartinBranchingRulesRevisited.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/DiplomBerthold.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] Hendel, G. New Rounding and Propagation Heuristics for Mixed Integer Programming. Bachelor's thesis at Technische Universität Berlin, 2011. PDF available at https://opus4.kobv.de/opus4zib/files/1332/bachelor_thesis_main.pdf.
[8] Mészáros C., and Suhl, U. H. Advanced preprocessing techniques for linear and quadratic programming. OR Spectrum, 25(4), pp. 575–595, 2003.
[9] Nemhauser, G. L. and Wolsey, L. A. Integer and Combinatorial Optimization. WileyInterscience, New York, 1999.
[10] Savelsbergh, M. W. P. Preprocessing and Probing Techniques for Mixed Integer Programming Problems. ORSA J. Computing, Vol. 6, No. 4, pp. 445–454, 1994.
[11] Wolsey, L. A. Integer Programming. WileyInterscience, New York, 1998.