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

2023
Views:

457

Pages:

4
Author:

Frederick Austin

1 Outline Slide 1 Minimal counterexample Lift and project 2 Matching polyhedron P = x matching X X(fig) e2 xe e2 (S ) 0 xe xe Slide 2 =1 1 1 e i S 2V V jS j 2E odd jS j 3 : set of perfect matchings in . Theorem: For the perfect matching problem matching = conv( ) F G P F : 2.1 Proof Outline conv(F ) Pmatching : For reverse: Assume G = (V E ) is a graph such that Pmatching 6 conv(F ), and jV j + jE j is the smallest. x be an extreme point of Pmatching not in conv(F ). For each edge e = fu vg, xe > 0, otherwise we could delete e from E . xe < 1, otherwise we could replace V by V n fu v g and E by all edges in E incident to V n fu vg. jE j > jV j otherwise, either G is disconnected (in this case one of the components of G will be a smaller counterexample), or G has a node of degree one (in this case the edge e incident to v satis es xe = 1), or G is the disjoint union of cycles (in this case the theorem holds trivially). x extreme point of Pmatching, there are jE j linearly independent tight constraint. There exists a S V with jS j odd, jS j 3, jV n S j 3, and X e2 (S ) xe = 1: Contract V n S to a single new node u, to obtain G0 = (S fug E 0 ). 0 xe = xe for all e 2 E (S ), and for v 2 S , 0 fuvg x x0 satis es constraints with X = fj2V nSfvjg2Eg respect to G0 . 1 fvjg : x Slide 3 As G is a smallest counterexample, x0 belongs to the convex hull of matchings on G0 , X x0 = M M : 0 0 M0 Contract S to a single new node t we obtain a graph G00 = ((V and a vector x00 : X x00 = M M : n S ) ftg E 00 ) 00 00 M 00 \Glue together" perfect matchings M 0 and M 00 x= X X e2 (S ) M perfect matching: 3 Lift and project = fx 2 Z n j Ax bg (Lift) Multiply Ax b by S M 0 M 00 M \ (S )=feg M xe Slide 4 : and 1 ; xj (Ax)xj bxj () (Ax)(1 ; xj ) b(1 ; xj ) xj and substitute yij = xi xj for i j = 1 : : : n i = 6 j and xj = x2j . Let Lj (P ) be the resulting polyhedron. (Project) Project Lj (P ) back to the x variables by eliminating variables y. Let Pj be the resulting polyhedron, i.e., Pj = (Lj (P ))x . 3.1 Theorem Proof: Pj x0 2 = conv(P \ fx 2 Rn j xj 2 f0 1gg) x and yij0 = x0i xj0 . Since x0j = (x0j )2 and Ax0 b, (x0 y0 ) 2 Lj (P ) and thus x0 2 Pj . Hence, conv(P \ fx 2 Rn j xj 2 f0 1gg) Pj : P \ f 2 Rn j xj 2 f0 1gg If P \ fx 2 Rn j xj = 0g = , then from the Farkas lemma there exists u 0, such that u0 A = ;ej and u0 b = ;1. Thus, for all x satisfying (*) we have u0 Ax(1 ; xj ) u0 b(1 ; xj ): Hence, for all x 2 Pj ;e0j x(1 ; xj ) = ;xj (1 ; xj ) ;(1 ; xj ): Replacing x2j by xj , we obtain that xj 1 is valid for Pj . Since, in addition, Pj P , we conclude that n n Pj P \ fx 2 R j xj = 1g = conv(P \ fx 2 R j xj 2 f0 1gg): 2 Slide 5 Similarly, if P \ fx 2 Rn j xj = 1g = , then Pj conv(P \ fx 2 Rn j xj 2 f0 1gg): Suppose P \ fx 2 Rn j xj = 0g = 6 , P \ fx 2 Rn j xj = 1g 6= . We prove that all valid inequalities for conv(P \ fx 2 Rn j xj 2 f0 1gg) are also valid for Pj . a0 x a valid inequality for conv(P \ fx 2 Rn j xj 2 f0 1gg). x 2 P . If xj = 0, then for all 2 R a0 x + xj = a0 x : If xj > 0, then there exists 0, such that for all x 2 P , a0 x + xj : Analogously, since a0 x is valid for P \ fx 2 Rn j xj = 1g, there exists some 0 such that for all x 2 P , a0 x + (1 ; j ) x : For all x satisfying (*), (1 ; xj )(a0 x + xj ) 0 xj (a x + (1 ; xj )) Hence, a0 x + ( + )( xj (1 ; xj ) xj : ; x2j ) : After setting x2j = xj we obtain that for all x 2 Pj , a0 x , thus all valid inequalities for conv(P \ fx 2 Rn j xj 2 f0 1gg) are also valid for Pj , and thus Pj conv(P \ fx 2 Rn j xj 2 f0 1gg): 3.2 Example P = f(x1 x2 )0 j 2x1 ; x2 0 2x1 + x2 2 x1 0 x2 0g: 2x21 ; x1 x2 0 2x1 (1 ; x1 ) ; x2 (1 ; x1 ) 0 2x21 + x1 x2 2x1 2x1 (1 ; x1 ) + x2 (1 ; x1 ) 2(1 ; x1 ) 2 x1 0 x1 (1 ; x1 ) 0 x2 x1 0 x2 (1 ; x1 ) 0: 3 Slide 6 y = x1 x2 , x12 = x1 2x1 ; y y ;x2 + y 2 ;y x 1 x 0 y 2 ;y x This implies that y = 0, 1 ;x2 x2 x1 x2 x which leads to 1 P 0 0 0 2 ; 2x1 0 0 0 0: 0 0 2 ; 2x1 0 0 = f(x1 x2 )0 j 0 x1 1 x2 = 0g = conv(P \ f(x1 x2 )0 j x1 2 f0 1gg): 3.3 Convex hull Slide 7 = ((Pi1 )i2 : : :)it : Theorem: The polyhedron Pi1 i2 :::it satis es: Pi1 i2 :::it Pi1 :::it 1:::n P = conv(P \ fx 2 Rn j xi 2 f0 1g = PI : 4 i 2 fi1 : : : it gg):