Consider the zero-one knapsack instance
with n=6, capacity 22, values (pi) = (27 24 18 23 15 2), and
weights (wi) = (10 9 7 9 6 1).
Let the upper bound for a node be the value of the solution
obtained by continuing on the remainder of the instance with the
greedy algorithm for the continuous knapsack problem. Let the
lower bound for a node be the value of the solution obtained by
continuing on the remainder of the instance with the greedy
algorithm that considers all remaining items in order, including
only those items that fit. Consider the following four control
strategies:
- depth-first search, pruning only when the knapsack
overflows.
- depth-first search, pruning when the upper bound for a
node is no greater than the best solution achieved so far.
- depth-first search, pruning nodes whose upper bound is
no greater than the best lower bound generated so far.
- best-first search, where the estimator is given by the
upper bound, and stopping when the first leaf is removed from the
priority queue.
Do not use in your pruning strageties the fact that all
profits in the instance are integers. Do not prune when an upper
bound equals a lower bound.
- Sketch the tree given by applying the first control strategy
to the given instance, labeling each node with the profit and weight
included so far.
- For each node in the this tree for which an upper
bound is computed in any of the last three control strategies,
label the node with the upper bound.
- For each node in this tree for which a lower bound
is computed in the third control strategy, label the node with the lower
bound.
- Label each node with the order in which it is expanded
(rather than generated, as in Figures 4.31-33 on pages 247-9 of
my text) in each of the four strategies. These labels should
appear on the outside of the nodes; the profits, weights, and bounds
described above should appear inside. Note that leaves are never expanded.
- How many nodes are expanded by each of the control strategies?
- What is the optimal solution to the given instance?