Integer Program Optimization: Problem Set 4 Solutions

Integer Programming & Combinatorial Optimization Solutions to Problem Set 4 1. BW 6.1 � (a) To show : b̃i bj = 0 ∀i �= j. We show by induction: Consider b̃1 , b̃2 � b̃2 = b2 − µ21 b̃1 = b2 − � � b̃2 b̃1 = b2 b̃1 − � = b2 b̃1 − b2 b̃1 · b̃1 ||b̃1 ||2 � b2 ˜b1 1� b̃1 · b̃ 1 2 ˜ �b � � b2 ˜b1 �b̃1 �2 1 �b̃ �2 = 0 Assuming that � b̃i b̃j = 0, we want to show that ∀i, j ∈ {1, . . . , k − 1} , i �= j � � b̃k b̃j b̃k b̃j = 0 ∀j = 1, . . . , k − 1 � � k−1 � bk� ·˜bi i� � k = b − · b̃ · b̃j ||˜bi ||2 � bk b̃j = − i=1 k−1 � i=1 � bk ·˜bi · 2 ||˜bi ||8 < : k� = b b̃j − � bk ˜bj ||˜bj ||2 � i j b̃���� b̃ 0 , i= � j ||b̃j ||2 , i = j · ||b˜j ||2 = 0 (b) To show: � k M = n x∈R :x= k � � i λi b , λ ∈ R k i=1 � = n x∈R :x= k � i=1 We show by induction: 1 � ˜i µi b , µ ∈ R k = Nk Start of induction: b1 = b̃1 k = 1, ⇒ x = λ1 b1 = λ1 b̃1 ⇒ M 1 = N 1 N k−1 = M k−1 , Hypothesis of induction: x ∈ N, x = = k � µi b̃i = i=1 k� −1 k� −1 µi b̃i + µk b̃k � � k� −1 i k i µi b̃ + µk · b − µki b̃ i=1 i=1 = i=1 k−1 � k � λ k bk ∈ M k (µi − µki )b̃i + µk bk = ���� i=1 �i=1 �� � =λk = k−1 P λi bi ∈M k−1 i=1 using the hypothesis ⇒ (c) To show: det(L) = n � Nk = Mk ||bi || i=1 det(L) = | det(B)| � (det(B))2 = det(B ⎛ B) � b 1 b1 ⎜ = det ⎝ ... � bn b 1 ⎛ 1� 1 b b ⎜ = det ⎝ 0 n � = |bi |2 ⎞ � . . . b1 bn .. ⎟ . ⎠ � n n ... b b ⎞ 0 ⎟ .. ⎠ . � b T bn i=1 ⇒ det(L) = n � ||bi || i=1 (d) To show: ||b̃i || ≤ ||bi || i = 1, . . . , n We show by induction: b̃1 = b1 ⇒ ||b̃1 || ≤ ||b1 || 2 b̃i = bi − i−1 � ⇒ bi = b̃i + j=1 i−1 � i ∈ {2, . . . , n} : µij b̃j µij b̃j j=1 i−1 � ||bi ||2 = ||b̃i + µij ˜bj ||2 j=1 = ||bi ||2 � + 2b̃i · i−1 � µij ˜bj + || j=1 = ||b̃i ||2 + 2 i−1 � j=1 i−1 � µij b̃j ||2 j=1 � i j µij b̃���� b̃ + || =0 � i−1 � µij b̃j ||2 j=1 �� ≥0 � ≥ ||b̃i ||2 ⇒ ||b̃i || ≤ ||bi || 2. BW 6.3 Lattices in one dimension Let b = {b1 , . . . , bm }. ”L(b) ⊆ L(a)”: y ∈ L(b) ⇒ y = λ� b m � = λi bi = i=1 m � λi ∈ Z λi µi a µi ∈ Z i=1 ⇒ y ∈ L(a) ”L(a) ⊆ L(b)”: Since a = gcd(b1 , . . . , bm ), 1 = gcd( ba1 , . . . , bam ). Therefore, ∀k ∈ Z , ∃λi ∈ Z, i = 1, . . . , m s.t. m � i=1 m � λi .( bai ) = k, λ i bi = k a i=1 ⇒ L(a) ∈ L(b) 3. BW 6.11 (Outstanding) 4. BW 6.14 ”E ⊆ P ”: It is shown in BW that the problem (6.15) is equivalent to problem (6.13), proving the above statement. ”P ⊆ E � ”: ¯ �∈ E � , then, ∃λ2 x ¯ + (1 − λ2 )d, λ2 ∈ (0, 1) be on Suppose that there exists x ¯ ∈ P such that x 3 the circumference of E � . Therefore, (λ2 (¯ x − d))� D−2 (λ2 (¯ x − d)) = 1 −2 (¯ ) x − d) = 1 x − d)� ( D (¯ λ D(n+1) −2 1 2 � x − d) = ( n+1 ) (¯ x − d) ( λ ) (¯ , d) is a feasible solution in the problem: Hence, ( D(n+1) λ max log | det(D)| s.t. E(D, d) ⊆ P (6.13) D(n+1) log(det(D)) ≥ log(det( )) λ � � (n+1) n = log ( λ ) det(D) = n log( (n+1) λ ) + log det(D) ⇒ log(n + 1) ≤ log λ which is a contradiction since λ ∈ (0, 1) and n ≥ 1. 5. Hands on exercise BW 6.12 Compute a reduced basis of the lattice L = L(b1 , b2 , b3 ) with ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ −10 −2 23 1 ⎠ , b2 = ⎝ 5 ⎠ , b3 = ⎝ −14 ⎠. b1 = ⎝ 71 7 9 To do this, apply the following steps: (a) Compute the GSO of b1 , b2 , b3 . ⎛ ⎞ −10 1 ⎠ b̃1 = b1 = ⎝ 71 1 0 −10 B C ⎛ ⎞ ⎛ ⎞ (−257)B 1 C @ A −2 −10 2 � ˜1 71 ⎝ 1 ⎠ b̃2 = b2 − µ21 b̃1 = b2 − D (b||˜b1)||b2 b̃1 = ⎝ 5 ⎠ − D 0 1 2 −10 71 7 B C B C 1 A @ 71 21 ⎛ ⎛ ⎞ �=µ ⎞ ⎛ ⎞ �� � −10 −2 −844 87 ⎝ 1 ⎝ 1 ⎠ = D 857 4198 ⎠ =⎝ 5 ⎠−D 857 7 71 −178 2 3 � ˜2 3 � ˜1 � b̃3 = b3 − µ3j b̃j = b3 − µ31 b̃1 − µ32˜b2 = b3 − D (b||˜b)1(||b2 ) b̃1 − D (b||˜b)2(||b2 ) b̃2 j=1 0 0 B ⎛ ⎞ 23 = ⎝ −14 ⎠ − D 9 (23,−14,9)B @ 0 B B @ −10 1 71 −10 1 71 1 2 1 C C A ⎛ ⎝ C C A 4 ⎞ −10 1 ⎠−D 71 B B B B (23,−14,9)B B @ 0 B B B B B B @ −D 844 857 D 4198 857 −D 178 857 844 −D 857 D 4198 857 −D 178 857 1 2 C C C C C C A 1 C C C C C C A 844 −D 857 ⎞ ⎜ ⎜ ⎜ D 4198 857 ⎝ −D 178 857 ⎟ ⎟ ⎟ ⎠ ⎛ ⎛ 844 =µ32 −D 857 ⎛ ⎞ � �� � � �� � � � −10 23 39893 ⎜ 395 ⎝ ⎜ 1 ⎠ − −D = ⎝ −14 ⎠ − D ⎜ D 4198 857 5142 10716 ⎝ 71 9 178 −D 857 ⎛ ⎞ =µ31 bi ⎟ ⎟ ⎟ ⎠ for j = i − 1, . . . , 1 (b) Apply algorithm A for i = 2, 3; D 12 , ⎞ bi then set := − �µij �bj i. if |µij | > ii. Compute GSO with multipliers Return b1 , b2 , b3 . � 87 � � < D1 i=2 j=1 |µ21 | = �D 857 � 2 1 � � i=3 j=2 |µ32 | = �−D 39893 10716 > D 2 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ 23 −2 15 b3 := b3 − �µ32 �b2 = ⎝ −14 ⎠ + 4 ⎝ 5 ⎠ = ⎝ 6 ⎠ 9 7 37 ⎛ ⎞ ⎛ ⎞ −10 −844 1 ⎝ 1 2 ⎝ ⎠ 1 4198 ⎠ GSO → b̃ = b̃ = D 857 71 −178 ⎛ ⎞ ⎛ ⎞ −10 15 2483 ⎝ 2 3 ⎝ ⎠ 1 ⎠ − D +2971 6 b̃ = − D 5142 10716 · b̃ 71 37 � 2483 � � i=3 j=1 |µ31 = D 5142 � < D 12 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ −10 −2 15 1 ⎠ b2 = ⎝ 5 ⎠ b3 = ⎝ 6 ⎠ b1 = ⎝ 71 7 37 (c) For i = 1, 2, 3 If ||b̃i+1 + µi+1,i b̃i ||2 < D 34 ||b̃i ||2 , exchange bi and bi+1 , return to (a). ��⎛ ⎞�� �� −2 ��2 � � �� || b̃2 + µ21 b̃1 ||2 = ����⎝ 5 ⎠���� = 78 < D 34 · 5142 = 3856, 5. � �� � �� 7 �� b2 �� ⎛ ⎞��2 �� −10 �� �� �� 1 2 1 ⎠���� = 5142 ||b̃ || = ����⎝ �� 71 �� exchange b1 and b2 . ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ −2 −10 15 1 ⎠ b3 = ⎝ 6 ⎠ b1 = ⎝ 5 ⎠ b2 = ⎝ 7 71 37 compute µij (GSO) 0 1 −2 B C C ⎛ 21 ⎞ ⎛ ⎞ �=µ ⎛ ⎞ ⎛ ⎞ (−10 1 71)B 5 A @ �� � ⎛ −2 ⎞ −2 −10 −2 −10 7 ⎝ 261 ⎝ 1 ⎠−D 5 ⎠=⎝ 5 ⎠= 1 ⎠−D b̃1 = ⎝ 5 ⎠ b̃2 = ⎝ − 0 1 2 39 −2 7 71 7 7 71 B C B C 5 A @ 7 5 ⎛ ⎞ 44 1 ⎝ −422 ⎠ D 13 314 0 ⎞ (15, 6, 15 b̃3 = ⎝ 6 ⎠ − D 37 ⎛ B 37)B @ −2 5 7 1 0 C C A B 37)B @ 78 ⎞ (15, 6, −2 ⎝ 5 ⎠−D 7 ⎛ 0 B 1 B D 13 @ 1 44 C 1 ⎛ ⎞ −422 C A·D 13 44 314 ⎝ −422 ⎠ · D 1 1 2 13 44 314 C C −422 A 314 =µ32 31 ⎞ ⎞ �=µ �� � ⎛ −2 ⎞ � �� � ⎛ 44 31 259 ⎝ 4873 ⎝ 1 5 ⎠−D −422 ⎠ · D 13 = ⎝ −34 ⎠ − D 10716 78 314 −19 7 Algorithm A ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ −10 −2 4 ⎝ 5 ⎠ = ⎝ −34 ⎠ 1 ⎠ − �D 261 i = 2 j = 1 |µ21 | ≈ |6, 69| > D 21 , b2 := ⎝ 39 � 7 22 71 ⎛ ⎞ −2 1 1 ⎝ 5 ⎠ GSO b̃ = b = 7 21 ⎛ ⎞ ⎛ ⎞ �=µ �� � ⎛ −2 ⎞ 4 44 4 2T 1 b b ⎝ −34 ⎠ − D ⎝ 5 ⎠ = D 1 ⎝ −422 ⎠ b̃2 = b2 − D ||b 1 ||2 = 13 13 22 314 7 ⎛ 3T 1 3T ˜2 b b b b 1 2 b̃3 = b3 − D ||b 1 ||2 b − D ˜2 2 b̃ ||b || µ32 31 ⎞ � µ�� ⎛ ⎞ � ⎛ −2 ⎞ � �� � 15 44 259 4873 ⎝ 5 ⎠−D =⎝ 6 ⎠−D D 1 ⎝ −422 ⎠ 78 10716 13 37 314 7 ⎛ |µ32 | ≈ |0, 45| < D 12 |µ31 | ≈ |3, 32| > D 21 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ 15 −2 21 b3 := b3 − �3, 32�b1 = ⎝ 6 ⎠ − 3 ⎝ 5 ⎠ = ⎝ −9 ⎠ 37 7 16 ⎛ ⎞ −2 GSO b̃1 = ⎝ 5 ⎠ 7 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ 4 −2 44 � � ⎝ 5 ⎠ = D 1 ⎝ −422 ⎠ b̃2 = ⎝ −34 ⎠ − D −4 13 13 22 7 314 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ −2 21 44 ⎝ 5 ⎠ − D 4873 D 1 ⎝ −422 ⎠ b̃3 = ⎝ −9 ⎠ − D 25 78 10716 13 16 7 314 ⎛ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎞ −2 4 21 ⎝b1 = ⎝ 5 ⎠ b2 = ⎝ −34 ⎠ b3 = ⎝ −9 ⎠⎠ 7 22 16 i=3 j=2 i=3 j=1 6 (Step 3) i = 1 ||b̃2 + µ21 b̃1 ||2 = ||b2 ||2 = 1656 > D 43 ||b1 ||2 = 58, 5 i = 2 ||b˜3 + µ32˜b2 ||2 = ||b3 − µ31 b̃1 ||2 = 959, 11 < D 34 ||b̃2 ||2 = 1236, 46 → exchange b2 and b3 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ −2 21 −10 1 ⎠ ⇒ b1 = ⎝ 5 ⎠ ; b2 = ⎝ −9 ⎠ ; b3 = ⎝ 7 16 71 ⎛ ⎞ −2 GSO : b̃1 = ⎝ 5 ⎠ 7 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ 21 −2 1688 1 25 ⎝ 5 ⎠ = ⎝ −827 ⎠ · D 78 b̃2 = ⎝ −9 ⎠ − D 78 16 7 1073 ⎛ ⎞ ⎛ ⎞ −10 � � −2 ⎝ 5 ⎠ − D 58476 b̃2 1 ⎠ − D 87 b̃3 = ⎝ 13 60059 71 7 Algorithm A i=2 j=1 |µ21 | ≈ |0, 321| < D 12 i=3 j=2 |µ32 | ≈ |0, 97| > D 21 ⎛ ⎞ −31 ⇒ b3 = b3 − �0, 97�b2 = ⎝ 10 ⎠ 55 ⎛ ⎞ −2 GSO : b̃1 = ⎝ 5 ⎠ 7 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ 21 −2 1688 25 ⎝ 1 ⎝ −827 ⎠ 5 ⎠ = D 78 b̃2 = ⎝ −9 ⎠ − D 76 16 7 1073 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ −31 1688 −2 ⎝ 5 ⎠ − D −1583 D 1 ⎝ −827 ⎠ b̃3 = ⎝ 10 ⎠ − D 497 78 60059 78 55 7 1073 |µ31 | ≈ |6, 37| > D 12 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ −31 −2 −19 ⇒ b3 = b3 − �6, 37�b1 = ⎝ 10 ⎠ − 6 ⎝ 5 ⎠ = ⎝ −20 ⎠ 55 7 13 i=3 j=1 7 ⎛ GSO b̃1 b̃2 b̃3 ⎞ −2 = ⎝ 5 ⎠ 7 ⎛ ⎞ 1688 1 ⎝ −827 ⎠ = D 78 1073 ⎛ ⎞ ⎛ ⎞ −19 −2 29 ⎝ ˜2 5 ⎠ − D −1583 = ⎝ −20 ⎠ − D 78 60059 b 13 7 (Step 3) i=1 ||b̃2 + µ21 b̃1 ||2 = ||b2 ||2 = 778 > D 43 ||b̃1 ||2 = 58, 5 i=2 ||b̃3 + µ32˜b2 ||2 ≈ |919, 21| > D 34 ||b̃2 ||2 ≈ 577, 49 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ −2 21 −19 ⇒ b1 = ⎝ 5 ⎠ b2 = ⎝ −9 ⎠ b3 = ⎝ −20 ⎠ 7 16 13 is a reduced basis of L. 8