The tree below shows the evolution of a hypothetical Branch and Cut Algorithm 12B solution of a given minimizing, all-binary ILP.

Relaxation solutions are shown next to nodes, and both fixed variables and new cuts are indicated on the branches.

Take nodes in sequence, one by one, and briefly describe what apparently happened and why. Also show the ultimate optimal solution.
Assume that generated cuts are all valid for the original ILP, and that whenever branching or termination occurs, the cut-generation subroutine has concluded that no valid inequality of the family being used can separate the last LP relaxation.

Transcribed Image Text:

(no initial incumbent) add cut 1 e add cut 2 0 (0, 2/5, 1, 2/3, 1, 0) 40 1) (1, 0, 1, 0, 2/3, 1)43 2 (0, 1/3, 1, 1, 1, 1/4) 47 x =1 x2=0 (0, 1, 1, 0, 1, 1, 1/3) 51 3(0, 0, 1, 1, 1, 3/4) 49 6 add cut 4 add cut 3 (0, 1, 1, 0, 4/5, 2/3) 55 (0, 0, 1, 1, 1, 1) 52