Integer Program Combination Optimization - Solving Relaxations | Massachusetts Institute of Technology

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

2023
Views:

196

Pages:

10
Author:

Raul Mccann

1 Outline The key geometric result behind the ellipsoid method The ellipsoid method for the feasibility problem The ellipsoid method for optimization Problems with exponentially many constraints 2 The Ellipsoid method D is an n n positive de nite symmetric matrix Slide 1 Slide 2 A set E of vectors in b a ' x > a ' xt 1 Slide 3 Key property: We can nd a new ellipsoid Et+1 that covers the halfellipsoid and whose volume is only a fraction of the volume of the previous ellipsoid Et 2.2 Key Theorem Slide 4 E = E (z D) be an ellipsoid in v for some v>0 E0, v V , are a priori known We can make our calculations in in nite precision square roots can be computed exactly in unit time 2.5 Input-Output Slide 6 Slide 7 Input: A matrix A and a vector b that de ne the polyhedron P = fx 2 v A ball E0 = E(x0 r2I ) with volume at most V , such that P E0 Output: A feasible point x 2 P if P is nonempty, or a statement that P is empty 0 � 2.6 The algorithm (Initialization) Let t = 2(n + 1) log(V =v) E0 = E (x0 r2 I ) D0 = r2 I t = 0. 2. (Main iteration) If t = t stop P is empty. If xt 2 P stop P is nonempty. If xt 2= P nd a violated constraint, that is, nd an i such that ai xt < bi . Let Ht = fx 2 a ( )x 0 0 i k i k k i k Hence, P Hk = x 2 v = n n(nU ) ; 5 2 (n+1) ;n Slide 17 2.12 Complexity P = fx 2 0 Given solution (y u z ) is feasible � � � � 8 S � 7 Conclusions Ellipsoid algorithm can characterize the complexity of solving LOPs with an exponential number of constraints For practical purposes use dual simplex Ellipsoid method is an important theoretical development, not a practical one 10 Slide 37