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?