\Opgave 11

Constraints

  (a) 4 x1 +   x2 <= 28
  (b)   x1 + 4 x2 <= 27
  (c)   x1 -   x2 <=  1
  (d)   x1        >=  0
  (e)          x2 >=  0

By drawing the set, one can find the following facets

  (0)   x1        >=  0
               x2 >=  0
  (1)   x1 -   x2 <=  1
  (2)   x1        <=  5
  (3)          x2 <=  6
  (4)   x1 + 2 x2 <= 15

To obtain the facets as chvatal-gomory cuts we use

  (0) follows from (d) (e)

  (1) follows from (c)

  (2) (a) + (c) and divide by 5.

  (3) (b) - (d) and divide by 4.

  (4) (b) + 3 (2) gives

        x1 + 4 x2 <= 27
      3 x1        <= 15
      -----------------
      4 x1 + 4 x2 <= 42

      divide by 4 and round gives
 
  (*)   x1 +   x2 <= 10  

      Now take (b) + 2 (*) 

        x1 + 4 x2 <= 27
      2 x1 + 2 x2 <= 20  
      -----------------
      3 x1 + 6 x2 <= 47

      divide by 3 and round gives

        x1 + 2 x2 <= 15