Vanilla BnB on 0/1 knapsack using Python

Question

I am implementing a vanilla BnB algorithm to solve the knapsack 0/1 problem using Python. My problem is that although it seems to work and find the optimal solution in a decent amount of time for n<20 (n being the number of objects) it completely fails to do so for n>=40, it takes forever and takes a high percentage of my CPU. That seems strange to me as a BnB should be faster than a vanilla dynamic programming approach that I coded previously and works fine for n<=200. I need the BnB to get to n=400,1000 and more.

So after debugging a little bit, I think the problem could have two different origins:

• The method I use to calculate the upper bound limit at each node, which to be honest is just a formula I borrowed from a Youtube tutorial that seems to work fine.

• The condition that I coded to stop exploring branches where the space left in the knapsack becomes negative (aka the infeasible solutions) is not correct and I always end up in the worst case scenario with an exponential complexity.

So far, I've not been able to spot my problem.

So here is the code: I know it is not optimal and could be better in many aspects but my priority is to fix the algorithm and then I'll take care of the vector that gives the decision variables.

I hope that somebody will be able to see what I can't see and help me fix my mistake.

thanks for reading.

from collections import namedtuple
import numpy as np
from operator import itemgetter
from queue import Queue

Item = namedtuple("Item", ['index', 'value', 'weight', 'ratio'])

class Node:
    """
    This class represents a Node object accordingly to the 
    representation given in the Coursera lectures of Week 2
    Essentially, each node has 3 attributes:
    - value (current value at the node)
    - room (the space left in the knapsack)
    - optimistic evaluation (what is the value we expect to get at this level)
    I add a level attribute to keep track of how many items are there left to explore.
    """
    def __init__(self,level,value,weight,estimate):
        self.level = level  # Level of the node in the decision tree 
        self.value = value  # value of nodes on the path from root to this node
        self.weight = weight  # Total weight at the node
        self.estimate = estimate  # Optimistic evaluation of the node

def optimistic_estimate(u,n,K,arr):
    """
    This function computes the optimistic estimate
    of the final value we could get at that node
    Args:
        u (Node object): the current node for which to compute the opt estimate
        n (int): number of items in our list
        arr (list): list of all the items available ordered by descending value
        of the value to weight ratio

    Returns:
        bound: the optimistic estimate at this node
    """
    
    # simple case, if the current room left in the node is < 0
    # we return 0 as this is not a solution to our problem and
    # there will be no need of exploring the branch further as 
    # explained in the lectures
    
    if u.level<n-1:
        ub = u.value + (K-u.weight)*arr[u.level+1].value/arr[u.level+1].weight
    else:
        ub = 0
    return ub
      
def solve_it(input_data):

    # parse the input
    lines = input_data.split('\n')

    firstLine = lines[0].split()
    item_count = int(firstLine[0])
    capacity = int(firstLine[1])

    items = []

    for i in range(1, item_count+1):
        line = lines[i]
        parts = line.split()
        r = int(parts[0])/int(parts[1]) # value per unit of weight ratio
        items.append(Item(i-1, int(parts[0]), int(parts[1]),-r))

    # sort items by the value per unit of weight ratio, add the - sign to get the most 
    # valuable item first
    items = sorted(items, key=itemgetter(Item._fields.index('ratio')))
    taken = [0]*len(items)  # vector of decision variables
    value = 0  # initial value of our solution 
    
    # BnB method to solve the problem
    
    # initialization with the root node (level -1 so we can get the 0 index item in the items list
    # when looping over)
    u = Node(-1,0,0,0)
    opt_estimate = optimistic_estimate(u,len(items),capacity,items)
    u.estimate = opt_estimate
    
    q = Queue()
    q.put(u)

    # loop over each node in the BnB tree
    while not q.empty():
        u = q.get()
        
        # treat the case where the node is the root one
        if u.level == -1:
            # initialize the child node
            v = Node(0,0,0,0)
        
        # if the node is a leaf node, skip it
        if u.level == len(items)-1:
            continue
        
        # Calculate the child node that includes the next item 
        v = Node(u.level+1,u.value+items[u.level+1].value,u.weight+items[u.level+1].weight,0)
        v.estimate = optimistic_estimate(v,len(items),capacity,items)
        
        # if the child node's weight is 
        # less than or equal to the knapsack's
        # capacity and its value is greater 
        # than the maximum value found so far,
        # we update the maximum value
        if v.weight<=capacity and v.value>value:
            value=v.value
        
        # use the optimistic evaluation to prune the tree
        # we add the child node to the queue only if the 
        # opt eval is greater than the one found so far
        if v.estimate>value:
            q.put(v)
            
        # compute the child node that does not include the next item
        v = Node(u.level+1,u.value,u.weight,0)
        v.estimate = optimistic_estimate(v,len(items),capacity,items)
        
        if v.estimate > value:
            q.put(v)
    
    # prepare the solution in the specified output format
    output_data = str(value) + ' ' + str(0) + '\n'
    output_data += ' '.join(map(str, taken))
    return output_data