I've coded branch and bound to solve the knapsack problem, and use a greedy linear relaxation to find an upper bound on a node I'm currently exploring. What I mean by this is that I first sort the items by their respective value density (computed
value/weight, for each item) and then fill the bag according to a greedy algorithm, using a fraction of the last item that would put us over the bag's capacity. This solution is unattainable (we can't take half an item) but provides an upper bound on the maximum value we can attain from considering an item
def _linear_relaxation(self, j, cp, cw): # we consider how well we can do to increase our current profit (cp) # by looking at items beyond the item that we either just took or left behind weight = cw value = cp for (v, w), index in self.ordered: if index > j: if w + weight <= self.capacity: value += v weight += w else: return value + (v * (self.capacity - w)/float(w)) return value
My code works great to solve small problems using this relaxation, but starts slowing down when the problem size increases. One optimization (or reduction on a node's upper bound) is to avoid taking items of high value density whose weight exceeds the leftover weight we're trying to fill.
Think about it this way: our greedy linear relaxation bound takes items in decreasing order according to their density,
value/weight. If the
residual or remaining weight in the bag is less than the item we're considering adding to the bound, it is much better to take items further down our density list. Consider, for example,
residual = 1,
weight = 2. Wouldn't it be great if we found a small
value, so that we could add to our estimate
value/2, rather than
2 * value? We'd get a much better estimate on the least upper bound than if we considered the last item with the greatest density, with no regard as to its relative effect on our upper bound.
With this in mind, a better bound can be found as follows:
def _linear_relaxation(self, j, cp, cw): weight = cw value = cp for (v, w), index in self.ordered: if index > j: if w + weight <= self.capacity: value += v weight += w else: if w > self.capacity - (w + weight): continue return value + (v * (self.capacity - w)/float(w)) return value
This bound is great for a list of no more than 1000 items (around 11 seconds compared to no solution) but fails on a problem with 10,000 items. My question, how can we we do better? Can the bound be improved on? Or can we more smartly consider what nodes are worth adding, based on the best solution discovered so far.
My question/goal of the review:
To provide some context, the code I've written is included below. Please let me know if you have improvements on its structure (for example, is it better practice to make
TreeNode a truly recursive object and give it
right attributes? Do we gain anything by doing this?). What I'm really looking for, though, is how we can improve the current depth first search implementation (please don't provide a solution that uses a heap, for example, unless you can demonstrate it is an all around better algorithm than what I've written). If you'd like to provide code, that would be great, but I'm really just looking for some ideas on how my current code might be optimized. I'm kind of new to optimization and don't really know where to look for improvements or really how to think about the problem as might a person with a speciality in optimization.
While searching, if we include an item, do we need to recalculate the bound on this node (or would it just be the value of its parent--this solution is still attainable)?
One optimization I should make: put the right node on after putting on the left node. The order in which we consider expanding a path matters, here!
class TreeNode: def __init__(self, level, V, W, taken): self.level = level self.V = V self.W = W self.taken = taken def __str__(self): return str((self.level, self.V, self.W, self.taken)) class KP: def __init__(self, cap, values, weights): self.capacity = cap self.values = values self.weights = weights # sort the items according to their value per weight self.ordered = sorted([((v, w), i) for i, (v, w) in enumerate(zip(self.values, self.weights))], key = lambda tup: float(tup)/tup, reverse = True) # our best initial solution will be the greedy solution def _greedy_solution(self): weight = 0 value = 0 taken =  for (v, w), index in self.ordered: if w + weight <= self.capacity: # take items of highest value per unit weight, while we still can value += v weight += w taken.append(index) else: return TreeNode(index, value, weight, taken) return TreeNode(index, value, weight, taken) def solve(self): best = self._greedy_solution() root = TreeNode(0, 0, 0, ) stack = [root] while len(stack) > 0: current = stack.pop() index = current.level if current.V >= best.V: # consider whether we can immediately improve our best best = current if index < len(self.values): # there are items left to consider # we have two branches to consider: if we have room, we take the item # if we don't have room, we continue our solution to the next iteration # where we consider the next item if current.W + self.weights[index] <= self.capacity: taken = list(current.taken) # update path of items taken taken.append(index) # create the right node right = TreeNode( index + 1, current.V + self.values[index], current.W + self.weights[index], taken ) if right.V > best.V: # update our best, if possible best = right bound = self._linear_relaxation(index, right.V, right.W) # only continue exploring if # we're guaranteed something better if bound >= best.V: stack.append(right) # create the left node, continue # solution of the parent, without # taking the item left = TreeNode( index + 1, current.V, current.W, list(current.taken) ) bound = self._linear_relaxation(index, left.V, left.W) # only continue exploring if # we're guaranteed something better if bound >= best.V: stack.append(left) return best