DASE7034 Chap.7 Relaxations, Integrality and Branch-and-Bound
Relaxations, Integrality and Branch-and-Bound
Branch-and-bound partitions the integer search space while LP relaxations provide bounds. A feasible integer solution becomes the incumbent, and a node closes when its relaxation is infeasible, already integer or unable to improve the incumbent.
Bound direction depends on whether the problem maximises or minimises, so every pruning decision must be labelled.
Start with a relaxation bound
At the root node, remove the integer restrictions and solve the resulting linear program. In a maximisation problem, this relaxation value is an upper bound because allowing fractional choices cannot make the best value worse. In minimisation it is a lower bound.
If the relaxation solution is already integer, it is optimal for the integer model. Otherwise, a separate feasible integer solution supplies an incumbent, whose value gives the opposite side of the optimality gap.
Branch to exclude the fractional solution
Select a variable whose relaxation value is fractional.
If its value is 3.6, create one child with x less than or equal to 3 and another with x greater than or equal to 4. These branches are disjoint and together retain every possible integer value while removing the current fractional point. Solve or bound each child, record its added restriction and keep objective direction visible.
Branching on a binary variable similarly creates the cases zero and one.
Fathom nodes for explicit reasons
A node may close because its relaxation is infeasible, because its relaxation solution is integer or because its bound cannot beat the incumbent. For maximisation, prune by bound when a node's upper bound is no greater than the incumbent value; for minimisation, prune when its lower bound is no less.
If an integer relaxation solution improves the incumbent, update the incumbent before comparing other open nodes. Labelling the reason beside every closed node prevents reversed inequalities and unsupported pruning.
Certify the final gap
The search ends when no open node can contain a better integer solution. Then the incumbent is globally optimal under the model.
Before termination, compare the incumbent with the best remaining node bound to report an absolute or relative gap, while treating zero and sign conventions carefully. Node-selection and branching rules affect effort but not the underlying proof when bounds are valid.
A clear tree therefore records node constraints, relaxation values, fractional branch choices, incumbent updates and the exact reason each subtree is discarded.
What this chapter covers
- 01
Relaxation bounds
- 02
Incumbent solutions
- 03
Fractional branching
- 04
Pruning rules
- 05
Minimum-cost flow integrality
Worked example · free
Prune a maximisation branch
- 2State that the relaxation is an upper bound.
- 2Compare the node bound with the incumbent.
- 2Prune and state the optimality implication.
Key terms
- Relaxation Bound
- The objective value of a less restricted model used to limit what a branch can achieve.
- Incumbent
- The best feasible integer solution discovered so far during a search.
- Optimality Gap
- The difference between the incumbent value and the best remaining bound, expressed in a chosen scale.
Relaxations, Integrality and Branch-and-Bound FAQ
Which branches cover a fractional integer value?
If an integer variable has relaxed value 2.5, use x less than or equal to 2 and x greater than or equal to 3. The branches cover every integer possibility and exclude the current fractional point.
Why do bound directions reverse for minimisation?
A relaxation enlarges the feasible set. In minimisation that can only lower or preserve the objective, so the relaxation is a lower bound, while a feasible incumbent is an upper bound.
Why can minimum-cost flow be solved as an LP?
Its node-balance structure has an integrality property: with integer supplies, demands and capacities, an LP optimum can be integer. This special structure does not apply to arbitrary integer programs.
Exam move
Annotate every tree node with relaxation value, variable split, integrality status and pruning reason. After each incumbent update, revisit open nodes using the correct bound direction. Finish by reporting the incumbent and best remaining bound rather than an unexplained tree picture. Begin each tree with a header stating maximisation or minimisation and the resulting meaning of a relaxation bound.
At a fractional node, write the selected variable value and both child inequalities so the branches are visibly disjoint and exhaustive for integer values. Whenever an integer solution appears, verify it against the original model before calling it an incumbent. Label every closed node as infeasible, integer or pruned by bound, and write the comparison inequality beside bound pruning.
Revisit open nodes after each incumbent improvement because a stronger incumbent may close several subtrees. Periodically calculate the best open bound and compare it with the incumbent to express what remains uncertified. On completion, explain why no open node can contain a better integer solution.
For practice, reverse the problem direction in the same tree and rewrite every bound comparison; this exposes memorised pruning rules that ignore whether the objective is maximised or minimised.
Working through Relaxations, Integrality and Branch-and-Bound in DASE7034? Sia is AskSia’s AI Mathematics tutor — ask any DASE7034 Relaxations, Integrality and Branch-and-Bound question and get a clear, step-by-step explanation grounded in how DASE7034 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.