KnapsackProblem.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving the Knapsack Problem with Quantum\n",
    "In this notebook we take on the challenge of solving a common constraint satisfaction problem known as the knapsack problem.\n",
    "\n",
    "* Hardware: D-Wave Advantage System version 1.1\n",
    "* Provider: Amazon Web Services Braket\n",
    "* Notebook: KnapsackProblem.ipynb\n",
    "* Revision: 3.0.1\n",
    "* Cost_USD: 1.47=3 jobs created x ( (0.00019/shot x 1000 shots/job) + (0.3/job) )\n",
    "\n",
    "notebook by [Brian Lechthaler](https://github.com/brianlechthaler) | gnu gpl v3 | third revision | 2020-12-15 | please don't distribute without explicit written consent and/or giving attribution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1: Introduction\n",
    "### 1.0: Shipping Fruit\n",
    "Let's imagine for a moment that we are farmers who export their fruit to other countries. We have 4 fruits to ship abroad: grapes, apples, bananas and pears. Each item, as shown in the figure below, is packaged in a large box to then be packed into a standard shipping container."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src='https://storage.googleapis.com/jupyter_assets-463b/knapsack_fruits.svg'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 The Problem\n",
    "There's plenty of room in the shipping container to fit as many boxes as we need, but due to the weight limits of shipping containers and the vehicles used to transport them we can only store so many boxes of each fruit before hitting weight limits. \n",
    "\n",
    "What's the most profitable way can we fill our container without exceeding weight limits while also exceeding weight limits?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://storage.googleapis.com/jupyter_assets-463b/knapsack_shippingContainer.svg\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2: The Solution\n",
    "This problem that we are faced with is characteristic of the exact kind of problem Quantum Annealers excel at: it's a constraint solution problem that can be expressed as a Binary Quadratic Model, or BQM for short. \n",
    "\n",
    "### 1.3: Technical Overview of Solution\n",
    "This notebook starts by generating a BQM from input variables. Then, a sampler and EmbeddingComposite() is created for our D-Wave machine on AWS. We then send a request over to our D-Wave machine that queues our BQM as a new job and runs it as soon as there is availibility. Once our BQM is on the QPU, it gets solved very quickly (nanoseconds to milliseconds) and returned back to us. Even after we test the limits and scale until we can't anymore, it still only takes a fraction of a fraction of a second to run. This is the magic of quantum: solving large scale equations with many variables in quadratic time, as opposed to linear or even logarithmic time for a classical computer performing the same operation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: Imports and Configuration\n",
    "### 2.0: Fetch Datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "fatal: destination path 'knapsack' already exists and is not an empty directory.\n"
     ]
    }
   ],
   "source": [
    "# Pull the original example to get the datasets. Comment this out if you don't need it.\n",
    "!git clone https://github.com/dwave-examples/knapsack.git"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1: Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "from itertools import combinations\n",
    "from dwave.system.composites import EmbeddingComposite\n",
    "from braket.ocean_plugin import BraketDWaveSampler\n",
    "import time\n",
    "from datetime import datetime as dt\n",
    "import pandas as pd\n",
    "import dimod\n",
    "from math import log2, floor\n",
    "from bucket import get_bucket as bucket"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2: Notebook Specific Configuration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# notebook specific config\n",
    "dwave_qpu = 'Advantage_system1'\n",
    "notebook_start_time = time.time()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3: AWS-Specific Configuration"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#AWS specific config\n",
    "# Please enter the S3 bucket you created during onboarding in the code below\n",
    "my_bucket = bucket() # the name of the bucket\n",
    "my_prefix = \"results\" # the name of the folder in the bucket\n",
    "s3_folder = (my_bucket, my_prefix)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 3: Defining Functions\n",
    "### 3.0: Timestamper\n",
    "This is a helpful function to quickly add a timestamp to the output of this notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tsmsg(msg=None):\n",
    "    now = dt.now()\n",
    "    timestamp = f'[@{str(now)}]: '\n",
    "    message = timestamp + msg\n",
    "    return message"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1: Sampler Builder\n",
    "This function creates our sampler along with an EmbeddingComposite() for the sampler. \n",
    "#### 3.1.1: What is Embedding?\n",
    "Embedding is the process of mapping the problem to the layout of a system's qubits.\n",
    "#### 3.1.2: Why is Embedding Important?\n",
    "Embedding is an important part of any D-Wave solution, as the [Pegasus topology](https://support.dwavesys.com/hc/en-us/articles/360054564874-What-is-the-Pegasus-Topology-) is not fully connected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mksampler():\n",
    "    arn = 'arn:aws:braket:::device/qpu/d-wave/' + dwave_qpu\n",
    "    print(tsmsg(f'Building sampler from {arn}...'))\n",
    "    sampler = BraketDWaveSampler(s3_folder, arn)\n",
    "    print(tsmsg(f'BraketDWaveSampler successfully built for {dwave_qpu} on AWS Braket.'))\n",
    "    print(tsmsg(f'Building EmbeddingComposite() sampler for {dwave_qpu}...'))\n",
    "    mkembed_start = time.time()\n",
    "    sampler = EmbeddingComposite(sampler)\n",
    "    mkembed_end = time.time()\n",
    "    mkembed_delta = mkembed_end - mkembed_start\n",
    "    print(tsmsg(f'EmbeddingComposite() successfully built for {dwave_qpu} in {mkembed_delta} seconds.\\n    -> Returning sampler.'))\n",
    "    return sampler"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2: Sampler Runner\n",
    "This function is responsible for sending the BQM to the D-Wave machine for solving."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def runSampler(bqm):\n",
    "    x = '\\n    -> '\n",
    "    print(tsmsg('Building sampler...'))\n",
    "    sampler = mksampler()\n",
    "    print(tsmsg(f\"[CLASSIC->QUANTUM] Creating a job to anneal on {dwave_qpu}'s QPU, and awaiting results...\"))\n",
    "    sampStart = time.time()\n",
    "    sampleset = sampler.sample(bqm)\n",
    "    sampEnd = time.time()\n",
    "    sampDelta = sampEnd - sampStart\n",
    "    print(tsmsg(f\"[QUANTUM->CLASSIC] Annealing completed successfully.{x}{sampDelta} seconds have elapsed since we sent our job to {dwave_qpu}.{x}Returning results from from {dwave_qpu}'s QPU.\"))\n",
    "    sample = sampleset.first.sample\n",
    "    energy = sampleset.first.energy\n",
    "    return sampleset, sample, energy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3: Knapsack Builder\n",
    "This function converts our costs, weights, and the maximum weight we can carry into a BQM."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_knapsack_bqm(costs, weights, weight_capacity):\n",
    "    x = '\\n    -> '\n",
    "    \"\"\"Construct BQM for the knapsack problem\n",
    "    \n",
    "    Args:\n",
    "        costs (array-like):\n",
    "            Array of costs associated with the items\n",
    "        weights (array-like):\n",
    "            Array of weights associated with the items\n",
    "        weight_capacity (int):\n",
    "            Maximum allowable weight\n",
    "    \n",
    "    Returns:\n",
    "        Binary quadratic model instance\n",
    "    \"\"\"\n",
    "    print(tsmsg('Building BQM.'))\n",
    "    buildbqmstart = time.time()\n",
    "    # Initialize BQM - use large-capacity BQM so that the problem can be\n",
    "    # scaled by the user.\n",
    "    bqm = dimod.AdjVectorBQM(dimod.Vartype.BINARY)\n",
    "\n",
    "    # Lagrangian multiplier\n",
    "    # First guess as suggested in Lucas's paper\n",
    "    lagrange = max(costs)\n",
    "\n",
    "    # Number of objects\n",
    "    x_size = len(costs)\n",
    "\n",
    "    # Lucas's algorithm introduces additional slack variables to\n",
    "    # handle the inequality. M+1 binary slack variables are needed to\n",
    "    # represent the sum using a set of powers of 2.\n",
    "    M = floor(log2(weight_capacity))\n",
    "    num_slack_variables = M + 1\n",
    "\n",
    "    # Slack variable list for Lucas's algorithm. The last variable has\n",
    "    # a special value because it terminates the sequence.\n",
    "    y = [2**n for n in range(M)]\n",
    "    y.append(weight_capacity + 1 - 2**M)\n",
    "\n",
    "    # Hamiltonian xi-xi terms\n",
    "    for k in range(x_size):\n",
    "        bqm.set_linear('x' + str(k), lagrange * (weights[k]**2) - costs[k])\n",
    "\n",
    "    # Hamiltonian xi-xj terms\n",
    "    for i in range(x_size):\n",
    "        for j in range(i + 1, x_size):\n",
    "            key = ('x' + str(i), 'x' + str(j))\n",
    "            bqm.quadratic[key] = 2 * lagrange * weights[i] * weights[j]\n",
    "\n",
    "    # Hamiltonian y-y terms\n",
    "    for k in range(num_slack_variables):\n",
    "        bqm.set_linear('y' + str(k), lagrange * (y[k]**2))\n",
    "\n",
    "    # Hamiltonian yi-yj terms\n",
    "    for i in range(num_slack_variables):\n",
    "        for j in range(i + 1, num_slack_variables):\n",
    "            key = ('y' + str(i), 'y' + str(j))\n",
    "            bqm.quadratic[key] = 2 * lagrange * y[i] * y[j]\n",
    "\n",
    "    # Hamiltonian x-y terms\n",
    "    for i in range(x_size):\n",
    "        for j in range(num_slack_variables):\n",
    "            key = ('x' + str(i), 'y' + str(j))\n",
    "            bqm.quadratic[key] = -2 * lagrange * weights[i] * y[j]\n",
    "    \n",
    "    buildbqmend = time.time()\n",
    "    buildbqmdelta = buildbqmend - buildbqmstart\n",
    "    \n",
    "    print(tsmsg(f'Done.{x}BQM built in {buildbqmdelta} seconds.'))\n",
    "    \n",
    "    return bqm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4: Compile the BQM\n",
    "This function uses the logic we just defined to create a BQM to be solved on our D-Wave machine, and time how long it takes to do so."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compileBQM(costs, weights, weight_capacity):\n",
    "    x = '\\n    -> '\n",
    "    #Build knapsack problem from costs, weights, and max capacity\n",
    "    \n",
    "    print(tsmsg(f\"Compiling BQM with: {x}Input Costs: {costs}{x}Weights: {weights}{x}Max Weight: {weight_capacity}\"))\n",
    "    \n",
    "    bqmstart = time.time()\n",
    "    bqm = build_knapsack_bqm(costs, weights, weight_capacity)\n",
    "    bqmend = time.time()\n",
    "    bqmdelta = bqmend - bqmstart\n",
    "    \n",
    "    print(tsmsg(f\"Done. BQM compiled in {bqmdelta} seconds.\"))\n",
    "    \n",
    "    return bqm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.5: Solve BQM\n",
    "Now that we have our BQM all we have to do is send it to our D-Wave quantum annealer and wait for the response, then we decide whether the result is valid, run again if it isn't and finally return the valid solution when we are done. Note the valid solution verification step at the end, this kind of error handling is vital to building good quantum solutions: because at the end of the day we're relying on quantum physics to run calculations for production workloads."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_knapsack():\n",
    "    return None\n",
    "def solve_knapsack(costs, weights, weight_capacity, sampler=None, xdf=pd.DataFrame()):\n",
    "    \"\"\"Construct BQM and solve the knapsack problem\n",
    "    \n",
    "    Args:\n",
    "        costs (array-like):\n",
    "            Array of costs associated with the items\n",
    "        weights (array-like):\n",
    "            Array of weights associated with the items\n",
    "        weight_capacity (int):\n",
    "            Maximum allowable weight\n",
    "        sampler (BQM sampler instance or None):\n",
    "            A BQM sampler instance or None, in which case\n",
    "            LeapHybridSampler is used by default\n",
    "    \n",
    "    Returns:\n",
    "        Tuple:\n",
    "            List of indices of selected items\n",
    "            Solution energy\n",
    "    \"\"\"\n",
    "    \n",
    "    x = '\\n    -> '\n",
    "    # store original variables in case we need to re-run function\n",
    "    original_costs = costs\n",
    "    original_weights = weights\n",
    "    original_weightcap = weight_capacity\n",
    "    \n",
    "    # compile a BQM from input variables\n",
    "    bqm = compileBQM(costs, weights, weight_capacity)\n",
    "    # run the sampler and read the results into 3 variables\n",
    "    sampleset, sample, energy = runSampler(bqm)\n",
    "\n",
    "    # Build solution from returned binary variables:\n",
    "    selected_item_indices = []\n",
    "    for varname, value in sample.items():\n",
    "        # For each \"x\" variable, check whether its value is set, which\n",
    "        # indicates that the corresponding item is included in the\n",
    "        # knapsack\n",
    "        if value and varname.startswith('x'):\n",
    "            # The index into the weight array is retrieved from the\n",
    "            # variable name\n",
    "            selected_item_indices.append(int(varname[1:]))\n",
    "            \n",
    "    selected_weights = list(xdf.loc[selected_item_indices, 'weight'])\n",
    "    total_weight = sum(selected_weights)\n",
    "    \n",
    "    if total_weight > original_weightcap:\n",
    "        print(tsmsg(f'[ERROR]: Invalid solution, total weight exceeds specified maximum capacity. {x}[WARNING]: Attempting to try again, this may incur significant costs.'))\n",
    "        solve_knapsack(original_costs, original_weights, original_weightcap, sampler, xdf=xdf)\n",
    "    else:\n",
    "        return sorted(selected_item_indices), energy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.6: Tying it all Together (Main Function)\n",
    "Finally, we take all the pieces we just defined and put them together to make our main function. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def knapsackSolver(wt_cap=None, pth=None):\n",
    "    \n",
    "    # set defaults just in case\n",
    "    if wt_cap == None:\n",
    "        wt_cap = 50\n",
    "    if pth == None:\n",
    "        pth = 'knapsack/data/small.csv'\n",
    "\n",
    "    # parse input data\n",
    "    print(tsmsg(f'Reading the contents of file {pth} into a new Pandas DataFrame.'))\n",
    "    \n",
    "    csvreadstart = time.time()\n",
    "    df = pd.read_csv(pth, names=['cost', 'weight'])\n",
    "    csvreadstop = time.time()\n",
    "    csvreaddelta = csvreadstop - csvreadstart\n",
    "    \n",
    "    print(tsmsg(f'New dataframe created from file {pth} in {csvreaddelta} seconds.'))\n",
    "\n",
    "    selected_item_indices, energy = solve_knapsack(df['cost'], df['weight'], wt_cap, xdf=df)\n",
    "    selected_weights = list(df.loc[selected_item_indices,'weight'])\n",
    "    selected_costs = list(df.loc[selected_item_indices,'cost'])\n",
    "    energysummary = \"----> SOLUTION: Found solution at energy {}\".format(energy)\n",
    "    \n",
    "    print(tsmsg(energysummary))\n",
    "    itemsummary = \"----> SOLUTION: Selected item numbers (0-indexed): \" + str(selected_item_indices)\n",
    "    print(tsmsg(itemsummary))\n",
    "    weightsummary = \"----> SOLUTION: Selected item weights: {}, total = {}\".format(selected_weights, sum(selected_weights))\n",
    "    print(tsmsg(weightsummary))\n",
    "    costsummary = \"----> SOLUTION: Selected item costs: {}, total = {}\".format(selected_costs, sum(selected_costs))\n",
    "    print(tsmsg(costsummary))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 4: Testing & Results!\n",
    "### 4.0: First Test\n",
    "For our first test run, we try a max weight of 50 with the \"small\" dataset. As expected, the D-Wave Annealer has absolutely no problem solving this problem in nanoseconds-to-milliseconds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[@2020-12-16 02:45:59.929206]: Reading the contents of file knapsack/data/small.csv into a new Pandas DataFrame.\n",
      "[@2020-12-16 02:45:59.933647]: New dataframe created from file knapsack/data/small.csv in 0.0041162967681884766 seconds.\n",
      "[@2020-12-16 02:45:59.934857]: Compiling BQM with: \n",
      "    -> Input Costs: 0    35\n",
      "1    85\n",
      "2    30\n",
      "3    50\n",
      "4    70\n",
      "5    80\n",
      "6    55\n",
      "Name: cost, dtype: int64\n",
      "    -> Weights: 0    12\n",
      "1    27\n",
      "2    11\n",
      "3    17\n",
      "4    20\n",
      "5    10\n",
      "6    15\n",
      "Name: weight, dtype: int64\n",
      "    -> Max Weight: 50\n",
      "[@2020-12-16 02:45:59.935153]: Building BQM.\n",
      "[@2020-12-16 02:45:59.936350]: Done.\n",
      "    -> BQM built in 0.0011515617370605469 seconds.\n",
      "[@2020-12-16 02:45:59.936677]: Done. BQM compiled in 0.0015211105346679688 seconds.\n",
      "[@2020-12-16 02:45:59.936719]: Building sampler...\n",
      "[@2020-12-16 02:45:59.936752]: Building sampler from arn:aws:braket:::device/qpu/d-wave/Advantage_system1...\n",
      "[@2020-12-16 02:46:02.408127]: BraketDWaveSampler successfully built for Advantage_system1 on AWS Braket.\n",
      "[@2020-12-16 02:46:02.409345]: Building EmbeddingComposite() sampler for Advantage_system1...\n",
      "[@2020-12-16 02:46:02.890843]: EmbeddingComposite() successfully built for Advantage_system1 in 0.4814434051513672 seconds.\n",
      "    -> Returning sampler.\n",
      "[@2020-12-16 02:46:02.890966]: [CLASSIC->QUANTUM] Creating a job to anneal on Advantage_system1's QPU, and awaiting results...\n",
      "[@2020-12-16 02:46:13.941353]: [QUANTUM->CLASSIC] Annealing completed successfully.\n",
      "    -> 11.050327777862549 seconds have elapsed since we sent our job to Advantage_system1.\n",
      "    -> Returning results from from Advantage_system1's QPU.\n",
      "[@2020-12-16 02:46:13.944548]: ----> SOLUTION: Found solution at energy -200.0\n",
      "[@2020-12-16 02:46:13.944623]: ----> SOLUTION: Selected item numbers (0-indexed): [3, 4, 5]\n",
      "[@2020-12-16 02:46:13.944955]: ----> SOLUTION: Selected item weights: [17, 20, 10], total = 47\n",
      "[@2020-12-16 02:46:13.944995]: ----> SOLUTION: Selected item costs: [50, 70, 80], total = 200\n"
     ]
    }
   ],
   "source": [
    "knapsackSolver(50, 'knapsack/data/small.csv')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1: Second Test\n",
    "Yet again, our annealer proves what can only be described as quantum's *complete and total ascendancy* over any model or practical example we have to describe even our wildest dreams of classical computer performance. Just imagine what the world will be able to do once we can eliminate current barriers like noise(interference), size, temperature (superconductors currently used in quantum computers need to be kept at well over 150x colder temperatures than interstellar space.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[@2020-12-16 02:46:13.953362]: Reading the contents of file knapsack/data/small.csv into a new Pandas DataFrame.\n",
      "[@2020-12-16 02:46:13.956331]: New dataframe created from file knapsack/data/small.csv in 0.002612590789794922 seconds.\n",
      "[@2020-12-16 02:46:13.957441]: Compiling BQM with: \n",
      "    -> Input Costs: 0    35\n",
      "1    85\n",
      "2    30\n",
      "3    50\n",
      "4    70\n",
      "5    80\n",
      "6    55\n",
      "Name: cost, dtype: int64\n",
      "    -> Weights: 0    12\n",
      "1    27\n",
      "2    11\n",
      "3    17\n",
      "4    20\n",
      "5    10\n",
      "6    15\n",
      "Name: weight, dtype: int64\n",
      "    -> Max Weight: 75\n",
      "[@2020-12-16 02:46:13.957500]: Building BQM.\n",
      "[@2020-12-16 02:46:13.958925]: Done.\n",
      "    -> BQM built in 0.001384735107421875 seconds.\n",
      "[@2020-12-16 02:46:13.959648]: Done. BQM compiled in 0.002143383026123047 seconds.\n",
      "[@2020-12-16 02:46:13.959689]: Building sampler...\n",
      "[@2020-12-16 02:46:13.959728]: Building sampler from arn:aws:braket:::device/qpu/d-wave/Advantage_system1...\n",
      "[@2020-12-16 02:46:15.985431]: BraketDWaveSampler successfully built for Advantage_system1 on AWS Braket.\n",
      "[@2020-12-16 02:46:15.985893]: Building EmbeddingComposite() sampler for Advantage_system1...\n",
      "[@2020-12-16 02:46:16.514834]: EmbeddingComposite() successfully built for Advantage_system1 in 0.5288896560668945 seconds.\n",
      "    -> Returning sampler.\n",
      "[@2020-12-16 02:46:16.514948]: [CLASSIC->QUANTUM] Creating a job to anneal on Advantage_system1's QPU, and awaiting results...\n",
      "[@2020-12-16 02:46:20.961942]: [QUANTUM->CLASSIC] Annealing completed successfully.\n",
      "    -> 4.446569204330444 seconds have elapsed since we sent our job to Advantage_system1.\n",
      "    -> Returning results from from Advantage_system1's QPU.\n",
      "[@2020-12-16 02:46:20.965176]: ----> SOLUTION: Found solution at energy -270.0\n",
      "[@2020-12-16 02:46:20.965255]: ----> SOLUTION: Selected item numbers (0-indexed): [0, 2, 4, 5, 6]\n",
      "[@2020-12-16 02:46:20.965293]: ----> SOLUTION: Selected item weights: [12, 11, 20, 10, 15], total = 68\n",
      "[@2020-12-16 02:46:20.965324]: ----> SOLUTION: Selected item costs: [35, 30, 70, 80, 55], total = 270\n"
     ]
    }
   ],
   "source": [
    "knapsackSolver(75, 'knapsack/data/small.csv')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 Final Tests\n",
    "Sometimes when giving our annealer a problem that pushes it's limits in terms of how large the solvable problem space we encounter errors. Try scaling the datasets and see what the largest combination you can achieve is."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[@2020-12-16 02:46:20.975360]: Reading the contents of file knapsack/data/small.csv into a new Pandas DataFrame.\n",
      "[@2020-12-16 02:46:20.978196]: New dataframe created from file knapsack/data/small.csv in 0.0025954246520996094 seconds.\n",
      "[@2020-12-16 02:46:20.978888]: Compiling BQM with: \n",
      "    -> Input Costs: 0    35\n",
      "1    85\n",
      "2    30\n",
      "3    50\n",
      "4    70\n",
      "5    80\n",
      "6    55\n",
      "Name: cost, dtype: int64\n",
      "    -> Weights: 0    12\n",
      "1    27\n",
      "2    11\n",
      "3    17\n",
      "4    20\n",
      "5    10\n",
      "6    15\n",
      "Name: weight, dtype: int64\n",
      "    -> Max Weight: 150\n",
      "[@2020-12-16 02:46:20.978973]: Building BQM.\n",
      "[@2020-12-16 02:46:20.980488]: Done.\n",
      "    -> BQM built in 0.0014789104461669922 seconds.\n",
      "[@2020-12-16 02:46:20.981497]: Done. BQM compiled in 0.002519369125366211 seconds.\n",
      "[@2020-12-16 02:46:20.982138]: Building sampler...\n",
      "[@2020-12-16 02:46:20.982293]: Building sampler from arn:aws:braket:::device/qpu/d-wave/Advantage_system1...\n",
      "[@2020-12-16 02:46:23.067321]: BraketDWaveSampler successfully built for Advantage_system1 on AWS Braket.\n",
      "[@2020-12-16 02:46:23.067442]: Building EmbeddingComposite() sampler for Advantage_system1...\n",
      "[@2020-12-16 02:46:23.652937]: EmbeddingComposite() successfully built for Advantage_system1 in 0.585444450378418 seconds.\n",
      "    -> Returning sampler.\n",
      "[@2020-12-16 02:46:23.653049]: [CLASSIC->QUANTUM] Creating a job to anneal on Advantage_system1's QPU, and awaiting results...\n",
      "[@2020-12-16 02:46:27.367364]: [QUANTUM->CLASSIC] Annealing completed successfully.\n",
      "    -> 3.7142715454101562 seconds have elapsed since we sent our job to Advantage_system1.\n",
      "    -> Returning results from from Advantage_system1's QPU.\n",
      "[@2020-12-16 02:46:27.371392]: ----> SOLUTION: Found solution at energy -340.0\n",
      "[@2020-12-16 02:46:27.371466]: ----> SOLUTION: Selected item numbers (0-indexed): [1, 3, 4, 5, 6]\n",
      "[@2020-12-16 02:46:27.371842]: ----> SOLUTION: Selected item weights: [27, 17, 20, 10, 15], total = 89\n",
      "[@2020-12-16 02:46:27.372002]: ----> SOLUTION: Selected item costs: [85, 50, 70, 80, 55], total = 340\n"
     ]
    }
   ],
   "source": [
    "knapsackSolver(150, 'knapsack/data/small.csv')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 5: Conclusions\n",
    "The knapsack problem, as with all constraint-satisfaction problems can be turned into a BQM. With our D-Wave quantum annealer, we can basically solve anything that is a BQM. By turning our problem into a BQM and solving it, we effectively exploit the dramatic speedup quantum offers for solving CSPs with large numbers of variables. The results speak for themselves. As we scale the problem up and down there are admittedly some errors we run into that are related to the actual accuracy of the machine. Over time, as quantum becomes less noisy and prone to errors, quantum computers could solve a wide range of problems at almost any scale in very small amounts of time. This massive boost in speed has the potential to usher in a new era of computing that brings use cases and solutions we could have never thought of even in our most optimistic dreams. Will they replace classical computers? Likely not, each has their advantages and weaknesses -- one cannot replace the other if one cannot be the other. Will quantum allow us to perform calculations we could not have before? Definitely. The speedup isn't just more convenient -- it makes easy work of certain problems like large prime factorisation previously thought to be impossible even for some future civilization that uses most of the universe as a classical computer to solve. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[@2020-12-16 02:46:27.382264]: Once dependencies were done importing, this notebook ran for a grand total of 27.54736638069153 seconds.\n",
      "    Notebook by Brian Lechthaler, last updated: 2020-12-16 02:46:27.382255.\n",
      "    Licensed under GNU GPL v3.\n",
      "    Do not re-distribute notebook or any of its contents without my explicit written consent and/or without attribution.\n",
      "    This notebook belongs to this repository: https://github.com/brianlechthaler/QuantumSolutions\n",
      "        If you found this useful, leave a star. Problems? Questions? Contact me or submit a pull request and I will be delighted to help you.\n"
     ]
    }
   ],
   "source": [
    "notebook_end_time = time.time()\n",
    "notebook_time_delta = notebook_end_time - notebook_start_time\n",
    "print(tsmsg(f'Once dependencies were done importing, this notebook ran for a grand total of {notebook_time_delta} seconds.\\n    Notebook by Brian Lechthaler, last updated: {str(dt.now())}.\\n    Licensed under GNU GPL v3.\\n    Do not re-distribute notebook or any of its contents without my explicit written consent and/or without attribution.\\n    This notebook belongs to this repository: https://github.com/brianlechthaler/QuantumSolutions\\n        If you found this useful, leave a star. Problems? Questions? Contact me or submit a pull request and I will be delighted to help you.'))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "conda_braket",
   "language": "python",
   "name": "conda_braket"
  },
  "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.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}