Primal-Dual Method Explore a solution (p,d)which is feasible for primal and dual,respectively. -p algorithm's output -d:a lower bound of the optimal solution (recall the weak duality theorem) -Complementary slackness for optimal: ·x(B-∑=1y)=0 ·z（1-y)=0Primal-Dual Method • Explore a solution (𝑝, 𝑑) which is feasible for primal and dual, respectively. – 𝑝 : algorithm’s output – 𝑑 : a lower bound of the optimal solution (recall the weak duality theorem) – Complementary slackness for optimal: • 𝑥 𝐵 − σ𝑗=1 𝑘 𝑦𝑗 = 0 • 𝑧𝑗 1 − 𝑦𝑗 = 0