Making a branch-and-bound algorithm more efficient for a large input

Question

I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the Coursera discrete optimisation course).

I tried implementing dynamic programming first, and that worked fine, but ran into memory issues with larger datasets, so I decided to try branch-and-bound.

My implementation works well for small datasets, but when I try and scale it, it hangs up like the DP algorithm, but I can't tell if it is because it is very slow or space inefficient.

The way I have implemented it is as follows (in bad pseudocode)

initialise global best value as 0
initialise taken list and leave list
initialise priority queue
initialise root node with take and leave lists
order items by (value/weight)
calculate upper bound of root
put root node in queue
while queue not empty:
    get queue element with highest priority (highest bound)
    if current node bound < global best:
        end because cant do better
    if current node value > global best:
        update global best
    if current node level < item count
        if weight with new item <= capacity
            create new take list by copying current node take list and setting take[level] = 1
            create new "left" node with new take list and old leave list
        create new leave list by copying current node leave list and setting leave[level] = 1
        create new "right" node with old take list and new leave list         

The node class is:

class node(level, take list, leave list):
    set level as argument
    set lists as argument
    set value by iterating over take list and summing values
    calculate room in bag by capacity - total weight calculated with take list
    set bound by calculating using take and leave lists
    left child = none
    right child = none

My question is: would it be more efficient to calculate the take and leave lists by traversing the tree rather than to explicitly store the lists in each node? I thought it might be quicker to store the lists and just update them with every new node, but I am thinking now that it might run into memory problems with large inputs.

Is it not such a bad thing to have to traverse the tree every time I want to calculate the bound and should I worry more about space issues?

Answer 1

It isn't clear if you are asking about time or memory efficiency. If you care more about memory, then it would be best to traverse the tree. If you care more about time, then it would be best to copy and modify both lists at each node. However, there are more than two alternatives. You could store a single number at each node, which identifies the items in the knapsack. For example, the binary number 10110 would denote the first, third, and fourth objects as being in the knapsack.

I don't want to do your homework for you, and you didn't ask me to, but I also recommend considering a more memory efficient DP approach if you haven't already. Good Luck!