The following table shows the LP relaxation outcomes for all possible combinations of fixed and free variables in branch and bound solution of a minimizing integer linear program over decision variables x1, x2, x3 = 0 or 1, x4 Ú 0. Solve the problem by LP-based Algorithm 12A and record your results in a branch and bound tree. Apply the depth first rule for selecting among active nodes and pick whichever of = 0 and = 1 is closest to the preceding relaxation value when nodes have equal depth. Branch on the integer-restricted variable with fractional relaxation value nearest to integer.

x1 x2 x3 x 
n 
# # # (0, 0.60, 0.14, 0) 60.9 # # 0 (0.20, 0.60, 0, 0) 61.0 # # 1 (0.60, 0, 1, 0) 69.0 # 0 # (0.60, 0, 1, 0) 69.0 # 0 0 Infeasible —
# 0 1 (0.60, 0, 1, 0) 69.0 # 1 # (0, 1, 0, 400) 4090.0 # 1 0 (0, 1, 0, 400) 4090.0 # 1 1 Infeasible —
0 # # (0, 0.60, 0.14, 0) 60.9 0 # 0 (0, 0.60, 0, 1.9) 73.6 0 # 1 (0, 0, 1, 6) 108.0 0 0 # (0, 0, 1, 6) 108.0 0 0 0 Infeasible —
0 0 1 (0, 0, 1, 6) 108.0 0 1 # (0, 1, 0, 400) 4090.0 0 1 0 (0, 1, 0, 400) 4090.0 0 1 1 Infeasible —
1 # # (1, 0.33, 0, 0) 65.0 1 # 0 (1, 0.33, 0, 0) 65.0 1 # 1 (1, 0, 1, 0) 83.0 1 0 # (1, 0, 0.71, 0) 69.3 1 0 0 Infeasible —
1 0 1 (1, 0, 1, 0) 83.0 1 1 # (1, 1, 0, 400) 4125.0 1 1 0 (1, 1, 0, 400) 4125.0 1 1 1 Infeasible —