15.083 Lecture 8: Duality Theory I

15.083J/6.859J Integer Optimization Lecture 8: Duality I 1 Outline • Duality from lift and project • Lagrangean duality 2 Duality from lift and project • ZIP = max c� x s.t. Ax = b xi ∈ {0, 1}. • {x ∈ n | Ax = b, x ≥ 0} is bounded for all b. • Without of loss of generality xi + xi+n = 1 are included in Ax = b. 2.1 LP1 ZLP1 = max  S⊆N  s.t.  j∈S  j∈S  S⊆N   cj Aj − b wS  wS = 0 ∀ S ⊆ N, wS = 1, wS ≥ 0. Theorem: ZIP = ZLP1 . 2.2 yS = LP2  T :S⊆T wT . ZLP2 = max  j∈N  s.t. cj y{j}  j∈S   j∈N  Aj − b yS + j ∈S /  Aj − b  yN = 0, yS ≥ 0, y∅ = 1. Theorem: ZLP1 = ZLP2 . 1 Aj yS∪{j} = 0, ∀ S ⊆ N, 2.3 Lift-Project • Inequality form:  j∈N A j xj ≤ b • Multiply constraints with  Aj j∈S • Define yS =  i∈S   i∈S xi for all S ⊆ N to obtain using x2i = xi : xi + i∈S  Aj j ∈S /  xi . i∈S   Aj − b yS +  Aj yS∪{j} ≤ 0. j ∈S / The dual problem min s.t. u∅ b u{j}(Aj − b) + u∅ Aj ≥ cj ∀ j ∈ N, uS  Aj − b j∈S 2.5 i∈S∪{j} xi ≤ b xi , noting that yS ≥ 0 and setting y∅ = 1 j∈S 2.4  +  uS\{j} Aj ≥ 0 ∀ S ⊆ N, |S| ≥ 2. j∈S Strong Duality Suppose that the only feasible solution to Ax = 0, x ≥ 0 is the vector 0. • (Weak duality) If x is a feasible solution to the primal problem and u is a feasible solution to the dual problem, then c x ≤ u∅ b. • (Strong duality) If the primal problem has an optimal solution, so does its dual problem, and the respective optimal costs are equal. 2.6 Complementary slackness x and u feasible solutions for primal and dual. Then, x and u are optimal solutions if and only if  uS  u{j} (Aj − b) + u∅ Aj − cj xj = 0 ∀ j ∈ N,  j∈S Aj − b +  uS\{j} Aj j∈S  j∈S 2 xj = 0 ∀ S ⊆ N, |S| ≥ 2. 2.7 Example maximize x1 + 2x2 + 3x3 + 5x4 subject to 3x1 + 5x2 + 7x3 + 9x4 = 12, xi ∈ {0.1}, i = 1, 2, 3, 4. Dual minimize subject to 12u∅ −9u1 + 3u∅ ≥1 −7u2 + 5u∅ ≥2 −5u3 + 7u∅ ≥3 −3u4 + 9u∅ ≥5 −4u1,2 + 5u1 + 3u2 ≥0 −2u1,3 + 7u1 + 3u3 ≥0 0u1,4 + 9u1 + 3u4 ≥0 0u2,3 + 7u2 + 5u3 ≥0 2u2,4 + 9u2 + 5u4 ≥0 4u3,4 + 9u3 + 7u4 ≥0 3u1,2,3 + 7u1,2 + 5u1,3 + 3u2,3 ≥0 5u1,2,4 + 9u1,2 + 5u1,4 + 3u2,4 ≥0 7u1,3,4 + 9u1,3 + 7u1,4 + 3u3,4 ≥0 9u2,3,4 + 9u2,3 + 7u2,4 + 5u3,4 ≥0 12u1,2,3,4 + 9u1,2,3 + 7u1,2,4 + 5u1,3,4 + 3u2,3,4 ≥ 0. Optimal solution u∅ = 1 1 1 5 7 , u1 = , u4 = − , u2,4 = , u3,4 = 2 18 6 12 24 Complementary slackness condition: x1 = 1, x2 = x3 = 0 and x4 = 1, the dual constraints associated with the subsets S = {1}, {4}, {1, 4} −9u1 + 3u∅ ≥1 −3u4 + 9u∅ ≥5 0u1,4 + 9u1 + 3u4 ≥0 are all satisfied with equality. 3 Lagrangean duality ZIP = min s.t. c x Ax ≥ b (∗) Dx ≥ d x ∈ Zn, X = {x ∈ Z n | Dx ≥ d}. 3 Let λ ≥ 0. c x + λ (b − Ax) Z(λ) = min x ∈ X, s.t. 3.1 Weak duality • If problem (*) has an optimal solution, then Z(λ) ≤ ZIP for λ ≥ 0. • The function Z(λ) is concave. • Lagrangean dual ZD = max s.t. Z(λ) λ ≥ 0. • ZD ≤ ZIP . 3.2 Characterization ZD = min c� x s.t. Ax ≥ b x ∈ conv(X). 3.3 Proof outline • Z(λ) = min x∈X c x + λ (b − Ax) . c x + λ (b − Ax) . • Z(λ) = minx∈conv(X) c x + λ (b − Ax) . • ZD = max min λ≥0 x ∈conv(X) • Let xk , k ∈ K, and w j , j ∈ J, be the extreme points and a extreme rays of conv(X) Z(λ) = ⎧ −∞, ⎪ ⎨ if (c − λ A)w j < 0, ⎪ ⎩ min c xk + λ (b − Axk ) , k∈K ZD = maximize • subject to for some j ∈ J, otherwise. min c xk + λ (b − Axk ) k∈K (c − λ A)w j ≥ 0, j ∈ J, λ ≥ 0, • maximize y subject to y + λ (Axk − b) ≤ c xk ,  λ Aw j  j ≤ cw , λ ≥ 0. 4 k ∈ K, j ∈ J,  Dual minimize subject to • c    αk xk + k∈K  βj w j j∈J αk = 1 k∈K  A  αk xk + k∈K  • conv(X) = k∈K  k βj w j ≥b j∈J αk , βj ≥ 0,   αk x + k ∈ K, j ∈ J.     β w  α = 1, αk , βj ≥ 0, k ∈ j∈J j k∈K k j K, j ∈ J . 3.4 Example minimize 3x1 − subject to x1 − x2 x2 ≥ −1 −x1 + 2x2 ≤ 5 3x1 + 2x2 ≥ 3 6x1 + x2 ≤ 15 x1 ,x2 ≥ 0 x1 , x2 ∈ Z. • Relax x1 − x2 ≥ −1 • X = {(1, 0), (2, 0), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2), (1, 3), (2, 3)} . • Z(λ) = min(x1 ,x2 )∈X 3x1 − x2 + λ(−1 − x1 + x2 ) , • Z(λ) = ⎧ ⎨ −2 + λ, ⎩ 0 ≤ λ ≤ 5/3, 3 − 2λ, 5/3 ≤ λ ≤ 3, 6 − 3λ, λ ≥ 3. • λ∗ = 5/3, and the optimal value is ZD = Z(5/3) = −1/3. For λ = 5/3, the corresponding elements of X are (1, 0) and (0, 2). 5 Z(λ) 4 2 − 31 λ 5 3 conv(X) x2 3 xIP xD 2 c xLP 1 0 1 2 6 x1