Consider a minimizing MILP over x1, x2, x3 binary and x4 0. (a) Solve the problem

Consider a minimizing MILP over x1, x2, x3 binary and x4 Ú 0.

(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 depth-forward-best-back enumeration would have taken up a different candidate than was done in your depth-first sequence.
Explain.

Transcribed Image Text:

X1 X2 X3 LP Optimum LP Value # # # # # # # 0 # 0 # 0 # 1 1 # # 1 10 # 1 0 # 0 # 0 # 00 00 00 01 01 0 1 1 # 1 # 1 # 10 10 10 11 +01+01+01+01+01+01+01+01+ # (1.0, 0.143, 0.0, 0.0) 2.429 (1.0, 0.143, 0.0, 0.0) 2.429 (0.7, 0.0, 1.0, 0.0) 5.400 # (1.0, 0.0, 0.25, 0.0) 3.000 (1.0, 0.0, 0.0, 0.067) 5.333 (0.7, 0.0, 1.0, 0.0) 5.400 (0.4, 1.0, 0.0, 0.0) 3.800 (0.4, 1.0, 0.0, 0.0) 3.800 (0.3, 1.0, 1.0, 1.0, 0.0) 7.600 # Infeasible Infeasible Infeasible # Infeasible Infeasible Infeasible # Infeasible 0 Infeasible 1 Infeasible # (1.0, 0.143, 0.0, 0.0) 2.429 (1.0, 0.143, 0.0, 0.0) 2.429 (1.0, 0.0, 1.0, 0.0) 6.000 # (1.0, 0.0, 0.25, 0.0) 3.000 (1.0, 0.0, 0.0, 0.067) 5.333 1 (1.0, 0.0, 1.0, 0.0) 6.000 # (1.0, 1.0, 0.0, 0.0) 5.000 1 1 0 (1.0, 1.0, 0.0, 0.0) 5.000 11 1 (1.0, 1.0, 1.0, 0.0) 9.000