5 (5) 2014 5 8 ( ) (5) 2014 5 8 1 / 60
Gomory Chvátal 2013 ( ) (5) 2014 5 8 2 / 60
3x 1 + 4x 2 x 1,x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z x 2 3x 1 +11x 2 = 66 ( ) 3 4 3x 1 x 2 = 12 ( ) (5) 2014 5 8 3 / 60 x 1
x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 R x 2 ( ) 3 4 ( ) (5) 2014 5 8 4 / 60 x 1
1 2 3 Gomory Chvátal 4 ( ) (5) 2014 5 8 5 / 60
() 3x 1 + 4x 2 x 1,x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z x 2 3x 1 +11x 2 = 66 ( ) 3 4 3x 1 x 2 = 12 ( ) (5) 2014 5 8 6 / 60 x 1
x 2 x 1 ( ) (5) 2014 5 8 7 / 60
x 2 x 1 () ( ) (5) 2014 5 8 8 / 60
x 2 ( ) 3 4 x 1 ( ) (5) 2014 5 8 9 / 60
x 2 ( ) 3 4 x 1 ( ) (5) 2014 5 8 10 / 60
x 2 ( ) 3 4 x 1 3x + 4x x 1,x 2 1 2 3x 1 x 2 12, 2x 1 + 5x 2 30, x 1 5, x 1 0, x 2 0, x 1, x 2 R ( ) (5) 2014 5 8 11 / 60
x 2 ( ) 3 4 x 1 3x + 4x x 1,x 2 1 2 3x 1 x 2 12, 2x 1 + 5x 2 30, x 1 5, x 1 0, x 2 0, x 1, x 2 R ( ) (5) 2014 5 8 12 / 60
x 2 ( ) 3 4 x 1 3x + 4x x 1,x 2 1 2 3x 1 x 2 12, 2x 1 + 5x 2 30, x 1 5, x 1 0, x 2 0, x 1, x 2 R ( ) (5) 2014 5 8 13 / 60
x 2 ( ) 3 4 ( ) (5) 2014 5 8 14 / 60 x 1
(cutting plane) ( ) (5) 2014 5 8 15 / 60
(cutting plane) ( ) (5) 2014 5 8 16 / 60
1 2 3 Gomory Chvátal 4 ( ) (5) 2014 5 8 17 / 60
1 2 (fractional cut) ( ) (5) 2014 5 8 18 / 60
() x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z x 1 0, x 2 0 x 1 Z, x 2 Z () () ( ) (5) 2014 5 8 19 / 60
(1) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z 1 2 3x 1 x 2 12 3x 1 + 11x 2 66 ( ) (5) 2014 5 8 20 / 60
(2) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z 1 10 30x 1 10x 2 120 3x 1 + 11x 2 66 ( ) (5) 2014 5 8 21 / 60
(3) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z 2 30x 1 10x 2 120 3x 1 + 11x 2 66 33x 1 + x 2 186 ( ) (5) 2014 5 8 22 / 60
(4) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z 33 (x 1 1 ) 33x 1 + x 2 186 x 1 + 1 33 x 2 186 33 ( ) (5) 2014 5 8 23 / 60
(5) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z x 1 + 1 33 x 2 186 33 1 x 1 + x 2 186 33 33 ( ) (5) 2014 5 8 24 / 60
(6) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z (186/33 = 563) x 1 186 33 186 x 1 33 ( ) (5) 2014 5 8 25 / 60
(7) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z x 1 5 ( ) (5) 2014 5 8 26 / 60
(1) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 R x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1 5, x 1, x 2 R ( ) (5) 2014 5 8 27 / 60
(2) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 R x 2 ( ) 3 4 x ( ) (5) 1 2014 5 8 28 / 60
(3) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1 5, x 1, x 2 R ( ) x 2 ( ) 3 4 x ( ) (5) 1 2014 5 8 29 / 60
1 2 3 ( ) 4 ( ) Gomory Chvátal ( ) (5) 2014 5 8 30 / 60
Gomory Chvátal 1 2 3 Gomory Chvátal 4 ( ) (5) 2014 5 8 31 / 60
Gomory Chvátal 1 2 Gomory Chvátal ( ) ( ) (5) 2014 5 8 32 / 60
Gomory Chvátal Ralph Gomory Vašek Chvátal Ralph Gomory (1929 ) Vašek Chvátal (1946 ) ( ) (5) 2014 5 8 33 / 60
Gomory Chvátal Gomory Chvátal x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 Z x 2 3x 1 +11x 2 = 66 ( ) 3 4 3x 1 x 2 = 12 x 1 ( ) (5) 2014 5 8 34 / 60
Gomory Chvátal Gomory Chvátal 1 (1) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 0, x 2 0, x 1, x 2 R x 2 ( ) 3 4 ( ) (5) 2014 5 8 35 / 60 x 1
Gomory Chvátal Gomory Chvátal 1 (2) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1, x 2, s 1, s 2 0 s 2 = 0 x 2 ( ) 3 4 x 1 = 0 s 1 = 0 x 2 = 0 x 1, x 2 Z s 1, s 2 Z x 1 ( ) (5) 2014 5 8 36 / 60
Gomory Chvátal Gomory Chvátal 1 (3) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1, x 2, s 1, s 2 0 s 2 = 0 x 2 ( ) 3 4 x 1 = 0 s 1 = 0 x 2 = 0 x 1 = 11 2, x 2 = 9 2, s 1 = 0, s 2 = 0 2 () x 1 ( ) (5) 2014 5 8 37 / 60
Gomory Chvátal Gomory Chvátal 1 (4) Gomory Chvátal 0 ( ) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1, x 2, s 1, s 2 0 x 1 s 1, s 2 1 11 33x 1 11x 2 + 11s 1 = 132 2 3x 1 + 11x 2 + s 2 = 66 36x 1 + 11s 1 + s 2 = 198 x 1 = 11 2 11 36 s 1 1 36 s 2 ( ) (5) 2014 5 8 38 / 60
Gomory Chvátal ( ) (5) 2014 5 8 39 / 60 Gomory Chvátal 1 (5) x 1 + x 1 + 11 36 s 1 + 1 11 1 s 1 + 36 36 x 1 = 11 2 11 36 s 1 1 36 s 2 36 s 2 = 11 2 s 2 11 2 x 1 11 2 x 1 x 1 5 11 2
Gomory Chvátal Gomory Chvátal 2 (1) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 5, x 1 0, x 2 0, x 1, x 2 R s 2 = 0 s x 3 = 0 2 ( ) 3 4 x 1 = 0 s 1 = 0 x 2 = 0 ( ) (5) 2014 5 8 40 / 60 x 1
Gomory Chvátal Gomory Chvátal 2 (2) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1 + s 3 = 5, x 1, x 2, s 1, s 2, s 3 0 s 2 = 0 s x 3 = 0 2 ( ) 3 4 x 1 = 0 s 1 = 0 x 2 = 0 x 1 x 1, x 2 Z s 1, s 2, s 3 Z ( ) (5) 2014 5 8 41 / 60
Gomory Chvátal Gomory Chvátal 2 (3) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1 + s 3 = 5, x 1, x 2, s 1, s 2, s 3 0 s 2 = 0 s x 3 = 0 2 ( ) 3 4 x 1 = 0 s 1 = 0 x 2 = 0 x 1 x 1 = 5, x 2 = 51 11, s 1 = 18 11, s 2 = 0, s 3 = 0 x 2 s 2, s 3 ( ) (5) 2014 5 8 42 / 60
Gomory Chvátal Gomory Chvátal 2 (4) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1 + s 3 = 5, x 1, x 2, s 1, s 2, s 3 0 2 11x 2 = 66 3x 1 s 2 3 11x 2 = 66 3(5 s 3 ) s 2 = 51 s 2 + 3s 3 x 2 = 51 11 1 11 s 2 + 3 11 s 3 x 2 + 1 11 s 2 3 11 s 3 = 51 11 ( ) (5) 2014 5 8 43 / 60
Gomory Chvátal Gomory Chvátal 2 (5) x 2 + 1 11 s 2 3 11 s 3 = 51 11 1 x 2 + s 2 + 3 s 3 51 11 11 11 x 2 s 3 51 11 51 x 2 s 3 11 x 2 s 3 4 ( ) (5) 2014 5 8 44 / 60
Gomory Chvátal Gomory Chvátal 2 (6) x 2 s 3 4 x 2 (5 x 1 ) 4 x 1 + x 2 9 x 1 + s 3 = 5 ( ) (5) 2014 5 8 45 / 60
Gomory Chvátal Gomory Chvátal 3 (1) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 5, x 1 + x 2 9, x 1 0, x 2 0, x 1, x 2 R x 2 s 2 = 0 s 4 = 0 s 3 = 0 ( ) 3 4 x 1 = 0 s 1 = 0 x 2 = 0 ( ) (5) 2014 5 8 46 / 60 x 1
Gomory Chvátal Gomory Chvátal 3 (2) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1 + s 3 = 5, x 1 + x 2 + s 4 = 9, x 2 s 2 = 0 s 4 = 0 s 3 = 0 ( ) 3 4 x 1 = 0 s 1 = 0 x 2 = 0 x 1, x 2, s 1, s 2, s 3, s 4 0 x 1 x 1, x 2 Z s 1, s 2, s 3, s 4 Z ( ) (5) 2014 5 8 47 / 60
Gomory Chvátal Gomory Chvátal 3 (3) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1 + s 3 = 5, x 1 + x 2 + s 4 = 9, x 2 s 2 = 0 s 4 = 0 s 3 = 0 ( ) 3 4 x 1 = 0 s 1 = 0 x 2 = 0 x 1, x 2, s 1, s 2, s 3, s 4 0 x 1 x 1 = 33 8, x 2 = 39 8, s 1 = 33 8, s 2 = 0, s 3 = 7 8, s 4 = 0 x 2 s 2, s 4 ( ) (5) 2014 5 8 48 / 60
Gomory Chvátal Gomory Chvátal 3 (4) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1 + s 3 = 5, x 1 + x 2 + s 4 = 9, x 1, x 2, s 1, s 2, s 3, s 4 0 2 3x 1 + 11x 2 = 66 s 2 4 3 3x 1 + 3x 2 = 27 3s 4 8x 2 = 39 s 2 + 3s 4 8 x 2 + 1 8 s 2 3 8 s 4 = 39 8 ( ) (5) 2014 5 8 49 / 60
Gomory Chvátal Gomory Chvátal 3 (5) x 2 + x 2 + 1 8 s 2 3 8 s 4 = 39 8 1 s 2 + 3 s 4 39 8 8 8 x 2 s 4 39 8 39 x 2 s 4 8 x 2 s 4 4 ( ) (5) 2014 5 8 50 / 60
Gomory Chvátal Gomory Chvátal 3 (6) x 2 s 4 4 x 2 (9 x 1 x 2 ) 4 x 1 + 2x 2 13 x 1 + x 2 + s 4 = 9 ( ) (5) 2014 5 8 51 / 60
Gomory Chvátal Gomory Chvátal 4 (1) x 1,x 2 3x 1 + 4x 2 3x 1 x 2 12, 3x 1 + 11x 2 66, x 1 5, x 1 + x 2 9, x 1 + 2x 2 13, x 1 0, x 2 0, x 1, x 2 R x 2 s 2 = 0 s 4 = 0 s 3 = 0 ( ) 3 4 x 1 = 0 s 1 = 0 s 5 = 0 x 2 = 0 ( ) (5) 2014 5 8 52 / 60 x 1
Gomory Chvátal Gomory Chvátal 4 (2) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1 + s 3 = 5, x 1 + x 2 + s 4 = 9, x 1 + 2x 2 + s 5 = 13, x 2 s 2 = 0 s 4 = 0 s 3 = 0 ( ) 3 4 x 1 = 0 s 1 = 0 s 5 = 0 x 2 = 0 x 1, x 2, s 1, s 2, s 3, s 4, s 5 0 x 1 x 1, x 2 Z s 1, s 2, s 3, s 4, s 5 Z ( ) (5) 2014 5 8 53 / 60
Gomory Chvátal Gomory Chvátal 4 (3) x,s 3x 1 + 4x 2 3x 1 x 2 + s 1 = 12, 3x 1 + 11x 2 + s 2 = 66, x 1 + s 3 = 5, x 1 + x 2 + s 4 = 9, x 1 + 2x 2 + s 5 = 13, x 2 s 2 = 0 s 4 = 0 s 3 = 0 ( ) 3 4 x 1 = 0 s 1 = 0 s 5 = 0 x 2 = 0 x 1, x 2, s 1, s 2, s 3, s 4, s 5 0 x 1 x 1 = 5, x 2 = 4, s 1 = 1, s 2 = 7, s 3 = 0, s 4 = 0, s 5 = 0 ( ) (5) 2014 5 8 54 / 60
Gomory Chvátal Gomory Chvátal (Gomory 1958, 1963) Gomory Chvátal ( ) Gomory Chvátal ( ) (5) 2014 5 8 55 / 60
Gomory Chvátal 2 ( ) (5) 2014 5 8 56 / 60
1 2 3 Gomory Chvátal 4 ( ) (5) 2014 5 8 57 / 60
Gomory Chvátal ( ) (5) 2014 5 8 58 / 60
( ) (5) 2014 5 8 59 / 60
1 2 3 Gomory Chvátal 4 ( ) (5) 2014 5 8 60 / 60