Date: Sun, 2 Dec 2001 19:00:14 -0600 (CST)
From: Mark Jacobson
To: Jimi Hendrix
Subject: Re: branch and bound questions
On Sat, 1 Dec 2001, Jimi Hendrix wrote:
> (1) How do we know what k is in the calculated_Bound() equation?
You take a node out of the priority queue.
It has a cost associated with it. This cost is stored as the value
of one of the fields of the node and it represents the total cost or
weight of all the items you have in the knapsack so far. Let us
refer the level of this node as level i.
Search ahead in the costs or weights array from location i + 1 to
location k (or the end of the array). The k location represents the
first node that exceeds your ability to pay the cost.
Obviously, this loop that advanced the level from i + 1 to k was
keeping the sum of the costs and the profits as it went.
You did not add cost c[k] on to the total cost, cause it exceeds the
budget you have. You also did not add on that last benefit, b[k].
You exit this loop with k value at that point.
What is it you could purchase with the money you have left?
W is your budget or weight limit.
(W - (costUpTo_ith node + costs of nodes on levels i+1 to k-1))
represents the money you have left to spend or the capacity you could
still carry.
Let us call this capacity or money leftToSpend.
b[k]
leftToSpend * ------------ = total benefit or profit you could get
c[k] from buying a FRACTION of the k_th item.
Now you know the theoretical bound that you could obtain and can use
it in the algorithm.
> (2) (in CN1) I assume that "i" in this case is the next_added node before
> its list is updated. Is this correct? Does i then become the level of
> next_added?
> (3) In the calculated_Bound equation (w - total cost up to k) seems to be
> similar to
> (maxcost - costOfAllItemsThatCanBeSelected) in easts question. However, I'm
> not understanding how this this value ever gets divided by
> (costOfPartialItem) as in east's equation.
In East's equation, I believe the denominator got moved over!
See my notes above, move East's denominator over to where it belongs
on your web page and notes, and it will make more sense.
If the benefit to cost ratio of item k is 100 to 20, that would be 5.
Suppose I have W of 100 and spent 90 so far up to item k - 1.
W - 90 is $10 left to spend. Cannot buy this $20 cost item to get its
100 benefit or profit. I only have $10.
Buy with $10 I can purchase at a rate of 5 benefits for each dollar.
I thus have 10 times 5 or 50 benefits or profits to add to my BOUND.
> I'm assuming that k in this is the index of the partial item. It this
> correct, if so how do we know what k is?
Having a loop that first initializes the profits and costs so far for
node i and then loops from i + 1 until k - 1 adding more cost and profit
to the total.
This loop exits when c[k] added to the cost would take you over budget,
i.e. exceed W.
--------
Good luck.
Mark