Consider a maximizing mixed-integer liner program with x1 0, x2, x3, x4 = 0 or 1. (a) Solve the problem by LP-based Branch and

Consider a maximizing mixed-integer liner program with x1 Ú 0, x2, x3, x4 = 0 or 1.

(a) Solve the problem by LP-based Branch and Bound Algorithm 12A, using the given table of candidate problem solutions, and record your computations in a branch and bound tree. When more than one node is active, apply the Depth-
First rule, breaking ties in favor of the child with newly fixed variable value most like that of its parent’s relaxation optimum. When needed, branch on the fractional variable of the most recent LP relaxation that is closest to integer in value. Start with no incumbent solution, and do not round to create early incumbents.

(b) Briefly explain why the logic of branch and bound assures your final solution is optimal.

(c) Point out the first time in your enumeration of

(a) where a comparable search based on best-first enumeration would have taken up a different candidate than was done in your depth-first sequence.
Explain.

X2 X3 x4 LP Rela.xation Value # # # # # +++00 # # (0.0, 0.58, 1.00, 0.00) 135.0 # 0 (0.0, 0.58, 1.00, 0.00) 135.0 # 1 (0.0, 0.00, 0.75, 1.00) 125.0 # (0.0, 1.00, 0.00, 1.00) 110.0 0 (0.9, 1.00, 0.00, 0.00) 87.5 # 0 1 (0.0, 1.00, 0.00, 1.00) 110.0 # 1 # (0.0, 0.58, 1.00, 0.00) 135.0 # 1 0 (0.0, 0.58, 1.00, 0.00) 135.0 # 1 1 infeasible 0 # # (0.0, 0.00, 1.00, 0.64) 131.8 0 # 0 (0.6, 0.00, 1.00, 0.00) 117.5 0 # 1 (0.0, 0.00, 0.75, 1.00) 125.0 0 0 % (1.0,0.00, 0.00, 1.00) 80.0 000 (1.9, 0.00, 0.00, 0.00) 57.5 0 0 1 (1.0, 0.00, 0.00, 1.00) 80.0 0 1 # (0.0, 0.00, 1.00, 0.64) 131.8 0 1 0 (0.6,0.00, 1.00, 0.00) 117.5 0 1 1 infeasible 1 # # (0.0, 1.00, 0.69,0.00) 128.8 1 # 0 (0.0, 1.00, 0.69, 0.00) 128.8 1 # 1 (0.0, 1.00, 0.00, 1.00) 110.0 10 # (0.0, 1.00, 0.00, 1.00) 110.0 10 0 (0.9, 1.00, 0.00, 0.00) 87.5 10 1 (0.0, 1.00, 0.00, 1.00) 110.0 1 1 # infeasible 1 1 0 infeasible 1 1 1 infeasible