labs/branch_and_bound/branch_and_bound_lab_key.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Branch & Bound and Knapsack Lab"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Objectives**\n",
    "- Preform the branch and bound algorithm\n",
    "- Apply branch and bound to the knapsack problem\n",
    "- Understand the geometry of the branch and bound algorithm\n",
    "\n",
    "**Brief description:** In this lab, we will try solving an example of a knapsack problem with the branch-and-bound algorithm. We will also see how adding a cutting plane helps in reducing the computation time and effort of the algorithm. Lastly, we will explore the geometry of the branch and bound algorithm.\n",
    "\n",
    "\n",
    "<font color='blue'> <b>Solutions are shown blue.</b> </font> <br>\n",
    "<font color='red'> <b>Instuctor comments are shown in red.</b> </font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# imports -- don't forget to run this cell\n",
    "from IPython.display import Image\n",
    "import pandas as pd\n",
    "import gilp\n",
    "from gilp.visualize import feasible_integer_pts\n",
    "from ortools.linear_solver import pywraplp as OR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1: Branch and Bound Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that the branch and bound algorithm (in addition to the simplex method) allows us to solve integer programs. Before applying the branch and bound algorithm to the knapsack problem, we will begin by reviewing some core ideas. Furthermore, we will identify a helpful property that will make branch and bound terminate quicker later in the lab!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** What are the different ways a node can be fathomed during the branch and bound algorithm? Describe each.\n",
    "\n",
    "**A:** <font color='blue'> You can fathom by:\n",
    "- integrality: the optimal solution for the node is integral\n",
    "- bound: the optimal value of the node is not better than the current incumbent\n",
    "- infeasibility: the node has no feasible solutions\n",
    "</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Suppose you have a maximization integer program and you solve its linear program relaxation. What does the LP-relaxation optimal value tell you about the IP optimal value? What if it is a minimization problem?\n",
    "\n",
    "**A:** <font color='blue'>The IP optimal value is upper-bounded by the LP-relaxation optimal value in the case of a maximization problem and lower-bounded in the case of a minimization problem.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Assume you have a maximization integer program with all integral coefficents in the objective function. Now, suppose you are running the branch and bound algorithm and come across a node with an optimal value of 44.5. The current incumbent is 44. Can you fathom this node? Why or why not?\n",
    "\n",
    "**A:** <font color='blue'>Yes, you can fathom this node because any node with an integral solution in this node's subtree will have an optimal value $\\leq 44$ since the coefficents of the objective function are integral. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** If the optimal solution to the LP relaxation of the original program is integer, then you have found an optimal solution to your integer program. Explain why this is true.\n",
    "\n",
    "**A:** <font color='blue'> The optimal solution to the LP relaxation is always just as good or better than the optimal integer solution. If the optimal LP solution is integer, that point must be feasible for the IP and so the optimal values of the two are equivalent.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** If the LP is infeasible, then the IP is infeasible. Explain why this is true.\n",
    "\n",
    "**A:** <font color='blue'> The LP is less constrainted than the IP. Hence, adding the additional integrality constraint can not add feasible solutions.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next questions ask about the following branch and bound tree. If the solution was not integral, the fractional $x_i$ that was used to branch is given. If the solution was integral, it is denoted *INT*. In the current iteration of branch and bound, you are looking at the node with the *****."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Image(\"images-lab/part1_bnb_tree.png\", width=500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Can you determine if the integer program this branch and bound tree is for is a minimization or maximixation problem? If so, which is it?\n",
    "\n",
    "**A:** <font color='blue'> Yes, it is a minimization problem because the optimal value is higher when constraints are added. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hint: For **Q7-8**, you can assume integral coefficents in the objective function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Is the current node (marked $z^*$) fathomed? Why or why not? If not, what additional constraints should be imposed for each of the next two nodes?\n",
    "\n",
    "**A:** <font color='blue'>No, the incumbent is 20 and 16.3 is better. The left branch node should have $x_1 \\leq 0$ and the right branch node should have $x_1 \\geq 1$</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Consider the nodes under the current node (where $z = 16.3$). What do you know about the optimal value of these nodes? Why? \n",
    "\n",
    "**A:** <font color='blue'> Their objective value must be $\\geq 16.3$ because adding a constraint can only make the objective value worse and this is a minimization. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: The Knapsack Problem\n",
    "\n",
    "In this lab, you will solve an integer program by branch and bound. The integer program to be solved will be a knapsack problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Knapsack Problem:** We are given a collection of $n$ items, where each item $i = 1,\\dots,n$ has a weight $w_i$ and a value $v_i$. In addition, there is a given capacity $W$, and the aim is to select a maximum value subset of items that has a total weight at most $W$. Note that each item can be brought at most once.\n",
    "\n",
    "\\begin{align*}\n",
    "\\max \\quad & \\sum_{i=1}^n v_ix_i\\\\\n",
    "\\text{s.t.} \\quad & \\sum_{i=1}^n w_ix_i \\leq W \\\\\n",
    "& 0 \\leq x_i \\leq 1, \\text{integer}, i = 1,\\dots,n\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the following data which we import from a CSV file:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = pd.read_csv('data/knapsack_data_1.csv', index_col=0)\n",
    "data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and $W = 18$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Are there any items we can remove from our input to simplify this problem? Why? If so, replace `index` with the item number that can be removed in the code below. Hint: how many of each item could we possibly take?\n",
    "\n",
    "**A:** <font color='blue'> We can not feasibly take any of item 7 so we can remove it from the problem!</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO: uncomment and replace index\n",
    "# data = data.drop(#index)\n",
    "\n",
    "### BEGIN SOLUTION\n",
    "data = data.drop(7)\n",
    "### END SOLUTION"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** If we remove item 7 from the knapsack, it does not change the optimal solution to the integer program. Explain why.\n",
    "\n",
    "**A:** <font color='blue'> In the integer program, item 7 is either in the knapsack or not. However, since $w_7 > W$, it can never be feasibly included.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Consider removing items $i$ such that $w_i > W$ from a knapsack input. How does the LP relaxation's optimal value change?\n",
    "\n",
    "**A:** <font color='blue'> By removing these items, some fractional feasible solutions were removed. Hence, it is possible that the LP relaxation's optimal value got worse.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In **Q10-11**, you should have found that removing these items removes feasible solutions from the linear program  but does not change the integer program. This is desirable as the gap between the optimal IP and LP values can become smaller. By adding this step, branch and bound may terminate sooner. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that a branch and bound node can be fathomed if its bound is no better than the value of the best feasible integer solution found thus far. Hence, it helps to have a good feasible integer solution as quickly as possible (so that we stop needless work). To do this, we can first try to construct a good feasible integer solution by a reasonable heuristic algorithm before starting to run the branch and bound procedure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In designing a heuristic for the knapsack problem, it is helpful to think about the value per unit weight for each item. We compute this value in the table below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data['value per unit weight'] = (data['value'] / data['weight']).round(2)\n",
    "data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Design a reasonable heuristic for the knapsack problem. Note a heuristic aims to find a decent solution to the problem (but is not necessarily optimal).\n",
    "\n",
    "**A:** <font color='blue'>List the items in order (highest to lowest) in terms of value per unit weight. Move down the list taking the item if it fits in the remaining knapsack capacity. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Run your heuristic on the data above to compute a good feasible integer solution. Your heuristic should generate a feasible solution with a value of 64 or better. If it does not, try a different heuristic (or talk to your TA!)\n",
    "\n",
    "**A:** <font color='blue'> First, take item 1. 8 units left. Can't take items 2 or 3. Take item 4. 1 unit left. Can't take items 5,6, or 7. The value of this solution is 64.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will now use the branch and bound algorithm to solve this knapsack problem! First, let us define a mathematical model for the linear relaxation of the knapsack problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Complete the model below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def knapsack(items, capacity, integer = False):\n",
    "    \"\"\"Model for solving the Knapsack problem.\n",
    "    \n",
    "    Args:\n",
    "        items (pd.DataFrame): A table indexd by items with a column for value and weight\n",
    "        capcity (int): An integer-capacity for the knapsack\n",
    "        integer (bool): True if the variables should be integer. False otherwise.\n",
    "    \"\"\"\n",
    "    ITEMS = list(items.index)        # set of items\n",
    "    v = items.to_dict()['value']     # value for each item \n",
    "    w = items.to_dict()['weight']    # weight for each item\n",
    "    W = capacity                     # capacity of the knapsack\n",
    "    \n",
    "    # define model\n",
    "    m = OR.Solver('knapsack', OR.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
    "    \n",
    "    # decision variables\n",
    "    x = {}    \n",
    "    for i in ITEMS:\n",
    "        if integer:\n",
    "            x[i] = m.IntVar(0, 1, 'x_%d' % (i)) \n",
    "        else:\n",
    "            x[i] = m.NumVar(0, 1, 'x_%d' % (i)) \n",
    "        \n",
    "    # define objective function here\n",
    "    m.Maximize(sum(v[i]*x[i] for i in ITEMS))\n",
    "    \n",
    "    # weight must not exceed capacity\n",
    "    # TODO: write this constraint\n",
    "    \n",
    "    ### BEGIN SOLUTION\n",
    "    m.Add(sum(w[i]*x[i] for i in ITEMS) <= W)\n",
    "    ### END SOLUTION\n",
    "    \n",
    "    return m, x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# You do not need to do anything with this cell but make sure you run it!\n",
    "def solve(m):\n",
    "    m.Solve()\n",
    "    print('Solution:')\n",
    "    print('Objective value =', m.Objective().Value())\n",
    "    for var in m.variables():\n",
    "        print(var.name(), ':',  var.solution_value())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now create a linear relaxation of our knapsack problem. Now, `m` represents our model and `x` represents our decision variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m, x = knapsack(data, 18)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can use the next line to solve the model and output the solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solve(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** How does this optimal value compare to the value you found using the heuristic integer solution?\n",
    "\n",
    "**A:** <font color='blue'> This optimal value (70) is greater than the heuristic value (64). </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Should this node be fathomed? If not, what variable should be branched on and what additional constraints should be imposed for each of the next two nodes?\n",
    "\n",
    "\n",
    "**A:** <font color='blue'> The node should not be fathomed. The variable $x_2$ should be branched on because it is fractional. The left branch should have constraint $x_2 \\leq 0$ and the right branch should have constraint $x_2 \\geq 1$. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After constructing the linear relaxation model using `knapsack(data1, 18)` we can add additional constraints. For example, we can add the constraint $x_2 \\leq 0$ and solve it as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m, x = knapsack(data, 18)\n",
    "m.Add(x[2] <= 0)\n",
    "solve(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " **NOTE:** The line `m, x = Knapsack(data1, 18)` resets the model `m` to the LP relaxation. All constraints from branching have to be added each time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Use the following cell to compute the optimal value for the other node you found in **Q16**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TODO: Answer Q17\n",
    "\n",
    "### BEGIN SOLUTION\n",
    "m, x = knapsack(data, 18)\n",
    "m.Add(x[2] >= 1)\n",
    "solve(m)\n",
    "### END SOLUTION"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** What was the optimal value? Can this node be fathomed? Why? (Hint: In **Q13**, you found a feasible integer solution with value 64.)\n",
    "\n",
    "**A:** <font color='blue'> The optimal value was 60. This node can be fathomed because we already have an integer feasible solution with a greater objective value (64)</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we continue running the branch and bound algorithm, we will eventually reach the branch and bound tree below where the $z^*$ indictes the current node we are looking at."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Image(\"images-lab/part2_bnb_tree.png\", width=700)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** The node with $z = 64.857$ was fathomed. Why are we allowed to fathom this node? (Hint: think back to **Q3**)\n",
    "\n",
    "**A:** <font color='blue'> We can fathom this node since the objective function has integral coefficients hence any integral feasible soultion in this branch will have value $\\leq 64$ and will be fathomed by bound.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Finish running branch and bound to find the optimal integer solution. Use a separate cell for each node you solve and indicate if the node was fathomed with a comment. (Hint: Don't forget to include the constraints further up in the branch and bound tree.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Template\n",
    "m, x = knapsack(data, 18)\n",
    "# Add constraints here\n",
    "\n",
    "solve(m)\n",
    "# fathomed?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### BEGIN SOLUTION \n",
    "m, x = knapsack(data, 18)\n",
    "m.Add(x[2] <= 0)\n",
    "m.Add(x[3] <= 0)\n",
    "m.Add(x[4] >= 1)\n",
    "m.Add(x[5] <= 0)\n",
    "m.Add(x[6] <= 0)\n",
    "solve(m)\n",
    "# fathom by bound\n",
    "### END SOLUTION "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### BEGIN SOLUTION \n",
    "m, x = knapsack(data, 18)\n",
    "m.Add(x[2] <= 0)\n",
    "m.Add(x[3] <= 0)\n",
    "m.Add(x[4] >= 1)\n",
    "m.Add(x[5] <= 0)\n",
    "m.Add(x[6] >= 1)\n",
    "solve(m)\n",
    "# fathom by bound\n",
    "### END SOLUTION "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**A:** <font color='blue'> An optimal solution is $x_1 = x_4 = 1$ and $x_i = 0$ otherwise with an optimal value of 64.   </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** How many nodes did you have to explore while running the branch and bound algorithm?\n",
    "\n",
    "**A:** <font color='blue'> 11 nodes were explored. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the next section, we will think about additional constraints we can add to make running branch and bound quicker."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 3: Cutting Planes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In general, a cutting plane is an additional constraint we can add to an integer program's linear relaxation that removes feasible linear solutions but does not remove any integer feasible solutions. This is very useful when  solving integer programs! Recall many of the problems we have learned in class have something we call the \"integrality property\". This is useful because it allows us to ignore the integrality constraint since we are garunteed to reach an integral solution. By cleverly adding cutting planes, we strive to remove feasible linear solutions (without removing any integer feasible solutions) such that the optimal solution to the linear relaxation is integral!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Conisder an integer program whose linear program releaxation is \n",
    "\n",
    "\\begin{align*}\n",
    "\\max \\quad & 2x_1+x_2\\\\\n",
    "\\text{s.t.} \\quad & x_1 + x_2 \\leq 3 \\\\\n",
    "& 2x_1 \\leq 5 \\\\\n",
    "& -x_1 + 2x_2 \\leq 2 \\\\\n",
    "& x_1, x_2 \\geq 0\n",
    "\\end{align*}\n",
    "\n",
    "We can define this linear program and then visualize its feasible region. The integer points have been highlighted."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lp = gilp.LP([[1,1],[2,0],[-1,2]],\n",
    "             [3,5,2],\n",
    "             [2,1])\n",
    "fig = gilp.lp_visual(lp)\n",
    "fig.set_axis_limits([3.5,2])\n",
    "fig.add_trace(feasible_integer_pts(lp, fig))\n",
    "fig"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** List every feasible solution to the integer program.\n",
    "\n",
    "**A:** <font color='blue'> The feasible solutions are: $(0,0), (0,1), (1,0), (1,1), (2,0), (2,1)$ </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Is the constraint $x_2 \\leq 1$ a cutting plane? Why? (Hint: Would any feasible integer points become infeasible? What about feasible linear points?)\n",
    "\n",
    "**A:** <font color='blue'> Yes, it removes feasible solutions to the linear relaxation but no integer feasible solutions.  </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's add this cutting plane to the LP relaxation!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lp = gilp.LP([[1,1],[2,0],[-1,2],[0,1]],\n",
    "             [3,5,2,1],\n",
    "             [2,1])\n",
    "fig = gilp.lp_visual(lp)\n",
    "fig.set_axis_limits([3.5,2])\n",
    "fig.add_trace(feasible_integer_pts(lp, fig))\n",
    "fig"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Is the constraint $x_1 \\leq 3$ a cutting plane? Why?\n",
    "\n",
    "**A:** <font color='blue'> No, it does not remove any feasible solutions. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Can you provide another cutting plane? If so, what is it?\n",
    "\n",
    "**A:** <font color='blue'> Yes, $x_1 \\leq 2$ </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at the feasible region after adding the cutting plane from **Q** and one of the possible answers from **Q25**. Notice the optimal solution to the LP relaxation is now integral!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lp = gilp.LP([[1,1],[2,0],[-1,2],[0,1],[1,0]],\n",
    "             [3,5,2,1,2],\n",
    "             [2,1])\n",
    "fig = gilp.lp_visual(lp)\n",
    "fig.set_axis_limits([3.5,2])\n",
    "fig.add_trace(feasible_integer_pts(lp, fig))\n",
    "fig"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try applying what we know about cutting planes to the knapsack problem! Again, recall our input was $W = 18$ and:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Look at items 1, 2, and 3. How many of these items can we take simultaneously? Can you write a new constraint to capture this? If so, please provide it.\n",
    "\n",
    "**A:** <font color='blue'> We can only take 1 of items 1, 2, and 3 since they take up half the capacity of the knapsack. We can write the constraint $x_1 + x_2 + x_3 \\leq 1$. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Is the constraint you found in **Q26** a cutting plane? If so, provide a feasible solution to the linear program relaxation that is no longer feasible (i.e. a point the constraint *cuts off*).\n",
    "\n",
    "**A:** <font color='blue'> Yes, no integral feasible solutions are cut but the feasible solution $x = (1,\\frac{2}{3}, 0,0,0,0)$ is. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Provide another cutting plane involving items 4,5 and 6 for this integer program. Explain how you derived it.\n",
    "\n",
    "**A:** <font color='blue'> We can only take 2 of the three of them in a feasible integral solution so we can add the constraint $x_4 + x_5 + x_6 \\leq 2$. This is a cutting plane because $x=(0,0,0,1,\\frac{2}{3},1)$ is no longer feasible. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Add the cutting planes from **Q26** and **Q28** to the model and solve it. You should get a solution in which we take items 1 and 4 and $\\frac{1}{6}$ of item 5 with an objective value of 66."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m, x = knapsack(data, 18)\n",
    "# TODO: Add cutting planes here\n",
    "\n",
    "### BEGIN SOLUTION\n",
    "m.Add(x[1] + x[2] + x[3] <= 1)\n",
    "m.Add(x[4] + x[5] + x[6] <= 2)\n",
    "### END SOLUTION\n",
    "\n",
    "solve(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's take a moment to pause and reflect on what we are doing. Recall from **Q9-11** that we dropped item 7 becuase its weight was greater than the capcity of the knapsack. Essentially we added the constraint $x_7 \\leq 0$. This constraint was a cutting plane! It eliminated some linear feasible solutions but no integer ones. By adding these two new cutting planes, we can get branch and bound to terminate earlier yet again! So far, we have generated cutting planes by inspection. However, there are more algorithmic ways to identify them (which we will ignore for now)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we continue running the branch and bound algorithm, we will eventually reach the branch and bound tree below where the $z^*$ indictes the current node we are looking at."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Image(\"images-lab/part3_bnb_tree.png\", width=700)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**NOTE:** Do not forget about the feasible integer solution our heuristic gave us with value 64."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q** Finish running branch and bound to find the optimal integer solution. Use a separate cell for each node you solve and indicate if the node was fathomed with a comment. Hint: Don't forget the cutting plane constraints should be included in every node of the branch and bound tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Template\n",
    "m, x = knapsack(data, 18)\n",
    "# Add constraints here\n",
    "\n",
    "solve(m)\n",
    "# fathomed?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### BEGIN SOLUTION\n",
    "m, x = knapsack(data, 18)\n",
    "m.Add(x[1] + x[2] + x[3] <= 1)\n",
    "m.Add(x[4] + x[5] + x[6] <= 2)\n",
    "m.Add(x[5] >= 1)\n",
    "m.Add(x[4] <= 0)\n",
    "solve(m)\n",
    "# fathom by bound\n",
    "### END SOLUTION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### BEGIN SOLUTION\n",
    "m, x = knapsack(data, 18)\n",
    "m.Add(x[1] + x[2] + x[3] <= 1)\n",
    "m.Add(x[4] + x[5] + x[6] <= 2)\n",
    "m.Add(x[5] >= 1)\n",
    "m.Add(x[4] >= 1)\n",
    "solve(m)\n",
    "# fathom by bound\n",
    "### END SOLUTION"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**A:** <font color='blue'> An optimal solution is $x_1 = x_4 = 1$ and $x_i = 0$ otherwise with an optimal value of 64.   </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Did you find the same optimal solution? How many nodes did you explore? How did this compare to the number you explored previously?\n",
    "\n",
    "**A:** <font color='blue'> Same optimal solution $x = (1,0,0,1,0,0)$ but only took 7 nodes this time compared to the 11 it took with only one cutting plane.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 4: Geometry of Branch and Bound"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Previously, we used the `gilp` package to viusualize the simplex algorithm but it also has the functionality to visualize branch and bound. We will give a quick overview of the tool. Similar to `lp_visual` and `simplex_visual`, the function `bnb_visual` takes an `LP` and returns a visualization. It is assumed that every decision variable is constrained to be integer. Unlike previous visualizations, `bnb_visual` returns a series of figures for each node of the branch and bound tree. Let's look at a small 2D example:\n",
    "\n",
    "\\begin{align*}\n",
    "\\max \\quad & 5x_1+ 8x_2\\\\\n",
    "\\text{s.t.} \\quad & x_1 + x_2 \\leq 6 \\\\\n",
    "& 5x_1 + 9x_2 \\leq 45 \\\\\n",
    "& x_1, x_2 \\geq 0, \\quad \\text{integral}\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = gilp.bnb_visual(gilp.examples.STANDARD_2D_IP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes[0].show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the cells above to generate a figure for each node and view the first node. At first, you will see the LP relaxation on the left and the root of the branch and bound tree on the right. The simplex path and isoprofit slider are also present."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Recall the root of a branch and bound tree is the unaltered LP relaxation. What is the optimal solution? (Hint: Use the objective slider and hover over extreme points).\n",
    "\n",
    "**A:** <font color='blue'> The optimal solution is $x = (2.25, 3.75)$</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Assume that we always choose the variable with the minimum index to branch on if there are multiple options. Write down (in full) each of the LPs we get after branching off the root node.\n",
    "\n",
    "**A:** <font color='blue'> \\begin{align*}\n",
    "\\max \\quad & 5x_1+ 8x_2\\\\\n",
    "\\text{s.t.} \\quad & x_1 + x_2 \\leq 6 \\\\\n",
    "& 5x_1 + 9x_2 \\leq 45 \\\\\n",
    "& x_1 \\leq 2 \\\\\n",
    "& x_1, x_2 \\geq 0\n",
    "\\end{align*}\n",
    "\n",
    "and \n",
    "\n",
    "\\begin{align*}\n",
    "\\max \\quad & 5x_1+ 8x_2\\\\\n",
    "\\text{s.t.} \\quad & x_1 + x_2 \\leq 6 \\\\\n",
    "& 5x_1 + 9x_2 \\leq 45 \\\\\n",
    "& x_1 \\geq 3 \\\\\n",
    "& x_1, x_2 \\geq 0\n",
    "\\end{align*}</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Draw the feasible region to each of the LPs from **Q33** on the same picture.\n",
    "\n",
    "**A:** <font color='blue'> Should look like the result from `nodes[1].show()` </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the following cell to see if the picture you drew in **Q** was correct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes[1].show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The outline of the original LP relaxation is still shown on the left. Now that we have eliminated some of the fractional feasible solutions, we now have 2 feasible regions to consider. The darker one is the feasible region associated with the current node which is also shaded darker in the branch and bound tree. The unexplored nodes in the branch and bound tree are not shaded in."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Which feasible solutions to the LP relaxation are removed by this branch?\n",
    "\n",
    "**A:** <font color='blue'> Those with $2 < x_1 < 3$.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** At the current (dark) node, what constraints will we add? How many feasible regions will the original LP relaxation be broken into?\n",
    "\n",
    "**A:** <font color='blue'> We add the constraints $x_2 \\leq 3$ and $x_2 \\geq 4$. It is divided into 3 feasible regions. </font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes[2].show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** What is the optimal solution at the current (dark) node? Do we have to further explore this branch? Explain.\n",
    "\n",
    "**A:** <font color='blue'> The optimal solution is 34. We do not have to further explore this branch since the optimal solution was integral. Hence, it must be an optimal solution to the IP for this node. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Recall shaded nodes have been explored and the node shaded darker (and feasible region shaded darker) correspond to the current node and its feasible region. Nodes not shaded have not been explored. How many nodes have not yet been explored?\n",
    "\n",
    "**A:** <font color='blue'>2</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** How many nodes have a degree of one in the branch and bound tree? (That is, they are only connected to one edge). These nodes are called leaf nodes. What is the relationship between the leaf nodes and the remaining feasible region?\n",
    "\n",
    "**A:** <font color='blue'>There are 3 leaf nodes and each corresponds to one of the remaining feasible regions. </font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Show the next two iterations of the branch and bound algorithm\n",
    "nodes[3].show()\n",
    "nodes[4].show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** At the current (dark) node, we added the constraint $x_1 \\leq 1$. Why were the fractional solutions $1 < x_1 < 2$ not eliminated for $x_2 <= 3$?\n",
    "\n",
    "**A:** <font color='blue'> Because we were on a node in the branch and bound tree with the constraint $x_2 \\geq 4$ so our branch would not affect fractional solutions associated with a different node in the tree.</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Show the next three iterations of the branch and bound algorithm\n",
    "nodes[5].show()\n",
    "nodes[6].show()\n",
    "nodes[7].show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** What constraints are enforced at the current (dark) node? Why are there no feasible solutions at this node?\n",
    "\n",
    "**A:** <font color='blue'> In addition to the original constraints, we have $x_1 \\leq 2$, $x_2 \\geq 4$, and $x_1 \\geq 2$. No feasible solutions have $x_1 = 2$ and $x_2 \\geq 4$.</font>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes[8].show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Are we done? If so, what nodes are fathomed and what is the optimal solution? Explain.\n",
    "\n",
    "**A:**  <font color='blue'> Yes! In this case, all the nodes were fathomed by integrality with the exception of the one fathomed by infeasibility. The optimal solution is $x = (0,5)$ with the objective value of 40 because it is the best integral solution we found.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at branch and bound visualization for an integer program with 3 decision variables!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes = gilp.bnb_visual(gilp.examples.VARIED_BRANCHING_3D_IP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Look at the first 3 iterations\n",
    "nodes[0].show()\n",
    "nodes[1].show()\n",
    "nodes[2].show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's fast-forward to the final iteration of the branch and bound algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nodes[-1].show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** Consider the feasible region that looks like a rectangular box with one corner point at the origin. What node does it correspond to in the tree? What is the optimal solution at that node?\n",
    "\n",
    "**A:** <font color='blue'>It is the node with the addtional constraints $x_2 \\leq 2$, $x_1 \\leq 1$, $x_3 \\leq 2$ and it has an optimal solution of $x=(1,2,2)$. </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q:** How many branch and bound nodes did we explore? What was the optimal solution? How many branch and bound nodes would we have explored if we knew the value of the optimal solution before starting branch and bound?\n",
    "\n",
    "**A:** <font color='blue'>We explored 13 nodes. The optimal solution was $x = (0,3,1)$ with value 13. Had we known the optimal IP value was 13, we would have only explored 3 nodes.</font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bonus: Branch and Bound for Knapsack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the following example:\n",
    "\n",
    "| item | value | weight\n",
    "|------|-------|-------\n",
    "|  1   |   2   |   1 \n",
    "|  2   |   9   |   3 \n",
    "|  3   |   6   |   2 \n",
    "\n",
    "The linear program formulation will be:\n",
    "\n",
    "\n",
    "\\begin{align*}\n",
    "\\max \\quad & 2x_1+9x_2+6x_3\\\\\n",
    "\\text{s.t.} \\quad & 1x_1+3x_2+2x_3 \\leq 10 \\\\\n",
    "& x_1, x_2, x_3 \\geq 0, \\quad \\text{integer}\n",
    "\\end{align*}\n",
    "\n",
    "In gilp, we can define this lp as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lp = gilp.LP([[1,3,2]],\n",
    "             [10],\n",
    "             [2,9,6])\n",
    "\n",
    "for fig in gilp.bnb_visual(lp):\n",
    "    fig.show()"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}