The following tree records solution of a maximizing ILP over x1, x2, x3 = 0 or 1 by branch and cut Algorithm 12B. LP relaxations solutions show next to each node.

Briefly describe the processing, including how and why nodes were branched tightened or terminated, when incumbent solutions were discovered, and what solution proved optimal. Assume that all added inequalities are valid for the original ILP.

Transcribed Image Text:

x =1 0 (0.3, 0.5, 0) 95 4x+3x23 1 (0.375, 0.5, 0) 91 2) (1, 0.2, 0.9) 84 x2+x31 x=0 x3=1 4 (0, 1, 0.6) 78 x3=0 3 5) (0,1,1) 75 6 infeasible solve infeasible