Branch and Bound in Integer Programming

Beginner → intermediate

Why LP relaxations are the engine of “proof” in MIP

A relaxation means “allow more solutions.” In ILP/MILP, the most common relaxation is the LP relaxation: temporarily drop integrality and solve a continuous linear program. Because the relaxation is easier, its objective value is a provable bound on the integer optimum.

That’s why the LP relaxation bound is both a theory concept and a practical diagnostic: it predicts how much pruning power branch-and-bound will have.

Advanced (simplified)

Why solvers track two numbers: incumbent vs best bound

Think of MIP progress as two moving targets: (1) the best feasible integer solution found (the incumbent) and (2) the best bound proven from relaxations over all open nodes (the best bound). When these meet (within tolerances), optimality is proven.

People ask

How does branch-and-bound work in integer programming?

Branch-and-bound repeatedly: (1) solves an LP relaxation to get a bound, (2) branches when the solution is fractional, and (3) prunes (fathoms) nodes that cannot contain a better integer solution than the current incumbent.

If you want a quick “see it” exercise: solve your ILP in the ILP calculator, then solve the relaxed version in the LP calculator and compare objectives.

People ask

What is fathoming (pruning) in branch-and-bound?

Fathoming means “this node is finished; don’t explore its children.” A node is fathomed when: it’s infeasible, it produces an integral solution (so it can update the incumbent), or its bound is already worse than the incumbent (so it can’t possibly help).

People ask

Why does branch-and-bound solve an LP at every node?

LP relaxations are usually much cheaper than ILPs and they produce bounds that make pruning possible. Without bounds, the solver would be forced into an uninformed combinatorial search.

People ask

What is the difference between branch-and-bound and branch-and-cut?

Branch-and-bound uses branching + relaxations. Branch-and-cut additionally adds cutting planes (valid inequalities) to tighten relaxations and improve bounds. Most modern MIP solvers are effectively branch-and-cut by default.

People ask

When should you stop early if the optimality gap is not zero?

Stop early when the incumbent is implementable and the remaining uncertainty (gap) is below your decision tolerance. If the gap is large and the LP bound seems unrealistic, improving your formulation (bounds, Big‑M, symmetry) often helps more than “running longer.” Use optimality gap in MIP for correct interpretation.

Algorithm

Step 1: Solve the root LP relaxation (your first difficulty forecast)

The root LP relaxation provides the first strong bound. If it’s far from any plausible integer solution, the model may require heavy branching. This is exactly why professionals compute the LP relaxation bound early.

Algorithm

Step 2: Find an incumbent (feasible integer solution)

Solvers use heuristics to find a feasible integer solution. A better incumbent increases pruning power because more nodes become “not worth exploring.”

Algorithm

Step 3: Branch on a fractional variable

If the LP solution violates integrality, the solver splits the problem into child nodes by adding constraints (e.g., x ≤ k and x ≥ k+1) so each child removes part of the fractional region.

Algorithm

Step 4: Fathom nodes aggressively

Most nodes are never fully explored—success comes from pruning. The next section gives the exact pruning rules for minimization vs maximization.

Cheat sheet

“Bound-dominated” depends on min vs max

Branching

Branching variable selection (what “strong branching” means in plain English)

Solvers usually branch on a variable that is fractional in the LP solution (e.g., a binary at 0.43). “Strong branching” roughly means the solver previews a few candidate branches and chooses the one that improves bounds the most.

You don’t need to implement branching rules, but the symptoms matter: if branching produces little improvement in bounds, your formulation may be too loose (e.g., Big‑M too large or bounds missing).

Search strategy

Depth-first vs best-bound (finding solutions fast vs proving fast)

Bounds

Why cuts can shrink the tree

Cutting planes remove fractional LP solutions while keeping all integer-feasible solutions. That tightens node relaxations, improves bounds, and increases pruning.

If you need practical tightening patterns (bounds, Big‑M, linking), use How to Model an ILP.

Gap

Interpret gap as a certified interval

Minimization: BestBound ≤ Optimum ≤ Incumbent
Maximization: Incumbent ≤ Optimum ≤ BestBound

Treat the gap as a statement about what’s mathematically still possible—not as a judgment of “good vs bad.” For correct interpretation details, see optimality gap in MIP.

Tooling

Where can you use a “branch and bound calculator”?

In practice, a “branch and bound calculator” is an ILP/MILP solver that uses branch-and-bound (often branch-and-cut) to search for an integer-feasible solution and prove optimality. On CalcTypes, you can run branch-and-bound online using our Integer Linear Programming (ILP/MILP) calculator.

To see the bound logic that drives branch-and-bound, compute the root LP relaxation in the Linear Programming calculator, then compare it to the best integer solution. This comparison is exactly what the LP relaxation bound concept formalizes.

Mini-lab

Lab 1: Compute a bound interval with ILP vs LP relaxation

1. Solve an integer model in the ILP calculator and record the incumbent.
2. Relax integrality and solve in the LP calculator to get the relaxation bound.
3. Write the certified interval that contains the optimum, and decide whether the remaining uncertainty is acceptable.

Worked example

Example 1: a tiny binary ILP showing bounds, branching, and pruning

Consider this maximization 0–1 ILP:

maximize   5x1 + 4x2
subject to 6x1 + 4x2 ≤ 7
           x1, x2 ∈ {0,1}

Root LP relaxation: allow 0 ≤ x ≤ 1. Then we can set x2 = 1 and x1 = 0.5 because 6(0.5) + 4(1) = 7. Objective becomes 5(0.5) + 4(1) = 6.5. Since this is maximization, 6.5 is an upper bound on the integer optimum.

Branch on x1:

• Node A: x1 = 0 ⇒ choose x2 = 1 ⇒ objective 4 (feasible integer incumbent = 4)
• Node B: x1 = 1 ⇒ constraint gives x2 ≤ 0.25 in LP ⇒ LP bound = 5 + 4(0.25) = 6

Node B can’t be pruned yet because its bound (6) could still beat the incumbent (4). Branch on x2 inside Node B:

• Node B1: x2 = 0 ⇒ objective 5 (new incumbent = 5)
• Node B2: x2 = 1 ⇒ infeasible (6+4>7) ⇒ fathomed

Now the best bound cannot exceed the incumbent, so optimality is proven: optimum = 5 at (x1=1, x2=0).

Worked example

Example 2: why Big‑M can make bounds stall (common MILP pattern)

If y is binary (“on/off”) and x is continuous, a common link is:

0 ≤ x ≤ U·y
y ∈ {0,1}

If U is extremely large, the LP relaxation can use fractional y to allow unrealistic x, producing overly optimistic bounds. That weakens pruning and can keep the gap stubbornly large. Fix by deriving the smallest valid U from real capacity/demand.

Troubleshooting

Log pattern → likely cause → next move

Speed

Modeling improvements usually beat solver tuning

• Tighten variable bounds (shrinks relaxations everywhere in the tree)
• Fix Big‑M/linking constants (use the smallest valid values)
• Reduce symmetry (fewer equivalent branches)
• Scale coefficients (improves numerical behavior)
• Use structure when possible (e.g., flow/transportation models)

If your model is mostly shipping/flow, try the Transportation Problem calculator before adding integer structure.

Glossary

• Node: a subproblem created by branching.
• Incumbent: best feasible integer solution found so far.
• Best bound: best proven bound across open nodes.
• Fathom/prune: discard a node (infeasible, integral, or dominated by bound).
• Root relaxation: LP relaxation at the root node (before branching).
• Cut: valid inequality added to tighten the relaxation.