Integer Program Combination Optimization - Duality I | Massachusetts Institute of Technology

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

2023
Views:

158

Pages:

6
Author:

Marissa Travis

1 Outline Slide 1 Duality from lift and project Lagrangean duality 2 Duality from lift and project Slide 2 cx s t Ax = b IP = max Z 0 : : i 2 f0 1g: x x f 2 < ( )= > : min ;c0 xk + 0 (b ; Axk ) k 2K ;0 k 0 k D = maximize min c x + (b ; Ax ) k 2K subject to (c0 ; 0 A)wj 0 2 0 if (c0 ; 0 A)wj < 0 for some j 2 J otherwise: Z Z j J maximize subject to y y + 0 (Axk ; b) c0 xk 0 Awj 0 c0 wj : 4 k j 2 2 K J Slide 13 Dual minimize c0 k 2K X subject to X k k 2K A x + j 2J =1 X k 2K k j k X k k x + k 0 X j 2J 2 k w j w b j K j conv( ) = Pk2K k xk + Pj2J j wj X K j 2 J ! j j ! 2 P J: k 2K k = 1 2 2Z 5 3 15 : x x Z x k ;1 Relax 1 ; 2 ;1 = f(1 0) (2 0) (1 ;1) (2 1) (0 2) (1 2) (2 2) (1 3) (2 3)g ( ) = min(x1 x2 )2X 3 1 ; 2 + (;1 ; 1 + 2 ) 8 ;2 + 0 5 3 < ( )=: 3 ; 2 5 3 3 6;3 3 Z Slide 14 minimize 3x1 ; x2 subject to x1 ; x2 ;x1 + 2x2 3x1 + 2x2 6x1 + x2 x1 ,x2 0 x1 x2 X 0 : 3.4 Example x k j x x : = = : = 5=3, and the optimal value is ZD = Z (5=3) = ;1=3: For corresponding elements of X are (1 0) and (0 2). 5 = 5=3, the () Z 4 2 ; 13 5 3 conv( ) X 2 x 3 IP x x D 2 c LP 1 x 0 1 2 6 1 x