Incumbent Solution¶

Definition¶

The incumbent solution in branch-and-bound is the best feasible solution of the original integer problem found so far. Its objective value supplies a lower bound for maximization and an upper bound for minimization.

Interpretation¶

The incumbent is the best solution found so far that can actually be implemented: it satisfies every original restriction, integrality included. In branch-and-bound it is the record to beat. Its value $L$ is a lower bound for maximization, and every subproblem is judged by whether it could still do better than $L$ .

Two step lines over the nodes explored: the incumbent value rising from 9 to 12 to 13 and the best remaining bound falling, with a pruned node whose bound is below the incumbent.

The blue step line is the incumbent value of a maximization problem. It only rises, from $L=9$ to $L=12$ to $L=13$ $13$ , because the incumbent is replaced only by a better feasible solution. The red dashed line is the best bound still possible among the unexplored nodes; it can only fall. The orange node has bound $11\le L=12$ $12$ : nothing inside it can beat the incumbent, so it is pruned without further branching.

Only a point that satisfies all restrictions may become the incumbent. A fractional optimum of an LP relaxation gives a bound, not an incumbent; an integral relaxed optimum, or a point found by a heuristic and checked for feasibility, does qualify. A good incumbent found early makes the pruning test, node bound at most $L$ , succeed more often.

A common slip is to treat the incumbent as optimal as soon as it is found. It is only the best known value; the gap between the two lines limits how much it could still improve, and only when no unexplored node has a bound above $L$ is the incumbent proven optimal.

Key Results¶

For maximization, replace the incumbent when a feasible solution with a larger value is found.
A fractional relaxed optimizer cannot become the incumbent.
Without a known feasible solution there is no incumbent value, although an obvious feasible point may already be available.

Examples¶

The graph shows the maximization incumbent value rising in steps and the best remaining bound falling. When valid global bounds meet, the incumbent is proven optimal.

Projects 1, 4, and 5 give an incumbent value 3.2.
Projects 1, 3, and 4 improve it to 3.4.

Prerequisites¶

Sources¶

OR Modelling · Week 3

Aliases: incumbent

Last updated: 20 October 2026 03:02