Aspects of OR - Integer Programming (Part 4)

In Part 2 we learned branch and bound — a tree search that uses LP bounds to prune the solution space. In Part 3 we learned cutting planes — valid inequalities that tighten the LP relaxation. Each is powerful on its own but limited: branch and bound with weak LP bounds produces enormous trees, and the pure cutting plane algorithm converges slowly.

Branch-and-cut combines both ideas into the algorithmic engine behind every modern IP solver. In this final part of the IP mini-series, we explain how branch-and-cut works, what else modern solvers do beyond the core algorithm, and see it in action with Gurobi.

The branch-and-cut algorithm

Branch-and-cut modifies branch and bound by adding a cutting plane phase at each node:

1. At each node of the B&B tree, solve the LP relaxation.
2. Before branching, try to generate cutting planes violated by the current LP solution.
3. If effective cuts are found, add them to the LP and resolve. Repeat until no more useful cuts can be found (or a round limit is reached).
4. If the LP solution is still fractional, branch as in standard B&B.

This gets the best of both worlds: cuts tighten the LP bounds (leading to more pruning), and branching handles the remaining integrality gap that cuts alone cannot close.

The key design question is: how aggressively should we generate cuts at each node? Generating many cuts tightens the bound but makes the LP larger and slower to solve. Modern solvers invest heavily in cuts at the root node (where the payoff is greatest, since every subsequent node inherits the root cuts) and generate cuts more sparingly deeper in the tree.

What modern solvers actually do

A solver like Gurobi or CPLEX performs many operations beyond basic branch-and-cut. Here is a simplified overview of the solve process.

Presolve

Before any LP is solved, the solver simplifies the model. This includes:

• Fixing variables whose values are determined by the constraints (e.g., if $x_1 + x_2 \leq 1$ and the objective strongly favors $x_1$, the solver may deduce $x_2 = 0$).
• Tightening variable bounds by propagating constraints.
• Removing redundant constraints that are implied by others.
• Detecting infeasibility early, before the expensive solve begins.
• Reformulating parts of the model into tighter forms.

Presolve alone can reduce a problem by 50% or more.

Root node processing

At the root node, the solver invests heavily:

• Multiple rounds of cuts from various families (Gomory, cover, clique, flow cover, MIR, and many more), keeping only the most effective ones.
• Primal heuristics to find good feasible solutions quickly — these serve as the initial incumbent for pruning. Among these heuristics are LP-based rounding methods like randomized rounding (round each fractional variable to 1 with probability equal to its LP value) and iterative rounding (round the most integer-looking variable, fix it, re-solve the LP, repeat). Unlike the naive rounding we dismissed in Part 1, these methods use the LP solution structure intelligently and often come with provable approximation guarantees for specific problem classes.

Tree search

The solver explores the B&B tree with:

• Adaptive node selection — switching between best-first and diving strategies based on progress.
• Cuts at selected nodes — not every node, to balance bound quality with LP solve speed.
• Periodic heuristics — running primal heuristics at regular intervals to improve the incumbent.
• Dynamic strategy adjustment — monitoring the MIP gap and adapting the balance between proving optimality and finding better solutions.

Parallelism

Modern solvers exploit multiple CPU cores by exploring different subtrees in parallel. Gurobi supports both deterministic parallelism (same result regardless of timing) and opportunistic parallelism (potentially faster but non-reproducible).

Seeing it in action with Gurobi

Let us solve a knapsack large enough to see cuts in the solver log:

import gurobipy as gp
from gurobipy import GRB
import random

random.seed(42)

n = 20
weights = {j: random.randint(5, 50) for j in range(n)}
values = {j: random.randint(10, 100) for j in range(n)}
capacity = int(0.4 * sum(weights.values()))

model = gp.Model('knapsack_20')
model.Params.OutputFlag = 1

x = model.addVars(n, vtype=GRB.BINARY, name='x')

model.setObjective(gp.quicksum(values[j] * x[j] for j in range(n)), GRB.MAXIMIZE)
model.addConstr(gp.quicksum(weights[j] * x[j] for j in range(n)) <= capacity, 'capacity')

model.optimize()

selected = [j for j in range(n) if x[j].X > 0.5]
print(f'\nSelected items: {selected}')
print(f'Total weight: {sum(weights[j] for j in selected)} / {capacity}')
print(f'Total value: {model.ObjVal:.0f}')

In the solver log, you will see lines like:

Cutting planes:
  Cover: 3
  GUB cover: 1

This shows that Gurobi added cover inequalities (and GUB cover inequalities, a generalization) to tighten the LP relaxation at the root node. For this problem, the cuts combined with presolve may close the gap entirely, requiring zero or very few B&B nodes.

Measuring the impact of cuts

To see how much cuts help, we can solve the same problem with and without them. Because Gurobi may retain information from a previous solve when using model.reset(), we rebuild the model from scratch for a clean comparison:

import gurobipy as gp
from gurobipy import GRB
import random

def build_knapsack_model():
    random.seed(42)
    n = 20
    weights = {j: random.randint(5, 50) for j in range(n)}
    values = {j: random.randint(10, 100) for j in range(n)}
    capacity = int(0.4 * sum(weights.values()))

    model = gp.Model('knapsack_20')
    model.Params.OutputFlag = 0
    x = model.addVars(n, vtype=GRB.BINARY, name='x')
    model.setObjective(
        gp.quicksum(values[j] * x[j] for j in range(n)), GRB.MAXIMIZE
    )
    model.addConstr(
        gp.quicksum(weights[j] * x[j] for j in range(n)) <= capacity, 'cap'
    )
    return model

# Without cuts
model = build_knapsack_model()
model.Params.Cuts = 0
model.optimize()
print(f'B&B only:        {model.NodeCount:>6} nodes')

# With cuts (default)
model = build_knapsack_model()
model.Params.Cuts = -1
model.optimize()
print(f'Branch-and-cut:  {model.NodeCount:>6} nodes')

For many problems, enabling cuts reduces the number of B&B nodes by an order of magnitude or more.

Summary of the IP mini-series

Across the four parts, we built up the full picture of how integer programs are solved:

1. Part 1 — IP definitions, LP relaxation, why rounding fails, formulation strength.
2. Part 2 — Branch and bound: tree search, pruning by bound/infeasibility/integrality, node and variable selection.
3. Part 3 — Cutting planes: geometric intuition, Gomory cuts, cover inequalities.
4. Part 4 (this post) — Branch-and-cut, presolve, heuristics, LP-based rounding, parallelism, and solver internals.

Together with the LP mini-series, these posts cover the core theory and algorithms of mathematical programming. This foundation supports everything that follows in the Aspects of OR series — from scheduling to vehicle routing to network design.