C4W3_33APPROXIMATION_ALGORITHMS_FOR_NP_COMPLETE_PROBLEMS.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# XXXIII. APPROXIMATION ALGORITHMS FOR NP-COMPLETE PROBLEMS \n",
    "\n",
    "### A Greedy Knapsack Heuristic\n",
    "\n",
    "So let's talk through a potentially greedy approach to the knapsack problem. Probably the first idea you'd have would be to consider the items in some order. And when you consider an item, you make an irrevocable decision at that point whether to include it in your solution or not.\n",
    "\n",
    "So the question that is, in what order should you look at the items? Well, what's our objective? Our objective is to maximize the value of our set. So obviously, high value items are important. So maybe the first idea would be to sort the items from highest value to lowest value.\n",
    "\n",
    "But if you think about that proposal for some time, you quickly realize that this is a little naive. This is not the whole story. If you have a high value item that fills up the whole knapsack, it seems like that's not quite as useful if you had an almost as high value item that basically had size close to zero but didn't use up any of the knapsack at all.\n",
    "\n",
    "Remember that each item has two properties, not just its value but also its size, and both of these are important. We want to prefer items that have a lot of value, but we also want to prefer items that are small.\n",
    "\n",
    "So, if you want to take the two parameters of each item, form a single parameter by which we can then sort the jobs, a natural first cut to look at is a ratio.\n",
    "\n",
    "Since we prefer high values, and we prefer low weights, the sensible thing to look at is the ratio of the value of an item divided by its size. And we'll then going to consider items from the highest values of these ratios to the lowest values of these ratios.\n",
    "\n",
    "So now that we have our greedy ordering, we just proceed to the items one at a time, and we pack the items into the knapsack in this ordering. Now, what happens here, and didn't actually trouble us in the scheduling problem, is at some point, we might no longer be able to pack items into the knapsack, the thing might get full. So once that happens, once we've reached an item which doesn't fit in the knapsack given the items that we've already packed into it, we just stop the greedy algorithm.\n",
    "\n",
    "![Greedy Knapsack Algorithm](images/18_greedy_Knapsack_Algorithm.png)\n",
    "\n",
    "\n",
    "eg.  Let's consider the following three item instance.<br>\n",
    "$v_1$ = 2, $w_1$ = 1<br>\n",
    "$v_2$ = 1000, $w_2$ = 1000<br>\n",
    "$W$ = 1000<br>\n",
    "\n",
    "Here the greedy solution is : 2<br>\n",
    "And optimal solution is : 1000\n",
    "\n",
    "Since the knapsack capacity is 1000, and the sum of the sizes of the job is 1001, there is no room for both of them. The greedy algorithm, unfortunately, because the first tiny item has a smaller ratio, will pack in item number one. And that leaves no room for item number two, so the value of the greedy algorithm solution is just two, whereas the optimal solution is of course to just take the second item. Yeah it's ratio is worse, but on the other hand, it fills up the whole knapsack. And so overall, your value is 1000, which obviously blows away the greedy solution.\n",
    "\n",
    "There is, however, a simple fix to address this issue. We're going to add a very simple Step 3 to our greedy heuristic. So the new Step 3 is just going to compare two different candidate solutions and return whichever one is better, which everyone has a bigger total value. The first candidate is just what we were doing before, it's just the output of Step 2 of the algorithm. The second candidate is whichever item by itself has the maximum value.\n",
    "\n",
    "In other words, this new greedy algorithm, it just runs the old one, but then it does a final sanity check. It looks at each item individually, and it says, well, if this item, just by itself, dominates the solution I've computed thus far, I return this single item by itself instead.\n",
    "\n",
    "![Greedy Knapsack Algorithm](images/19_greedy_Knapsack_Algorithm.png)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A : [[2.0, 0], [1.3333333333333333, 1], [1.0, 2]]\n",
      "\n",
      "Max Value of optimal solution: 4\n",
      "Knapsack items: [2, 4]\n",
      "\n",
      "A : [[2.0, 0], [1.0, 1]]\n",
      "\n",
      "Max Value of optimal solution: 1000\n",
      "Knapsack items: 1000\n"
     ]
    }
   ],
   "source": [
    "def knapsack_problem_greedy_heuristic(value, weights, W): \n",
    "    A = [[value[i]/weights[i], i] for i in range(len(value))]\n",
    "    A = sorted(A) \n",
    "    A.reverse()\n",
    "    knapsack = 0\n",
    "    knapsack_items = []\n",
    "    for i in range(len(A)):\n",
    "        wt = weights[A[i][1]]\n",
    "        if knapsack + wt <= W:\n",
    "            knapsack += wt\n",
    "            knapsack_items.append(value[A[i][1]])\n",
    "        else:\n",
    "            break\n",
    "    knapsack_fix = -1\n",
    "    for i in range(len(value)):\n",
    "        if value[i] > knapsack:\n",
    "            if value[i] > knapsack_fix:\n",
    "                knapsack_fix = value[i]  \n",
    "    if knapsack_fix == -1:    \n",
    "        print(\"A : {}\\n\\nMax Value of optimal solution: {}\\nKnapsack items: {}\".format(A, knapsack, knapsack_items))\n",
    "    else:\n",
    "        print(\"A : {}\\n\\nMax Value of optimal solution: {}\\nKnapsack items: {}\".format(A, knapsack_fix, knapsack_fix))\n",
    " \n",
    "\n",
    "#knapsack_problem_greedy_heuristic([1, 2, 5, 6], [2, 3, 4, 5], 8)\n",
    "knapsack_problem_greedy_heuristic([2, 4, 3], [1, 3, 3], 5)\n",
    "print()\n",
    "knapsack_problem_greedy_heuristic([2, 1000], [1, 1000], 1000)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A Dynamic Programming Heuristic for Knapsack\n",
    "\n",
    "![Dynamic Programming Heuristic Knapsack](images/20_DynamicProgrammingHeuristic_Knapsack.png)\n",
    "\n",
    "So here is the algorithm in full detail. It really only has two steps. Fist, we do the transformation. We round the item values to the small integers, then we invoke the second dynamic programming algorithm on the transformed instance. Precisely, here is how we round each item value $v_i$. To begin, we decrease $v_i$ to the nearest multiple of a parameter $m$.\n",
    "\n",
    "![Dynamic Programming Heuristic Knapsack](images/21_DynamicProgrammingHeuristic_Knapsack.png)\n",
    "\n",
    "Let's now wrap things up with the pseudocode of the new dynamic programming algorithm. So A will be our usual table. It has two dimensions, because subproblems are indexed by two parameters, i, the prefix that ranges from 0 to n, and x, the value target that ranges from 0 to, to the maximum imaginable value, let's say n times Vax. So the base case is when i equal 0, that is, you're not allowed to use any items. In this case, we have to fill it in with plus infinity. Well, except if x itself is 0, then the answer is 0. Now, we just populate the table using the recurrence in a double for loop. The structure here is exactly the same as in our first knapsack dynamic programming algorithm. In the first dynamic programming solution that we developed for knapsack, we could return the correct answer in constant time given the filled-in table. That's because of one of the subproblems in that dynamic programming algorithm, literally was the original problem. When i=n and x is equal to the full map sack capacity capital W, the responsibility of that subproblem was to compute the max value solution subject to the capacity capital W using all of the items, that's literally the original problem. By contrast, in this dynamic programming algorithm, none of the subproblems are literally the original problem that we wanted to solve. In this new dynamic programming algorithm, however, none of thesubproblems correspond directly to the original problem that we wanted to solve, none of them tell you the maximum value of a feasible solution. To see why, let's inspect the largest batch of subproblems. When i is equal to n and you can use whatever subset of items that you want. The second index of one of these problems is a target value x. That might be a number, like say 17,231. So after you've run this algorithm and you've filled in the whole table, what do you know in this subproblem? You will have computed the smallest total size of a bunch, bunch of items that has total value at least 17,231. So that's going to be some number, maybe it's 11,298. But, what if your knapsack capacity's only 10,000? Then, this is not a feasible solution, so it doesn't do you any good. Okay, well that's not quite true, it does do you some good. If you know that every single solution that gets value 17,231 or more has size bigger than your knapsack capacity, well then, you know that the optimal solution has to be less than 17,231. There is no feasible way to get a total value that high.\n",
    "\n",
    "Now, you realize that if you knew this information for every single target value x, and you do once you've filled in the entire table, that's sufficient to figure out the optimal solution, figure out the biggest value of a feasible solution. All you need to do is scan through this final batch of subproblems. You begin with the largest conceivable target value x, and then you get less and less ambitious as you keep finding infeasible solutions. So you scan from high target values to low target values and you're looking for the first that is the largest target value x, such that there exists a subset of items meeting that target value whose total size is at most your knapsack capacity. That is going to be the optimal solution, that first target value x, that can be physically met given your knapsack is at capacity. \n",
    "\n",
    "![Dynamic Programming Heuristic Knapsack](images/22_DynamicProgrammingHeuristic_Knapsack_RT.png)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Max Value of optimal solution: 5\n",
      "Max Value of optimal solution: 3\n",
      "Max Value of optimal solution: 0\n",
      "Max Value of optimal solution: 1000\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def knapsack_problem_tabular(v_hat, weights, A, W):\n",
    "    #print(\"v_hat {}, weights {}, W {}\".format(v_hat, weights, W))\n",
    "    r, c = A.shape\n",
    "    for i in range(1, r):\n",
    "        for x in range(c):\n",
    "            #print(\"i: {}, x: {}\".format(i,x))\n",
    "            if A[i-1][x] != None:\n",
    "                aexcluding = A[i-1][x]\n",
    "            if v_hat[i-1] > x :\n",
    "                aincluding = 0 \n",
    "            else:\n",
    "                aincluding = A[i-1][x - v_hat[i-1]] + weights[i-1] \n",
    "            #print(\"aexcluding: {}, aincluding: {}\".format(aexcluding, aincluding))\n",
    "            A[i][x] = min(aexcluding, aincluding)\n",
    "    max_last_row = -1\n",
    "    for i in range(c):\n",
    "        if (A[-1][i] > max_last_row) and (A[-1][i] != float('inf')) and (A[-1][i] <= W):\n",
    "            max_last_row = A[-1][i] \n",
    "    return max_last_row\n",
    "    \n",
    " \n",
    "    \n",
    "def knapsack_problem_dynamic_heuristic(value, weights, W, epsilon): \n",
    "    # value: profit  ,  W: capacity  , epsilon : error\n",
    "    n = len(value)\n",
    "    v_max = max(value)\n",
    "    m = epsilon * v_max / n\n",
    "    if m != 0 :\n",
    "        v_hat = [ int(vi//m) for vi in value]\n",
    "    else:\n",
    "        v_hat = value\n",
    "    A = np.full((n+1, (n*v_max)+1), None)  # max weight\n",
    "    A[0][:] = float('inf')\n",
    "    A[0][0] = 0\n",
    "    max_value = knapsack_problem_tabular(v_hat, weights, A, W)\n",
    "    print(\"Max Value of optimal solution: {}\".format( max_value))\n",
    "    #reconstruction_algorithm(value, weights, A)\n",
    "    \n",
    " \n",
    "\n",
    "\n",
    "knapsack_problem_dynamic_heuristic([1, 2, 5, 6], [2, 3, 4, 5], 8, 1)\n",
    "knapsack_problem_dynamic_heuristic([2, 4, 3], [1, 3, 3], 5, 1)\n",
    "knapsack_problem_dynamic_heuristic([2, 4, 3], [1, 3, 3], 5, 30)\n",
    "knapsack_problem_dynamic_heuristic([2, 1000], [1, 1000], 1000, 1)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Challenge Problem\n",
    "\n",
    "In this problem we will revisit an old friend, the traveling salesman problem (TSP). You will implement a heuristic for the TSP, rather than an exact algorithm, and as a result will be able to handle much larger problem sizes. Here is a data file describing a TSP instance (original source: http://www.math.uwaterloo.ca/tsp/world/bm33708.tsp): nn.txt \n",
    "\n",
    "The first line indicates the number of cities. Each city is a point in the plane, and each subsequent line indicates the x- and y-coordinates of a single city.\n",
    "\n",
    "The distance between two cities is defined as the Euclidean distance --- that is, two cities at locations  $(x,y)$ and $(z,w)$ have distance $\\sqrt{(x-z)^2 + (y-w)^2}$  between them.<br><br>\n",
    "\n",
    "**You should implement the nearest neighbor heuristic:**\n",
    "\n",
    "1. Start the tour at the first city.\n",
    "2. Repeatedly visit the closest city that the tour hasn't visited yet. In case of a tie, go to the closest city with the lowest index. For example, if both the third and fifth cities have the same distance from the first city (and are closer than any other city), then the tour should begin by going from the first city to the third city.\n",
    "3. Once every city has been visited exactly once, return to the first city to complete the tour.\n",
    "\n",
    "Find the cost of the traveling salesman tour computed by the nearest neighbor heuristic for this instance, rounded down to the nearest integer.\n",
    "\n",
    "[Hint: when constructing the tour, you might find it simpler to work with squared Euclidean distances (i.e., the formula above but without the square root) than Euclidean distances. But don't forget to report the length of the tour in terms of standard Euclidean distance.]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/aishwaya/anaconda2/envs/python_3_6/lib/python3.6/site-packages/urllib3/connectionpool.py:847: InsecureRequestWarning: Unverified HTTPS request is being made. Adding certificate verification is strongly advised. See: https://urllib3.readthedocs.io/en/latest/advanced-usage.html#ssl-warnings\n",
      "  InsecureRequestWarning)\n"
     ]
    }
   ],
   "source": [
    "import urllib3\n",
    "import networkx as nx\n",
    "\n",
    "\n",
    "def TSP_nearest_neighbor_heuristic(url):\n",
    "    # pre-processing input dataset\n",
    "    challenge_graph = nx.Graph()\n",
    "    http = urllib3.PoolManager()\n",
    "    r1 = http.request('GET', url)\n",
    "    IntegerMatrixStringJoin = r1.data.decode('utf8').split('\\r\\n')\n",
    "    IntegerMatrixStringJoin.remove('')\n",
    "    n = int(IntegerMatrixStringJoin[0])\n",
    "    IntegerMatrixStringJoin.remove(IntegerMatrixStringJoin[0])\n",
    "    coords_cities = []\n",
    "    edges = []\n",
    "    for i in IntegerMatrixStringJoin:\n",
    "        node_coord = i.split(' ')\n",
    "        city = int(node_coord[0])\n",
    "        x = float(node_coord[1])\n",
    "        y = float(node_coord[2])\n",
    "        coords_cities.append([x, y, city])\n",
    "    for i in range(len(coords_cities)):\n",
    "        challenge_graph.add_node(coords_cities[i][0], pos=(coords_cities[i][0], coords_cities[i][1]))\n",
    "    for c1 in range(n-1):\n",
    "        for c2 in range(c1+1, n):\n",
    "            euclidean_distance = ((coords_cities[c1][0]-coords_cities[c2][0])**2 + (coords_cities[c1][1]-coords_cities[c2][1])**2)**0.5\n",
    "            edges.append((coords_cities[c1][2], coords_cities[c2][2], euclidean_distance))\n",
    "    challenge_graph.add_weighted_edges_from(edges)\n",
    "    # TSP\n",
    "    not_visited = [_ for _ in range(1, n+1)]\n",
    "    x = 1\n",
    "    tsp_tour = 0\n",
    "    not_visited.remove(x)\n",
    "    while len(not_visited) != 0:\n",
    "        print(len(not_visited))\n",
    "        neighbour = list(challenge_graph.neighbors(x))\n",
    "        minimum_neighbour = float('inf')\n",
    "        minimum_neighbour_x = n\n",
    "        for nei in neighbour:\n",
    "            if nei in not_visited:\n",
    "                wt = challenge_graph.edges[x, nei]['weight']\n",
    "                if (wt < minimum_neighbour) or ( (wt == minimum_neighbour) and (nei < minimum_neighbour_x) ):                    \n",
    "                    minimum_neighbour = wt\n",
    "                    minimum_neighbour_x = nei\n",
    "        tsp_tour += minimum_neighbour\n",
    "        x = minimum_neighbour_x\n",
    "        not_visited.remove(minimum_neighbour_x)\n",
    "    tsp_tour += challenge_graph.edges[1, x]['weight']\n",
    "    print(\"Cost of the traveling salesman tour computed by the nearest neighbor heuristic:\".format(tsp_tour))\n",
    "\n",
    "\n",
    "TSP_nearest_neighbor_heuristic(\"https://d3c33hcgiwev3.cloudfront.net/_ae5a820392a02042f87e3b437876cf19_nn.txt?Expires=1564531200&Signature=IUPe~3Fk8ERGhOqNqtT7Xo6jUL66lzchM2PAgqwxuTvdNYpRmSZRKpCNAydcAP579dU8WNSkwWISgMllNTGWorZdSf9adNgZFWNfY-wpfnTmw4k8mE0PMPydHFlAu6r8ZM6Pv5i3hj5TnfftrawqpeKRS7dNEL~MZV8Es1c0GiU_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A\")\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### TODO\n",
    "\n",
    "Answer 1203406.501271"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}