Consider the integer program: max 2 · y1 3 · y2 (IP) s.t. 9 · y1 9 · y2 ≤ 20 y1 9 · y2 ≤ 13 −y1 ≤ 0 −y2 ≤ 0 y1, y2 : integer. What is the optimal solution to its linear program relaxation? Which of the following are valid cutting planes? Explain.
(a) 2y1 y2 ≤ 3.
(b) 2y1 2y2 ≤ 4.
(c) 2y1 3y2 ≤ 6.