notebooks/knapsack-branch-bound.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Branch and Bound: Knapsack Problem\n",
    "\n",
    "---\n",
    "\n",
    "The **branch and bound** algorithm is a very important technique in combinatorial optimisation and operations research. In this tutorial, we will introduce the **branch and bound** algorithm using an example of the 0-1 knapsack problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 0-1 Knapsack Problem\n",
    "\n",
    "---\n",
    "\n",
    "The **knapsack problem** is a well known combinatorial optimisation problem with many real-world applications such as inventory management, financial portfolio selection and cloud computing. Here we consider its most basic model: 0-1 knapsack problem. The problem is described as follows.\n",
    "\n",
    "Given a set of $N$ items and a knapsack, each item $i$ has a value $v_i$ and a weight $w_i$, and the knapsack has a capacity $Q$. The 0-1 knapsack problem is to select a subset of items to maximise the total value while the total weight of the selected items cannot exceed the knapsack capacity $Q$.\n",
    "\n",
    "The mathematical problem of the knapsack problem is as follows.\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\max \\;\\; & \\sum_{i=1}^{N} v_ix_i, \\\\\n",
    "\\text{subject to:} \\;\\; & \\sum_{i=1}^{N} w_ix_i  \\leq Q, \\\\\n",
    "& x_i = 0 \\text{ or } 1, \\;\\; i = 1, \\dots, N.\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exhaustive Search for Knapsack Problem\n",
    "\n",
    "---\n",
    "\n",
    "Let's consider the following simple knapsack problem with three items and a knapsack capacity of 10.\n",
    "\n",
    "| Item | Value | Weight |\n",
    "| ---- | ----- | ------ |\n",
    "| 1 | 5 |  5  |\n",
    "| 2 | 7 |  8  | \n",
    "| 3 | 6 |  4  | \n",
    "\n",
    "If we simply exhaustive search in the solution space of the knapsack problem, the search tree is as follows. At each time, we further expand the tree by branching an undecided variable $x_i$ to 1 or 0. We can see that the branch [1, 1, ?] is no needed to be expanded, since it is already *infeasible* (the total weight exceeds the capacity). The optimal solution in this case is [1, 0, 1], with total value of 11 and total weight of 9.\n",
    "\n",
    "<img src=\"img/knapsack-exhaustive.png\" width=800></img>\n",
    "\n",
    "From the above search tree, we can see that all the solutions on the right branch of the root are worse than the optimal solution or infeasible. So if we can **early prune** the right branch, we can save a lot of computational effort."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Branch and Bound\n",
    "\n",
    "---\n",
    "\n",
    "The main idea of the **branch and bound** algorithm is to search the solution space with **early pruning** of the useless sub-trees. This way, it can obtain the optimal solution much faster than the exhaustive search.\n",
    "\n",
    "The branch and bound algorithm has two main components: \n",
    "\n",
    "1. **Branching**: This is the same as the exhaustive search. At each step, it expands a node of the tree with branches, each with a possible value of a variable. Each branch is a sub-problem. \n",
    "2. **Bounding**: This is to find the **upper/lower bound** of the optimal solution of a branch/sub-problem based on **optimistic estimate**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bounding by Optimistic Estimate\n",
    "\n",
    "To optimistically estimate the bound of the optimal solution, we can **relax** the constraints of the sub-problem to make it easier to solve. A typical relaxation of combinatorial optimisation is to remove the integer constraints, i.e., the variables can take continuous values. This can convert the problem into a **linear programming** problem, which can be easily solved by algorithms such as the [simplex algorithm](https://en.wikipedia.org/wiki/Simplex_algorithm).\n",
    "\n",
    "By relaxing the integer constraints, the knapsack problem becomes the following problem:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "\\max \\;\\; & \\sum_{i=1}^{N} v_ix_i, \\\\\n",
    "\\text{subject to:} \\;\\; & \\sum_{i=1}^{N} w_ix_i  \\leq Q, \\\\\n",
    "& 0 \\leq x_i \\leq 1, \\;\\; i = 1, \\dots, N.\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "In other words, we can select **a part of** an item, rather than the binary decision of either select or unselect.\n",
    "\n",
    "This relaxed problem can be easily solved to optimality by the follow heuristics.\n",
    "\n",
    "1. Sort the items in the non-increasing order of efficiency, so that $\\frac{v_i}{w_i} \\geq \\frac{v_{i+1}}{w_{i+1}}$.\n",
    "2. Select the items one by one to put into the knapsack.\n",
    "3. If the last item cannot be fully put into the knapsack, we select the part of it to fill in the remaining capacity.\n",
    "\n",
    "For example, given the above three items and capacity of 10:\n",
    "\n",
    "| Item | Value | Weight |\n",
    "| ---- | ----- | ------ |\n",
    "| 1 | 5 |  5  |\n",
    "| 2 | 7 |  8  | \n",
    "| 3 | 6 |  4  | \n",
    "\n",
    "1. We sort the items by efficiency. We have the order [3, 1, 2], since $\\frac{6}{4} > \\frac{5}{5} > \\frac{7}{8}$.\n",
    "2. We select item 3, the total value becomes 6, and the total weight becomes 4.\n",
    "3. We select item 1, the total value becomes 11, and the total weight becomes 9.\n",
    "3. The last item 2 cannot fully fit into the remaining capacity (8 > 10-9). Thus, we select a part of it. The fraction is $\\frac{10-9}{8} = 0.125$. The fractional value is $7 \\times 0.125 = 0.875$. After adding the partial last item, the total value becomes 11.875, and the total weight becomes 10.\n",
    "\n",
    "Finally, we obtain the optimal solution [1, 0.125, 1], with total value of 11.875."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The bounding method of a knapsack (sub-)problem can be implemented as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bounding(values, weights, capacity):\n",
    "    bound = 0\n",
    "    remaining_capacity = capacity\n",
    "    \n",
    "    efficiency = [values[i] / weights[i] for i in range(len(values))]\n",
    "    \n",
    "    sorted_idx = sorted(range(len(efficiency)), reverse=True, key=efficiency.__getitem__)\n",
    "    \n",
    "    for i in sorted_idx:\n",
    "        if weights[i] > remaining_capacity:\n",
    "            fraction = remaining_capacity / weights[i]\n",
    "            frac_value = fraction * values[i]\n",
    "            bound += frac_value\n",
    "            return bound\n",
    "        else:\n",
    "            bound += values[i]\n",
    "            remaining_capacity -= weights[i]\n",
    "    \n",
    "    return bound"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on the above bounding method, the branch and bound algorithm for the knapsack problem can be shown as follows.\n",
    "\n",
    "<img src=\"img/knapsack-bb-dfs.png\" width = 550></img>\n",
    "\n",
    "1. Initially, at the root node, we solve the relaxed problem and obtain its upper bound $V \\leq 11.875$.\n",
    "2. We conduct the **depth-first-search** and visit the left branch first. The left branch is the same as the exhaustive search, and we have found a solution with value of 11 and weight of 9.\n",
    "3. Now we visit the right branch. By solving the corresponding relaxed sub-problem, we obtain the upper bound $V \\leq 9.25$. This means that the **optimal solution of this sub-problem cannot have total value larger than 9.25!** Therefore, we can early prune the right branch, since it can never find a better solution than the current one with value of 11.\n",
    "\n",
    "Compared with the two search trees, we can see that the branch and bound algorithm can be much faster than the exhausitive search."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below shows the Python code for the banch and bound algorithm with depth-first-search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import deque for the stack structure, copy for deep copy nodes\n",
    "from collections import deque\n",
    "import copy\n",
    "\n",
    "def knapsack_bb_dfs(values, weights, capacity):\n",
    "    # Initialise the root, where 'expanded_item' indicates the item to be expanded at this node\n",
    "    root = {\n",
    "        'solution': [0] * len(values),\n",
    "        'value': 0,\n",
    "        'weight': 0,\n",
    "        'expanded_item': 0\n",
    "    }\n",
    "    \n",
    "    # Initially, the fringe contains the root node only\n",
    "    best_solution = root\n",
    "    fringe = deque()\n",
    "    fringe.append(root)\n",
    "    \n",
    "    while len(fringe) > 0:\n",
    "        # Depth-first-search, Last-In-First-Out of the stack\n",
    "        node = fringe.pop()\n",
    "        \n",
    "        # Check if the node is a leaf node\n",
    "        if node['expanded_item'] == len(values):\n",
    "            if node['value'] > best_solution['value']:\n",
    "                best_solution = node\n",
    "                continue\n",
    "        \n",
    "        # Obtain the sub-problem: values, weights, capacity\n",
    "        node_values = values[node['expanded_item']:]\n",
    "        node_weights = weights[node['expanded_item']:]\n",
    "        node_capacity = capacity - node['weight']\n",
    "        \n",
    "        # Bounding on the sub-problem, and then add the value of the current solution\n",
    "        bound = bounding(node_values, node_weights, node_capacity) + node['value']\n",
    "        \n",
    "        # Prune the branch\n",
    "        if bound <= best_solution['value']:\n",
    "            continue\n",
    "            \n",
    "        # Branching on the expanded item, 0 or 1\n",
    "        expanded_item = node['expanded_item']\n",
    "        \n",
    "        # Child 1: unselect the expanded item\n",
    "        child1 = copy.deepcopy(node)\n",
    "        child1['solution'][expanded_item] = 0\n",
    "        child1['expanded_item'] = expanded_item + 1\n",
    "        fringe.append(child1)\n",
    "        \n",
    "        # Child 2: select the expanded item if the capacity is enough\n",
    "        new_weights = node['weight'] + weights[expanded_item]\n",
    "        \n",
    "        if new_weights <= capacity:\n",
    "            child2 = copy.deepcopy(node)\n",
    "            child2['solution'][expanded_item] = 1\n",
    "            child2['value'] = node['value'] + values[expanded_item]\n",
    "            child2['weight'] = new_weights\n",
    "            child2['expanded_item'] = expanded_item + 1\n",
    "            fringe.append(child2)\n",
    "    \n",
    "    return best_solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We apply this algorithm to the above knapsack problem with 3 items and print the obtained optimal solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'solution': [1, 0, 1], 'value': 11, 'weight': 9, 'expanded_item': 3}\n"
     ]
    }
   ],
   "source": [
    "values = [5, 7, 6]\n",
    "weights = [5, 8, 4]\n",
    "capacity = 10\n",
    "\n",
    "print(knapsack_bb_dfs(values, weights, capacity))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Search Strategies\n",
    "\n",
    "---\n",
    "\n",
    "During the branch and bound algorithm, we iteratively apply the **branching** and **bounding** steps. At each iteration, we select a frontier node in the search tree and calculate its bound (**bounding**). If its bound is already worse than the current solution, then we prune it. Otherwise, we expand it and add new branches into the tree (**branching**)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have seen that bounding can greatly speed up the search process due to early pruning. In addition, the order of expanding the nodes can also affect the search efficiency. If we first expand the nodes that are mostly likely to have the optimal solution, then we can prune more branches earlier, and further speed up the process.\n",
    "\n",
    "In terms of the order of expanding nodes, common search strategies include:\n",
    "\n",
    "- Depth-First Search\n",
    "- Breadth-First Search\n",
    "- Best-First Search\n",
    "\n",
    "Branch and bound typically considers **depth-first** search and **best-first** search. The depth-first search can obtain a feasible complete solution as soon as possible to help with the future pruning. The best-first search can expand the most potential nodes first, so it may reach a very good/optimal solution earlier.\n",
    "\n",
    "Unfortunately, no search strategy can guarantee to be the best, and their effectiveness depends on the problem inputs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "---\n",
    "\n",
    "In this tutorial, we introduce how to use the branch and bound method to speed up the exhaustive search process of the knapsack problem. We can see that the branch and bound method can obtain the **optimal** solution much faster than the exhaustive search. \n",
    "\n",
    "However, *the computational complexity of the branch and bound method is still exponential to the problem size.* In other words, branch and bound can still be very slow when the problem size becomes large. In this case, we can use heuristics to obtain near-optimal solutions in a short time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "- More tutorials can be found [here](https://github.com/meiyi1986/tutorials).\n",
    "- [Yi Mei's homepage](https://meiyi1986.github.io/)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "authorship_tag": "ABX9TyMeJhjW6Pj0jBqaT2hJqUdO",
   "name": "ortools-jss.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}