A binary integer programming problem is expressed as:

Max z = 3x₁ + 2x₂ - 5x₃ - 2x₄ + 3x₅ Subject to x1 + x2 + x3 +2x4 + x5 <= 4 7x1 + 3x3 - 4x4 +3x5 <= 8 11x1 - 6x2 + 3x4 - 3x5 <= 3 x1,...,x5 all take values of either 0 or 1

Suppose now you are in the middle of the Branch-and-Bound solution, and you need to solve the relaxed LP for the case where you have preset and . Again you use the syntax x=linprog(f,A, B, [], [], lb, ub). Which of the following formulations will give you the correct answer?

a) f = [3 2 -5 -2 3]; A =[1 1 1 2 1; 7 3 -4 3; 11 -6 3 -3]; b=[4 8 3]; lb = zeros(3,1); ub=ones(3,1);

b) f = -[3 2 -5 -2 3]; A =[1 1 1 2 1; 7 0 3 -4 3; 11 -6 0 3 -3]; b=[4 8 3]; lb = zeros(5,1); ub= ones(5,1);

c) f = [3 2 -5 -2 3]; A =[1 1 1 2 1; 7 3 -4 3; 11 -6 3 -3]; b=[4 8 3]; lb = zeros(3,1); ub=[1, 0, 1];

d) f = -[3 2 -5 -2 3]; A =[1 1 1 2 1; 7 0 3 -4 3; 11 -6 0 3 -3]; b=[4 8 3]; lb=[1, 0, 0, 0, 0]; ub=[1, 0, 1, 1, 1];

e) You will have to use the syntax x=linprog(f,A, B, Aeq, beq, lb, ub) because Aeq and beq cannot be empty.