Consider the IP problem given below.
Minimize Summation (i=1 to 4) x_i, subject to
x1 + x2 + x3 >= 1,
x1 + x2 + x4 >= 1,
x1 + x3 + x4 >= 1,
x2 + x3 + x4 >= 1,
x1, x2, x3, x4 belong to {0,1}, and the LP relaxation, which allows 0 <= x_i <= 1, for i = 1,2,3,4. Show that, (x1*,x2*,x3*,x4*) is an optimal solution to the LP relaxation, {please refer to the attachment for complete question}. Solve the IP problem and LP relaxation problem.