The upper bound at the initial node of a branch and bound tree is given by
A) the value of the objective function of the LP relaxation .
B) the value of the objective function after the LP relaxation solution is rounded down to an integer solution.
C) the value of the objective function corresponding to an integer feasible solution determined on the basis of trial and error.
D) cannot be determined

Question

Quizplus · Accepted Answer

The LP relaxation provides the most optimistic estimate of the maximum possible value of the objective function, so it is the best estimate of the upper bound at the initial node. Rounding down the LP relaxation solution or using trial and error to find an integer feasible solution may result in a suboptimal upper bound. The upper bound cannot be obtained without solving the LP relaxation.

The Upper Bound at the Initial Node of a Branch