Q12a

MCQMarks unknown

Consider the following instance of the $0 -1$ Knapsack problem: $\max\; 6X_{1} + 11X_{2} + 16X_{3} + 21X_{4} + 26X_{5}$ Subject to $4X_{1} + 8X_{2} + 12X_{3} + 16X_{4} + 20 X_{5} < 32$ and $X_{i}=0$ or $1$ for $i=1,\dots,5$ . It is required to find all the optimal solutions to this instance using the branch and bound technique.

(A)

State what method you would use to compute bounds on the partial solutions.

(B)

Using a suitable branching technique, generate the entire search tree for this instance of the problem and find all the optimal solutions. Number the nodes in the tree in the order in which they are expanded and for each node show the bound on the partial solutions and the decision which leads to that node.

Loading…