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

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?