(C-G : Chvtal-Gomory)

Example 8.1 A Pure 0-1 Set. Consider the 0-1 knapsack set: X={x{0,1}5:3x14x2+2x33x4+x52}. If x2=x4=0, the lhs (left-hand side) =3x1+2x3+x50 and the rhs (right-hand side) =2, which is impossible. So all feasible solutions satisfy the valid inequality x2+x41. If x1=1 and x2=0, the lhs =3+2x33x4+x533=0 and the rhs =2, which is impossible, so x1x2 is also a valid inequality. (i) Derive the inequalities of Example 8.1 as CG inequalities