The relaxation doesn't lose anything It is easily observed that the LP has the following optimal solution x=0,zi=1,if k<B x=1,z=0,ifk≥B This is the same as the optimal solution to the IP. So the LP relaxation doesn't lose anything. 11
The relaxation doesn’t lose anything ◼ It is easily observed that the LP has the following optimal solution ൝ 𝑥 = 0, 𝑧𝑗 = 1, if 𝑘 < 𝐵 𝑥 = 1, 𝑧𝑗 = 0, if 𝑘 ≥ 𝐵 ◼ This is the same as the optimal solution to the IP. ◼ So the LP relaxation doesn’t lose anything. 11
Dual LP Primal Dual min Bx+f=1zj max =1y s.t. x+2≥1， js.t.=1y≤B j x≥0，z1≥0，j y∈[0,1] j 12
Dual LP Primal min 𝐵𝑥 + σ𝑗=1 𝑘 𝑧𝑗 𝑠.𝑡. 𝑥 + 𝑧𝑗 ≥ 1, ∀𝑗 𝑥 ≥ 0, 𝑧𝑗 ≥ 0, ∀𝑗 12 Dual max σ𝑗=1 𝑘 𝑦𝑗 𝑠.𝑡. σ𝑗=1 𝑘 𝑦𝑗 ≤ 𝐵 ∀𝑗 𝑦𝑗 ∈ [0,1] ∀𝑗