A binary integer programming problem is expressed as: Max z = 3x 1 + 2x 2 - 5x 3

Question

A binary integer programming problem is expressed as:

Max z = 3x1 + 2x2 - 5x3 - 2x4 + 3x5
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

To solve it by using branch-and-bound method, you now need to solve a series of relaxed LP problems. You decide to solve them by using MATLAB . For that, you need to define the matrices/vectors , and . Suppose you use the syntax For the original relaxed LP problem, 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=inf(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=inf(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=ones(3,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 = zeros(5,1); ub=ones(5,1);

e) None of the above

Explanation / Answer

Correct answer:

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=inf(5,1);

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.