We aim to solve the following integer programming problem (*) :

max x1 +x2 +x3; subject to 2x1 + 2x2 3,

15x1 + 12x3 20 x1,x2,x3 {0,1}.

a) Propose the continuous relaxation (**) of the above problem, and solve it. [6 points]

b) What is the dimension of the set of optimal solution to the relaxation (**)? [6 points]

c) Solve the integer programming (*). [6 points]

**There's a typo in the picture, the min on the second line should be max.

1. We aim to solve the following integer programming problem ) min 1 2 +x3; subject to 2x1 + 2r2