Integer Program Combination Optimization - Methods to Enhance Formulations II

University:
Massachusetts Institute of Technology
Course:
15.501/516 | Accounting
Academic year:

2023
Views:

170

Pages:

8
Author:

Phaliedeplerey5

1 Outline Slide 1 Polyhedral review Methods to generate valid inequalities Methods to generate facet de ning inequalities 2 Polyhedral review 2.1 Dimension of polyhedra De nition: The vectors x1 xk 2 0. Select a in order for (1) to be still valid, and to dene a facet for S . x2 For x1 = 0, (1) is valid for all a. If x1 = 1, a 2 ; x2 ; x3 ; x4 ; x5 ; x6. Since x1 = 1 implies x2 = = x6 = 0, then a 2. Therefore, if 0 a 2, (1) is valid. For a = 2, f2 4g f2 5g f3 5g f3 6g f4 6g, and f1g satisfy it with equality. 2x1 + x2 + x3 + x4 + x5 + x6 2 is valid and denes a facet conv (S ). 4.2.1 General principle P Suppose S f0 1gn S i = S \ x 2 f0 1gn x1 = i , i = 0 1, and nj�2 aj xj a0 (2) is valid for S 0 . If S 1 = , then x1 0 is valid for S . P 6= , then a1 x1 + nj�2 aj xj a0 (3) is valid for S for any a1 a0 ; Z , If S 1P n a x s.t. x 2 S 1 . Z = j�2 j j If a1 = a0 ; Z and (2) denes a face of dimension k of conv(S 0 ), then (3) gives a face of dimension k + 1 of conv(S ). 4.2.2 Geometry Slide 26 Slide 27 Slide 28 7 x3 a1 x1 + a2 x2 + a3 x3 a0 a2 x2 + a3 x3 a0 x2 x1 4.2.3 Order of lifting = conv fx 2 f0 1g6 j 5 1 + 5 2 + 5 3 + 5 4 + 3 5 + 8 6 17g \ f 5 = 6 = 0g 1 + 2 + 3 + 4 3 is valid for Lifting on 5 and then on 6 , yields 1 + 2 + 3 + 4 + 5 + 6 3. Lifting on 6 and then on 5 , yields 1 + 2 + 3 + 4 + 2 6 3. P x x x x x x x P x x x x x : x x x x x x x x x x x x 8 : x x x Slide 29