Integer Programming

Problem Classes

Integer Linear Program (ILP): all variables are integer-constrained.

minimize    c^T x
subject to  Ax <= b
            x in Z^n

Mixed-Integer Program (MIP): some variables are integer, others continuous.

minimize    c^T x + d^T y
subject to  Ax + By <= b
            x in Z^p, y in R^q

Binary (0-1) programs restrict integer variables to {0, 1}. Many combinatorial problems (set cover, knapsack, scheduling) are naturally binary.

ILP is NP-hard in general. Even feasibility of binary programs is NP-complete (reduces from SAT). However, modern solvers routinely handle instances with millions of variables through sophisticated algorithms.

LP Relaxation

Dropping integrality constraints gives the LP relaxation, which provides a lower bound (for minimization). The integrality gap is the ratio between the IP optimum and the LP relaxation optimum.

A tight LP relaxation (small integrality gap) is critical for solver performance. Formulation strength matters: different valid formulations of the same problem can have drastically different LP relaxation bounds.

Total Unimodularity

A matrix A is totally unimodular (TU) if every square submatrix has determinant in {-1, 0, 1}. If A is TU and b is integral, the LP relaxation polyhedron {x : Ax <= b, x >= 0} has all integer vertices.

Key TU examples:

Node-edge incidence matrices of bipartite graphs
Network flow constraint matrices
Interval scheduling matrices

This is why network flow problems (shortest path, max flow, min-cost flow, assignment) solve as LPs despite being integer problems.

Branch and Bound

The primary algorithmic framework for solving IPs.

Algorithm

Solve LP relaxation at the root node. If the solution is integral, done.
Select a fractional variable x_j = f (branching). Create two subproblems: x_j <= floor(f) and x_j >= ceil(f).
Solve LP relaxations of subproblems. Prune nodes where:
- LP is infeasible (pruned by infeasibility)
- LP bound >= best known integer solution (pruned by bound)
- LP solution is integral (update incumbent if better)
Select next node (search strategy) and repeat.

Branching Strategies

Most fractional: branch on the variable closest to 0.5.
Strong branching: tentatively branch on several candidates, evaluate LP bounds, pick the one giving the best bound improvement. Expensive but effective.
Reliability branching: hybrid—use strong branching initially, then switch to pseudocost branching once estimates are reliable.

Node Selection

Best-first: expand the node with the best bound. Optimizes bound improvement but uses more memory.
Depth-first: dive deep to find feasible solutions quickly. Low memory, good for finding incumbents.
Best-estimate: predict which node will yield the best integer solution.

Cutting Planes

Add valid inequalities that cut off fractional LP solutions without removing integer feasible points.

Gomory Cuts

From the optimal simplex tableau, if basic variable x_i has fractional value, the Gomory fractional cut is:

sum_j (f_ij) * x_j >= f_i0

where f_ij = a_ij - floor(a_ij) are the fractional parts of the tableau row. Gomory's algorithm (pure cutting plane) converges finitely but is slow in practice.

Other Cut Families

| Cut Type | Applicable To | |----------|---------------| | Gomory mixed-integer | MIPs with mixed variables | | Knapsack covers | Knapsack constraints | | Flow covers | Fixed-charge network flow | | Clique / odd-hole | Binary packing/covering | | Lift-and-project | General 0-1 programs | | Split cuts | General MIPs |

Branch and Cut

The dominant paradigm in modern IP solvers. Combines branch and bound with cutting plane generation at each node.

At each node, solve the LP relaxation.
Search for violated cutting planes. Add them to tighten the relaxation.
Re-solve. Repeat cut generation until no more useful cuts are found or a limit is reached.
Branch if the solution is still fractional.

Additional solver techniques:

Presolve: simplify the formulation (fix variables, remove redundant constraints, tighten bounds).
Heuristics: rounding, diving, RINS, feasibility pump to find good incumbents early.
Conflict analysis: learn from infeasible subproblems (inspired by SAT solvers).

Column Generation

For problems with exponentially many variables (e.g., cutting stock, crew scheduling), enumerate variables implicitly.

Solve a restricted master problem (RMP) with a subset of columns.
Solve a pricing subproblem to find the column with the most negative reduced cost.
If no negative reduced cost column exists, the current RMP solution is optimal for the full problem.
Otherwise, add the column and re-solve.

Branch and price combines column generation with branch and bound for integer solutions.

TSP Formulations

The Traveling Salesman Problem illustrates IP formulation choices.

Subtour Elimination (Dantzig-Fulkerson-Johnson)

minimize  sum_{i,j} c_ij * x_ij
subject to  sum_j x_ij = 2         for all i  (degree constraints)
            sum_{i,j in S} x_ij <= |S| - 1   for all S subset V, 2 <= |S| <= n-1
            x_ij in {0, 1}

Exponentially many subtour constraints—add them as cutting planes via separation (solve min-cut).

Miller-Tucker-Zemlin (MTZ)

Compact formulation with O(n^2) constraints using auxiliary variables u_i:

u_i - u_j + n * x_ij <= n - 1    for all i != j, i,j >= 2

MTZ is compact but gives a weak LP relaxation compared to subtour elimination.

Modeling Techniques

Big-M constraints: link binary indicators to continuous variables. Use tight M values.
SOS constraints (Type 1, Type 2): ordered sets with adjacency restrictions.
Indicator constraints: if y = 1 then g(x) <= 0. Handled natively by modern solvers.
Piecewise linear: model via SOS2 or binary expansion.
Symmetry breaking: add constraints to eliminate equivalent solutions.

Connections

LP relaxation fundamentals (→ 01-linear-programming.md).
Combinatorial structure and matroids (→ 07-combinatorial-optimization.md).
Solver implementations and modeling (→ 09-optimization-solvers.md).