Construct a branching tree that solves the 0-1 programming problem min{cx | Ax ≥ b} given by min 3x1 + 4x2 6x1 + 2x2 ≥ 3 3x1 + 6x2 ≥ 4 x1, x2 ∈ {0, 1} Branch on x1 first. Recursively define a...

Construct a branching tree that solves the 0-1 programming problem

min{cx | Ax ≥ b} given by

min 3x1 + 4x2

6x1 + 2x2 ≥ 3

3x1 + 6x2 ≥ 4

x1, x2 ∈ {0, 1}

Branch on x1 first. Recursively define a value-bounding function v(b + Δb).

Then write a closed-form expression for v(b + Δb) in terms of Δb that

distinguishes three cases (Δb1, Δb2 ≥ −1; Δb1 ≥ −1 and Δb2 <>

Δb1