The branch and bound tree that follows shows the incomplete solution of a maximizing ILP

by LP-based Algorithm 12A, with numbers next to nodes indicating LP relaxation solution values.

Node 4 has just produced the first incumbent solution, and nodes a to d remain unexplored.

(a) Show which unexplored nodes could be immediately terminated by parent bound if the incumbent at node 4 had objective function value 205. How about 210?

(b) Determine the best upper bound on the ultimate ILP optimal value that is available after processing of node 4.

(c) Assuming the incumbent at node 4 has objective value 195, compute the maximum absolute and percent objective value error in accepting the incumbent as an approximate optimum.

Transcribed Image Text:

x2=1 x=1 (1, 0.2, 0) 65.4 32=0 (0.53, 1, 0) 99 x=0 x3=1 (0, 1, 0.64) 98.4 x3=0 infeasible (1,0,0.14) 61.2 (0,0.50, 1) 77 (10) (0,1,0) 72 X3-1 x3=0 x2=1 x2=0 infeasible (1,0,0) 51 8 infeasible 9 (0, 0, 1) 41 FIGURE 12.11 Branch and Bound Tree for Exercise 12-30