The tree below shows the hypothetical evolution of a Branch and Price Algorithm 13B solution of an all-binary ILP in original variables x1, x2, and x3. Relaxation solutions are shown next to nodes, and both fixed variables and new columns (variables) are identified on the branches.

(a) Is the model minimizing or maximizing?
Explain.

(b) Assuming the process correctly followed Branch and Price Algorithm 13B, take the nodes in numerical order and briefly describe what apparently happened. Also, explain what solution proved optimal and why.

Transcribed Image Text:

(no initial incumbent) 0 (0, 1/2,1) 50 add x4 1 (1,1,0,1) 43 add x5 (0, 2/5, 1, 1, 1) 33 2 (0, 1, 1, 1/3, 0) 40 2=0 add x6 5 (0, 1, 1, 0, 3/4, 1) 46 3 (1,0,1,1,1) 47