Mixed-Integer Linear Programming Algorithms

Mixed-Integer Linear Programming Definition
intlinprog Algorithm

Mixed-Integer Linear Programming Definition

A mixed-integer linear program is a problem with

Linear objective function, f^Tx, 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

$\min_{x} f^{T} x subject to {\begin{array}{l} x (intcon) are integers \\ A \cdot x \leq b \\ A e q \cdot x = b e q \\ l b \leq x \leq u b . \end{array}$

intlinprog Algorithm

Algorithm Overview
Linear Program Preprocessing
Linear Programming
Mixed-Integer Program Preprocessing
Cut Generation
Heuristics for Finding Feasible Solutions
Branch and Bound

Algorithm Overview

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.

Linear Program Preprocessing

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{matrix} A \cdot x \leq b \\ A e q \cdot x = b e q . \end{matrix}$

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 [1] and Mészáros and Suhl [5].

Linear Programming

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^Tx_LP ≤ f^Tx,

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.

Mixed-Integer Program Preprocessing

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

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:

Mixed-integer rounding cuts
Gomory cuts
Cliques 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 [2].

Heuristics for Finding Feasible Solutions

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 [3].
'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.

Branch and Bound

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^Tx. 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^Tx_feas ≥ f^Tx,

because f^Tx 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^Tx_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.
Pseudocost
The peudocost of a variable i is based on empirical estimates of the change in the lower bound when i has been chosen as the branching variable, combined with the fractional part of the i component of the current point x. The fractional part p is in two pieces, the lower part and the upper part:
p_i^– = x(i) – ⌊x(i)⌋
p_i⁺ = 1 – p_i^–.
Let x_i^– be the solution of the linear program restricted to have x(i) ≤ ⌊x(i)⌋, and let the change in objective function be denoted
Δ_i^– = f^Tx_i^– – f^Tx.
Similarly, Δ_i⁺ is the change in objective function when the problem is restricted to have x(i) ≥ ⌈x(i)⌉.
The objective gain per unit change in variable x_i is
$d_{i}^{-} = \frac{Δ_{i}^{-}}{p_{i}^{-}} or d_{i}^{+} = \frac{Δ_{i}^{+}}{p_{i}^{+}} .$
Let s_i^– and s_i⁺ be the empirical averages of d_i^– and d_i⁺ during the branch-and-bound algorithm up to this point. The empirical values are initialized to the absolute value of the objective coefficient f(i) for the terms before there are any observations. Then the 'maxpscost' rule is to branch on a node i that maximizes, for some positive weights w⁺ and w^–, the quantity
w^– * p_i^– * s_i^– + w⁺ * p_i⁺ * s_i⁺.
Roughly speaking, this rule chooses a coefficient that is likely to increase the lower bound maximally.
'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_i^– and p_i⁺, where
p_i^– = x(i) – ⌊x(i)⌋
p_i⁺ = 1 – p_i^–.
'simplebestproj' — Choose the node with the best projection.
Best Projection
Let x_B denote the best integer-feasible point found so far, x_R demote the LP relaxed solution at the root node, and x denote the node we examine. Let in(x) denote the sum of integer infeasibilities at the node x (see 'mininfeas'). The best projection rule is to minimize
$f^{T} x + \frac{f^{T} x_{B} - f^{T} x_{R}}{i n (x_{R})} i n (x) .$
If there is no integer-feasible point found so far, set f^Tx_B = 0.

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 [6] and Wolsey [8].

References

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

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

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

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

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

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

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

Was this topic helpful?

Documentation