Incumbent Solutions and Upper Bounds

In branch and bound for a minimization integer program, the best feasible integer solution found so far is the incumbent. Its objective value gives an upper bound on the optimal value, which combined with the LP relaxation's lower bound brackets the optimum and powers pruning by bound.

Step 1 of 157%

Tutorial

The Incumbent Solution

While running branch and bound on an integer program, subproblems occasionally produce points that satisfy every constraint, including integrality. Such points are called feasible integer solutions.

The incumbent is the feasible integer solution with the best objective value found so far during the algorithm. Its objective value is the incumbent value, denoted $\bar{z}$ .

For a minimization problem, "best" means smallest objective value. At the start of branch and bound, no feasible integer solution has been found yet, so the incumbent is undefined and we initialize

\bar{z} = +\infty.

For example, suppose during a minimization B&B we have found three feasible integer solutions with objective values $34$ , $27$ , and $31$ . The best (smallest) is $27$ , so the incumbent is the solution with value $\bar{z}=27$ .