Integer Program Combination Optimization - Problem Set 6 - Solutions

Integer Programming & Combinatorial Optimization Solutions to Problem Set 6 1. BW 8.11 We use Algorithm 8.1 to compute an integral generating set for � � S = x ∈ Z4+ : x1 + 2x2 − 3x3 + 5x4 ≤ 2 . A = (1, 2, −3, 5), Initialization: � � T = e1 , e2 , e3 , e4 , b=2 A · T = {1, 2, −3, 5} Main Iteration Round 1: Az y v w z e1 e3 e1 + e3 −2 − ∈ T e2 e3 e2 + e3 −1 − ∈ T 2 − ∈T e4 e3 e3 + e4 T A·T = = � e1 , e2 , e3 , e4 , e1 + e3 , e2 + e3 , e3 + e4 {1, 2, −3, 5, −2, −1, 2} � Round 2: v e1 e1 e2 e3 e4 e4 w Az y z 3 1 3 +e 2e + e −1 − e2 + e3 e1 + e2 + e3 0 − 2 3 2 3 e +e 2e + e 1 − e3 + e4 2e3 + e4 −1 − e1 + e3 e1 + e3 + e4 3 e1 e2 + e3 e2 + e3 + e4 4 e2 e1 T A·T = = � ∈T ∈T ∈T ∈T ∈ /T ∈ /T e1 , e2 , e3 , e4 , e1 + e3 , e2 + e3 , e3 + e4 , 2e1 + e3 , e1 + e2 + e3 , 2e2 + e3 , 2e3 + e4 {1, 2, −3, 5, −2, −1, 2, −1, 0, 1, −1} Round 3: 1 � v e1 e1 e2 e2 e3 e4 e4 1 e + e3 e2 + e3 e3 + e4 e3 + e4 T w z Az y 2e1 + e3 3e1 + e3 0 − 2e3 + e4 e1 + 2e3 + e4 0 − 2e1 + e3 2e1 + e2 + e3 1 e1 2e3 + e4 e2 + 2e3 + e4 1 − 2 3 2 3 2e + e 2e + 2e −6 e3 1 3 1 3 4 2e + e 2e + e + e 4 e1 2e3 + e4 2e3 + 2e4 4 e3 + e4 2 3 1 2 3 2e + e e + 2e + 2e −1 e2 + e3 2e2 + e3 3e2 + 2e3 0 − 1 3 1 3 4 2e + e 2e + 2e + e 1 e1 3 4 3 4 − 2e + e 3e + 2e 1 = ∈T ∈T ∈ /T ∈T ∈ /T ∈ /T ∈ /T ∈ /T ∈T ∈ /T ∈T e1 , e2 , e3 , e4 , e1 + e3 , e2 + e3 , e3 + e4 , 2e1 + e3 , e1 + e2 + e�3 , 2e2 + e3 , 2e3 + e4 , 3e1 + e3 , e1 + 2e3 + e4 , e2 + 2e3 + e4 , 3e2 + 2e3 , 3e3 + 2e4 � Round 4: v e3 e3 1 e + e3 e1 + e3 e2 + e3 e2 + e3 2e1 + e3 2e1 + e3 2e3 + e4 2e3 + e4 w z 3 4 2 + 2e + e e + 3e3 + e4 4 3 3e + 2e 4e3 + 2e4 2 3 4 1 e + 2e + e e + e2 + 3e3 + e4 3e3 + 2e4 e1 + 4e3 + 2e4 2 3 4 2e2 + 3e3 + e4 e + 2e + e 3e3 + 2e4 e2 + 4e3 + 2e4 2 3 4 1 e + 2e + e 2e + e2 + 3e3 + e4 2e1 + 4e3 + 2e4 3e3 + 2e4 e2 + 2e3 + e4 e2 + 4e3 + 2e4 3 4 5e3 + 3e4 3e + 2e e2 Az y 2 e + e3 −2 2e3 + e4 −2 e2 + e3 −1 2e3 + e4 −1 − 0 − 0 0 e1 + e2 + e3 0 e1 + 2e3 + e4 − 0 − 0 ∈T ∈ /T ∈ /T ∈ /T ∈T ∈T ∈ /T ∈ /T ∈T ∈T The new elements z satisfy Az = 0. No further round is required. The integral generating set for S is: � T = e1 , e2 , e3 , e1 + e3 , e2 + e3 , e3 + e4 , 2e1 + e3 , e1 + e2 + e3 , 2e2 + e3 , 2e3 + e4 , 3e1 + e3 , � e1 + 2e3 + e4 , e2 + 2e3 + e4 , 3e2 + 2e3 , 3e3 + 2e4 , 2e2 + 3e3 + e4 , e2 + 4e3 + 2e4 , 5e3 + 3e4 The integral basis is: � e1 , e2 , e3 , e3 + e4 � 2. BW 8.13 2x1 + x2 ≤ 4 −2x1 + x2 ≤ 0 − x2 ≤ 0 �� � � � � � � �0� � � � � �0� 0 −2 (a) 0 : Integral generating set of cone −1 , −2 ∩ Z2 : −12 , −01 , −1 1 , 1 We start with P : ⇒ Add the following constraints: −2x1 + x2 ≤ 0 −x1 ≤ 0 − x2 ≤ 0 �� � � �� �� �� �� �0� 0 (b) 20 : Integral generating set of cone 21 , −1 ∩ Z2 : 12 , 10 , −1 2 ⇒ (c) x2 ≤ 4 ≤ 2 −x2 ≤ 0 2x1 + x1 � 1� : Integral generating set of cone ⇒ 2x1 + x2 ≤ 4 x1 + x2 ≤ 3 x2 ≤ 2 −x1 + x2 ≤ 1 −2x1 + x2 ≤ 0 2 ��−2� �2�� � � � � � � � � �−2� ∩ Z2 : 21 , 11 , 01 , −1 1 , 1 1 , 1 Thus,⎡ the following establish a totally dual integral system describing P: ⎤ set of inequalities ⎡ ⎤ −2 1 0 ⎢ −1 ⎢ 0 ⎥ 0 ⎥ ⎥ ⎢ ⎢ ⎥ ⎢ 0 −1 ⎥ ⎢ 0 ⎥ ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ 2 ⎢ 4 ⎥ 1 ⎥ ⎢ ⎢ ⎥ A=⎢ b = ⎢ 2 ⎥ 0 ⎥ ⎥ ⎢ 1 ⎢ ⎥ ⎥ ⎢ 1 ⎢ 3 ⎥ 1 ⎥ ⎢ ⎢ ⎥ ⎦ ⎣ 0 ⎣ 2 ⎦ 1 −1 1 1 3. BW ⎧ 9.2 max 20x1 ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ s.t. x1 (∗) ⎪ −x1 ⎪ ⎪ ⎪ ⎪ 6x1 ⎪ ⎪ ⎩ x1 � c0 = (20, ⎛ 11) ⎞ 1 1 A0 = ⎝ −1 1 ⎠ 6 2 + 11x2 + + + , x2 ≤ 5 x2 ≤ 0 2x2 ≤ 21 x2 ∈ Z+ ⎛ ⎞ 5 b0 = ⎝ 0 ⎠ 21 (a) Let c1 = (1, 1)� . (a) t = 0 ⎧ ⎫ x1 + x2 ≤ 5 ⎬ ⎨ (b) P 0 = x ∈ R2 : −x1 + 6x2 ≤ 0 ∈ / ∅, since (0, 0) ∈ P 0 ⎩ ⎭ 6x1 + 2x2 ≤ 21 0 x is optimal for : β0 = 79D 43 = max(c0 )� x : x ∈ P 0 and = max(c1 )� x :∈ P 0 , (c0 )� x ≤ β0 . β1 = 5 � � 9 / Z2+ (c) x0 = D 11 4 ,D4 ∈ (d) I = {1, 3} � � 1 1 (e) AI = 6 2 ��1� �2� �3�� ⇒ H = 1 , 1 , 1 is integral generating set for cone (AI ) ∩ Z2 ⎡ ⎤ � 0 � 1 1 A 0 1 ⎣ ⎦ (f) H = 2 1 ⇒ A = H0 3 1 1 b = {5, 0, 21, 5, 7, 10} � � P 1 = x ∈ R 2 : A1 x ≤ b 1 3 (b) P 1 = � ∅, since (0, 0) ∈ P 1 � � x1 = D 73 , D 73 ist optimal for: β0 = 72D 13 = max(c0 )� x : x ∈ P 1 and β1 = 4D 23 = max(c1 )� x : x ∈ P 1 , (c0 )� x ≤ β0 (c) x1 ∈ / Z2 (d) I = {2, 5} � � −1 1 (e) AI = 2 1 ��−1� �0� �1� �2�� is integral generating set for cone (AI ) ∩ Z2 H= 1 , 1 , 1 , 1 � �� � 1 � A −1 0 1 2 2 1 A = (f) H = 1 1 1 1 H1 � b2 = (b1 , 0, 2, 4, 7)� � � P 2 = x ∈ R 2 : A2 x ≤ b 2 (b) P 2 = � ∅ 2 x = (3, 1) is optimal for: β0 = 71 = max(c0 )� x : x ∈ P 2 and β1 = 4 = max(c1 )� x : x ∈ P 2 , (c0 )� x ≤ β0 (c) x2 ∈ Z2+ ⇒ x2 is optimal for (∗) 4. BW 9.9 (a) False. Consider graph G of Figure 2.4 in BW. 2x1 + x2 + x3 + x4 + x5 + x6 ≤ 52 is a valid inequality for P , therefore there exists a supporting hyperplane 2x1 + x2 + x3 + x4 + x5 + x6 = δ of P where δ ≤ 52 . We know in addition that 2x1 + x2 + x3 + x4 + x5 + x6 ≤ 2 is facet defining for P I , and by Theorem A.1, this inequality is essential in the description of P 1 . However, this inequality is not representable as a 0­ 12 combination of the edge inequalities 1 1 and is therefore not in the description of P 2 . Therefore, P 1 �= P 2 . 1 1 (b) Given P 2 ⊇ P i ⊇ P I , we seek to prove P 2 = P I . Consider an odd hole with 2n + 1 nodes and edges, we know xi + xi+1 ≤ 1 ∀i = 1, . . . , 2n x2n+1 + x1 ≤ 1 Since 2n+1 � i=1 2n+1 � 1 1 xi ≤ n, (xi + xi+1 ) ≤ (2n + 1) ⇔ 2 2 i=1 � P 1 2 ∗ ⊆P = x∈ 2n+1 R+ | xi + xi+1 ≤ 1, ∀i = 1, . . . , 2n, x2n+1 + x1 ≤ 1, 2n+1 � � xi ≤ n i=1 Assume that P ∗ is not integral, and there exists an arbitrary cost vector c such that the optimal solution maximizing c� x is fractional for some xi . 4 xj = � 0 ⇐⇒ cj > 0, ∀j, else xj can be reduced to zero without violating any in­ equalities. Furthermore, given xi fractional, ci > 0, either xi + xi−1 = 1 or xi + xi+1 = 1 since we can increase xi otherwise. Assuming that xi + xi−1 = 1, xi−1 is also fractional and therefore ci−1 > 0, else xi−1 = 0 and xi is not fractional. We can extend this argument while decreasing i, until we arrive at the condition xi + xi+1 = 1, therefore xi = 21 , ∀i. However, this solution violates the �2n+1 constraint i=1 xi ≤ n. We arrive at a contradiction. 1 Therefore, P ∗ is integral, and P 2 ⊆ P ∗ = P I . 5. BW 10.2 ⎫ max 3x1 − 5x2 + 7x3 ⎪ ⎪ ⎬ s.t. s1 + 3x1 − 5x2 + 7x3 = 1 (∗) s2 + x2 = 3 ⎪ ⎪ ⎭ x1 , x2 , x3 , s1 , s2 ∈ Z+ 1. Step: c1 = 3 > 0 ⇒ Pivot column: Pivot row: Pivot element: column corr. to x1 1. row 3 > 1. x = (0, 0, 0, 1, 3) is solution for (∗) Generate cut from the source ⇒ 3x1 − 5x2 + 7x3 ≤ 1 x1 + �−D 35 �x2 + �D 37 �x3 ≤ �D 31 � x1 − 2x2 + 2x3 ≤ 0 → x1 − 2x2 + 2x3 + s3 = 0 is inserted in (∗), ⎫ ⇒ max 3(2x2 − 2x3 − s3 ) − 5x2 + 7x3 = x2 + x3 − 3s3 ⎪ ⎪ ⎪ ⎪ s.t. s1 + x2 + x3 − 3s3 = 1 ⎬ s2 + x2 = 3 (∗∗) ⎪ ⎪ x1 − 2x2 + 2x3 + s3 = 0 ⎪ ⎪ ⎭ i = 1, 2, 3 xi , si ∈ Z+ 2. Step: c2 = 1 > 0 ⇒ Pivot column: Pivot row: Pivot element: column corr. to x2 1. row 1 y = (0, 0, 0, 1, 3, 0) is solution for (∗∗) ⇒ x2 = 1 − x3 − s1 + 3s3 ⇒ max (1 − x3 − s1 + 3s3 ) + x3 − 3s3 x2 + x3 + s1 − 3s3 s2 − x3 − s1 + 3s3 x1 + 4x3 + 2s1 − 5s3 xi , s i ∈ Z + = = = = 5 1 − s1 1 2 2 i = 1, 2, 3 ⎫ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎭ (∗ ∗ ∗) ⇒ ci ≤ 0 ∀i z = (2, 1, 0, 0, 2, 0) is solution of (∗ ∗ ∗). ⇒ x◦ = (2, 1, 0, 0, 2) is optimal for (∗∗). 6. BW 10.4 maximize � (t − 1)xi − ty i∈S s.t. s1 + � xi − ty = 0 i∈S s2 + � xi = 1 i∈S xi , si ∈ Z+ , By applying Algorithm 10.1, we select an index i ∈ S. Then the first constraint is a pivot row. We introduce an integral basis for the solutions with xi > 0. This means, we replace column i ∈ S with a new column corresponding to the partial solution xi = 1, y = 1. This gives a new system � −x�i − ty maximize i∈S s.t. s1 − � (t − 1)x�i − ty = 0 i∈S s2 + � x�i = 1 i∈S x�i , si ∈ Z+ , For this program we see that the solution s1 = s2 = 0 is optimal. 6