MIP Journey

Prerequisites

You should have completed LP Fundamentals or be comfortable with:

• The simplex method (primal and dual)
• LP duality and reduced costs
• Why LP can be solved efficiently

---

1. What is Mixed-Integer Programming?

MIP extends LP by requiring some variables to be integers:

$$\min_{x,y} \quad c^T x + d^T y$$ $$\text{s.t.} \quad Ax + By = b$$ $$\quad x \geq 0, \quad y \in \mathbb{Z}^p_{\geq 0}$$

Where $x$ are continuous and $y$ are integer variables.

Why Integers Matter

Many real decisions are discrete:

• Build a factory or not (binary: 0 or 1)
• Number of trucks to deploy (integer)
• Which routes to use (binary selection)

Why MIP is Hard

LP is solvable in polynomial time. MIP is NP-hard.

Types of Integer Programs

Type	Variables	Example
Pure IP	All integer	Scheduling
Mixed IP (MIP)	Some integer, some continuous	Facility location
Binary IP	All 0-1	Set covering
MIQCP	Integer + quadratic constraints	Portfolio with lots

---

2. LP Relaxation and Bounds

The key idea: relax integer constraints to get an LP, then use its solution to guide the search.

LP Relaxation

Drop the integrality requirements: $$y \in \mathbb{Z}^p \quad \rightarrow \quad y \in \mathbb{R}^p$$

The resulting LP is called the LP relaxation.

Why Relaxation Helps

Example

MIP: min $-x$ s.t. $x \leq 2.5$, $x \in \mathbb{Z}_{\geq 0}$

• LP relaxation optimal: $x = 2.5$, objective = $-2.5$
• MIP optimal: $x = 2$, objective = $-2$

The LP bound ($-2.5$) is valid but optimistic.

The Integrality Gap

$$\text{Gap} = \frac{\text{MIP optimal} - \text{LP optimal}}{\text{MIP optimal}}$$

Smaller gaps mean:

• LP relaxation is a good approximation
• Branch-and-bound will be faster
• Cutting planes are more effective

---

3. Branch-and-Bound Trees

Branch-and-bound systematically explores the solution space by dividing it into smaller subproblems.

The Algorithm

Visualizing the Tree

                    Root (LP: -2.5)
                   /              \
        y₁ ≤ 2                    y₁ ≥ 3
           |                        |
      Node 1 (LP: -2.3)        Node 2 (LP: -2.8)
      Integer! Best = -2.3     Better bound, explore...
                               /              \
                    y₂ ≤ 1                    y₂ ≥ 2
                       |                        |
                   Infeasible              Pruned (bound ≥ -2.3)

Node Selection Strategies

Strategy	Description	When to use
Best-first	Explore node with best bound	Prove optimality
Depth-first	Explore deepest node	Find solutions fast, low memory
Best-estimate	Use heuristic prediction	Balance exploration
Diving	Go deep, then backtrack	Find good solutions early

---

4. Cutting Planes

Cutting planes tighten the LP relaxation by adding constraints that cut off fractional solutions without removing integer solutions.

What is a Cutting Plane?

A valid inequality $\alpha^T x \leq \beta$ that:

1. Is satisfied by all integer-feasible points
2. Cuts off the current fractional LP solution

Example: Gomory Cut

If the LP solution has $y_1 = 2.7$ with tableau row: $$y_1 + 0.3y_2 - 0.5y_3 = 2.7$$

The Gomory cut captures that the fractional parts must sum to an integer: $$0.3y_2 + 0.5y_3 \geq 0.7$$

(Because $y_1$ must be integer, the fractional contributions from $y_2, y_3$ must compensate.)

Types of Cuts

Cut Type	What it exploits	Generated by
Gomory	Simplex tableau structure	CglGomory
Knapsack cover	Knapsack constraints	CglKnapsackCover
Clique	Conflicts between binaries	CglClique
MIR (Mixed Integer Rounding)	Mixing integer and continuous	CglMixedIntegerRounding
Flow cover	Network structure	CglFlowCover
Lift-and-project	Disjunctions	CglLandP

Cut Management

Adding too many cuts can slow down the LP. Solvers manage cuts by:

• Limiting cuts per round
• Removing inactive cuts
• Aging out old cuts

---

5. Branching Strategies

How you choose which variable to branch on dramatically affects performance.

Most Fractional

Branch on the variable closest to 0.5 (most "undecided").

Pros: Simple, no overhead Cons: Often inefficient

Pseudo-cost Branching

Track history: for each variable, record how much the LP bound changed when branching on it before.

$$\text{score}_j = f_j \cdot \text{down_pseudo} + (1-f_j) \cdot \text{up_pseudo}$$

Pros: Learns from experience Cons: No history at start

Strong Branching

Actually solve the LP for both branches (partially) to estimate bound improvement.

Pros: Best predictions Cons: Expensive (many LPs per node)

Reliability Branching

Hybrid: use strong branching until pseudo-costs are "reliable" (enough observations), then switch.

---

6. Primal Heuristics

Heuristics find good (not necessarily optimal) integer solutions fast. A good incumbent enables massive pruning.

Why Heuristics Matter

Without an incumbent, we can't prune anything. The sooner we find a good solution:

• The more we can prune
• The better our gap estimate
• The faster we converge

Common Heuristics

---

7. Putting It Together: Branch-and-Cut

Modern MIP solvers combine everything into branch-and-cut:

The Full Algorithm

Performance in Practice

Technique	Typical impact
Presolve	2-10x speedup
Root cuts	10-100x speedup
Good incumbent	10-1000x speedup
Strong branching	2-5x speedup

Monitoring Progress

Solvers report:

• Gap: (incumbent - bound) / incumbent — how far from optimal
• Nodes: Number explored and remaining
• Time: Wall clock and per-node

When gap reaches tolerance (often 0.01%), solver declares optimal.

---

What's Next?

You now understand the core MIP algorithms! Next steps:

• Browse Cbc source - See the implementation
• Cutting plane algorithms - Deep dive on specific cuts
• Try it: Solve a MIP with Cbc and watch the log output. Match what you see to the concepts here.