This exercise is designed to guide you through the process of implementing an efficient branch and bound algorithm, specifically tailored to tackle the Knapsack Problem. The term "efficient" here is defined by our ability to keep the search tree as compact as possible, preventing exponential growth with the addition of more items. Although it is not feasible to promise a consistently small search tree, strategic decision-making can significantly mitigate its expansion. Such optimization techniques are fundamental to modern solvers, enabling them to address large-scale problems with remarkable efficiency. While your implementation may not rival the capabilities of these advanced solvers, this exercise aims to deepen your understanding of their underlying mechanics, enhancing your proficiency in utilizing them effectively.
This exercise will be conducted within a Jupyter notebook, providing a dynamic and interactive coding environment. To prepare, install the necessary packages by executing the following command in your terminal:
pip install -r requirements.txtAfter installing the requirements, initiate the notebook by running:
jupyter-lab bnb.ipynbFor those unfamiliar with JupyterLab, a brief introduction is available through this Youtube video, offering insights into its features and functionalities.