ETF2480 Chap.8 Branch-and-Bound and Stronger Models
Branch-and-Bound and Stronger Models
Branch-and-bound solves an integer program by repeatedly solving LP relaxations, branching on fractional decisions and pruning subproblems that cannot improve the best feasible integer solution. The incumbent proves what is currently achievable, while node relaxations bound what remains possible. Nodes close through infeasibility, an integer relaxation solution or a dominated bound.
Cutting planes strengthen relaxations by removing fractional points without excluding any feasible integer solution. Two formulations can describe the same integer decisions but produce very different relaxations, so tighter links and valid inequalities can reduce search substantially. A trace should explain every incumbent update, bound comparison and pruning reason.
What this chapter covers
- 01
Relaxation bounds
- 02
Incumbents and feasible values
- 03
Branching on fractional variables
- 04
Infeasibility and bound pruning
- 05
Valid cutting planes
- 06
Strong versus weak formulations
Worked example · free
Update an incumbent and close nodes
- +1Prune Node A because its upper bound 50 cannot improve incumbent 52.
- +1Explore Node B because bound 61 leaves potential improvement.
- +2Update the incumbent to 57 when B1 supplies an integer-feasible solution.
- +2Prune B2 as infeasible; if no live node has bound above 57, certify 57 as optimal.
Key terms
- Branch-and-bound
- An exact search method combining relaxation bounds, branching and pruning.
- Incumbent
- The best feasible integer solution known at the current point in the search.
- Node bound
- A relaxation-based limit on how good any descendant solution can become.
- Fathoming
- Closing a search node because it is infeasible, integral or unable to beat the incumbent.
- Cutting plane
- A valid inequality that tightens the relaxation while retaining every feasible integer point.
Branch-and-Bound and Stronger Models FAQ
Why does branching preserve all integer options?
If an integer variable has fractional value 3.7, one child restricts x to at most 3 and the other restricts x to at least 4. They cover every integer possibility while excluding the current fractional point, so together they partition the relevant integer search without losing a feasible discrete value.
When can a node be pruned by bound?
For maximisation, prune when the node upper bound cannot exceed the incumbent. For minimisation, prune when the node lower bound cannot improve the incumbent. Always state objective direction before comparing numbers.
What makes a formulation stronger?
A stronger formulation has a tighter continuous relaxation while describing the same feasible integer decisions. Smaller valid big-M values, disaggregated links and problem-specific inequalities can improve bounds and reduce the branch-and-bound tree.
What belongs in the final search certificate?
Report the incumbent decision and objective, the best remaining bound, the gap convention and the termination reason. Those facts distinguish a proved optimum from a feasible time-limit solution with a quantified guarantee.
Exam move
Practise search traces as proofs. At each node record the relaxation status, bound, fractional variable, branch decision and pruning reason. Maintain a separate incumbent line and update it only with integer-feasible solutions. Work paired max and min examples so the bound direction does not become a memorised sign error.
For cuts, verify two conditions: the current fractional point violates the inequality, and every feasible integer point satisfies it. Compare a weak and strong formulation of the same logical decision by drawing or calculating their relaxations. Then explain why the tighter one improves bounds. When reading solver output, distinguish a proven optimal solution from a feasible solution stopped at a gap or time limit.
Report the guarantee that was actually established, not the one you hoped the algorithm would reach. Use a node table with separate columns for relaxation bound, feasible objective, branch restriction and closure reason. Before pruning by bound, write whether the problem is a maximisation or minimisation and compare in words.
When branching on a fractional value, verify that the two child restrictions cover every permitted integer while excluding the current relaxation point. Create examples in which an early incumbent is weak and observe how a better feasible solution closes additional nodes. For a proposed cut, test several feasible integer points as well as the offending fractional point, then seek an algebraic validity argument.
Compare two equivalent integer formulations by solving their continuous relaxations and recording the root gaps. In solver reports, distinguish the best incumbent, best bound, relative gap and termination reason. A time-limit result can still support a quantified guarantee, but it cannot be called proven optimal unless the reported gap and status justify that statement.
Working through Branch-and-Bound and Stronger Models in ETF2480? Sia is AskSia’s AI Management tutor — ask any ETF2480 Branch-and-Bound and Stronger Models question and get a clear, step-by-step explanation grounded in how ETF2480 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
