2d_bin_packing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# QOSF 10\n",
    "<h2>Task 3 - Optimization of the 2D Bin Packing Problem</h2>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "  <center>\n",
    "  <img src=\"img/bpp.png\" alt=\"My image caption\" height=250>\n",
    "  <figcaption>Instance of 2D BPP solved using quantum annealing</figcaption>\n",
    "  </center>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Project Summary\n",
    "\n",
    "Imagine you're packing for a flight — whether you realize it or not, you're tackling a classic optimization challenge known as the **Bin Packing Problem (BPP)**. In its three-dimensional form, the task is to efficiently fit as many items (cases) as possible into a limited number of suitcases (bins), while also adhering to weight restrictions imposed by the airline. By considering these real-world constraints, BPP can be divided into two subproblems:\n",
    "- <u>Weight</u>: By choosing whether or not to include a case in a particular bin, stay under the declared weight limit per bin\n",
    "- <u>Space</u>: Assuming all the cases can fit by rearranging them between bins, find a spatial configuration that manages to fit all the cases\n",
    "\n",
    "The weight problem is formulated as a constrained optimization over binary variables, see [[1]](#openqaoa). In this work we focus on optimizing for space, deriving mainly from [[2]](#dwave3d), and break down the problem by simplifying it to two dimensions.\n",
    "\n",
    "The 2D BPP is described mathematically as a constrained quadratic model (CQM). We describe the coordinates of case $i$ as $(x_i, y_i)$. These are real-valued variables which pose a challenge for implementing on a digital quantum computer. Fortunately a solution can be found on D-Wave's `LeapHybridCQMSampler` backend which is a quantum-classical hybrid sampler [[3]](#ocean) that uses GPUs to handle the non-binary continuous variables in the CQM.\n",
    "\n",
    "First, import the required packages."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pickle\n",
    "import dimod\n",
    "import packing2d as bpp\n",
    "import pennylane as qml\n",
    "import pennylane.numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem instance and constraints\n",
    "We can use a stored solution from a past run, or start a job to run on the cloud (requires sign-in to Leap).\n",
    "\n",
    "In the original implementation from [[2]](#dwave3d), the user has the ability to generate random problem instances in a slider-based GUI. Our port reads in a 2D BPP instance from a file, see `packing2d.py` for more information. This is done on purpose to stay within the free tier limits of the cloud service. As an example we choose medium-seized instance of BPP (see `test_data.txt`) which requires 2 bins and runs relatively quick on the cloud. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run on D-Wave service (True), or use a cached run (False)\n",
    "QPU = False\n",
    "\n",
    "cached = {\n",
    "    \"med\" : {\"p\" : \"cache/test_data_1.txt\", \"s\" : \"cache/solution_1.pickle\"},\n",
    "    \"easy\" : {\"p\" : \"cache/test_data_2.txt\", \"s\" : \"cache/solution_2.pickle\"}\n",
    "}\n",
    "\n",
    "data = bpp.read_instance(cached[\"med\"][\"p\"])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following section is a description of the CQM:\n",
    "- the variables pertaining to BPP\n",
    "- an expression to be extremized (objective)\n",
    "- a list of equalities and inequalities (constraints) that must be satisfied by a feasible solution on our problem variables.\n",
    "\n",
    "<hr>\n",
    "\n",
    "#### Objective\n",
    "The objective for our CQM is three-fold:\n",
    "- Minimize average height of cases:\n",
    "    $$\n",
    "    o_1 = \\frac{\\sum_i y_i + y_i^\\prime}{m}\n",
    "    $$\n",
    "    where $y_i^\\prime$ is the effective height (more later) and $m$ is the number of cases.\n",
    "- Minimize height of the case at the top of the bin:\n",
    "    $$\n",
    "    o_2 = \\sum_j s_j\n",
    "    $$\n",
    "    where $s_j$ is the height of the highest case in bin $j$.\n",
    "- Minimize the number of used bins:\n",
    "    $$\n",
    "    o_3 = H\\sum_j v_j\n",
    "    $$\n",
    "    where $v_j = 1$ if it contains atleast one case, and $H$ is the height of the bins. All bins have the same height which simplifies the problem, but not all bins are treated equally (more later).\n",
    "\n",
    "These objectives turn out to the be the same no matter the dimension of BPP, and the total objective is the sum $o_1+o_2+o_3$.\n",
    "\n",
    "\n",
    "#### Orientation constraints\n",
    "<figure>\n",
    "  <center>\n",
    "  <img src=\"img/orientation.svg\" alt=\"My image caption\" height=250>\n",
    "  <figcaption>Two possible orientations of the same case</figcaption>\n",
    "  </center>\n",
    "</figure>\n",
    "Each case has only one orientation, which is enforced by:\n",
    "\n",
    "$$\n",
    "\\sum_{i,k} r_{i,k} = 1\n",
    "$$\n",
    "\n",
    "where index $k$ runs over the two orientations in 2D shown above. In 3D, this would be 6 orientations. \n",
    "\n",
    "**Sidenote:** In a general axis-aligned BPP in $n$ dimensions we assign each axis of the hyperrectangle to one axis of the bin, which is $n!$ orientations, or the number of permutations of $n$ items without repetition.\n",
    "\n",
    "This is where the effective width and height of a case comes in handy. It chooses an orientation from these allowed permutations:\n",
    "\n",
    "$$\n",
    "\\begin{aligned}\n",
    "x_i^\\prime = w_i r_{i,1}+ h_i r_{i,2}\\\\\n",
    "y_i^\\prime = h_i r_{i,1}+ w_i r_{i,2}\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "\n",
    "#### Case and bin assignment constraints\n",
    "We calculate up front based on the total area of all the cases how many bins we actually need. Then we manually place the first case in the first bin. This leads to a series of constraints:\n",
    "- Each case goes to exactly one bin:\n",
    "    $$\n",
    "    \\sum_j u_{i,j} = 1\n",
    "    $$\n",
    "- Each case goes to exactly one bin:\n",
    "    $$\n",
    "    \\sum_i (1-v_j)u_{i,j} \\le 0\n",
    "    $$\n",
    "- Ensure bins are added in order:\n",
    "    $$\n",
    "    v_{j+1} - v_j \\le 0 \\qquad j \\ne n\n",
    "    $$\n",
    "\n",
    "\n",
    "#### Geometric constraints\n",
    "<figure>\n",
    "  <center>\n",
    "  <img src=\"img/geometric.svg\" alt=\"My image caption\" height=250>\n",
    "  <figcaption>Four possible placements of one case, relative to another</figcaption>\n",
    "  </center>\n",
    "</figure>\n",
    "\n",
    "We define the binary variable $b_{i,k,q}$ which defines the geometric relation $q \\in \\{0,1,2,3\\}$ between cases $i$ and $k$. As $q$ is unsigned, it seems to be cleverly optimized behind the scenes to $q \\in \\{00, 01, 10, 11\\}$. This means the following geometric constraints do not involve integer variables, which we notice in the CQM stats later. So the binary constraint indexed by $q$ encodes the four possible placements in 2D:\n",
    "1. Case $i$ is to the left of case $k$ ($q=0$)\n",
    "$$\n",
    "-(2-u_{i,j}u_{k,j}-b_{i,k,0})nW + (x_i+x_i^\\prime-x_k) \\le 0\n",
    "$$\n",
    "2. Case $i$ is above case $k$ ($q=1$)\n",
    "$$\n",
    "-(2-u_{i,j}u_{k,j}-b_{i,k,1})H + (y_i+y_i^\\prime-y_k) \\le 0\n",
    "$$\n",
    "3. Case $i$ is to the right of case $k$ ($q=2$)\n",
    "$$\n",
    "-(2-u_{i,j}u_{k,j}-b_{i,k,2})nW + (x_k+x_k^\\prime-x_i) \\le 0\n",
    "$$\n",
    "4. Case $i$ is below case $k$ ($q=3$)\n",
    "$$\n",
    "-(2-u_{i,j}u_{k,j}-b_{i,k,3})H + (y_k+y_k^\\prime-y_i) \\le 0\n",
    "$$\n",
    "We have to multiply the width $W$ by number of bins $n$ because we stack the bins left to right. $x_i = 0$ means bottom left of case $i$ is located at the bottom left of the first bin. \n",
    "\n",
    "To enforce only one placement of case $i$ relative to case $k$, we have:\n",
    "$$\n",
    "\\sum_{i,k,q} b_{i,k,q} = 1\n",
    "$$\n",
    "\n",
    "**Sidenote:** A BPP in $n$ dimensions would have $2n$ geometric relations, one for each face of the hyperrectangle.\n",
    "\n",
    "#### Bin boundary constraints\n",
    "These sets of constraints ensure that case $i$ is not placed outside the bins\n",
    "$$\n",
    "\\begin{aligned}\n",
    "y_i + y_i^\\prime - H \\le 0\\\\\n",
    "y_i + y_i^\\prime - s_j - (1-u_{i,j})nW \\le 0\\\\\n",
    "x_i + x_i^\\prime - W(j+1) - (1-u_{i,j})nW \\le 0\\\\\n",
    "jWu_{i,j} - x_i \\le 0\n",
    "\\end{aligned}\n",
    "$$\n",
    "\n",
    "This concludes our mathematical description of the CQM.\n",
    "<hr>\n",
    "\n",
    "Notice that we can frame every inequality constraint as less-than-equal (LE) to zero. According to [[4]](#dwavewp), the entire CQM can be cast as a minimization of the following:\n",
    "$$\n",
    "\\argmin \\quad \\text{objective} + \\text{square of the LHS of LE constraint}\n",
    "$$\n",
    "If one tries to manually change any of the LE constraints to GE, we can see this reflected in the CQM stats. But `dimod` would need to convert them back to LE under the hood to perform the above minimization.\n",
    "\n",
    "We now set up the CQM as stated above by specifying our variables (binary or real), and objectives and constraints on the variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of cases: 23\n",
      "Minimum Number of bins required: 2\n"
     ]
    }
   ],
   "source": [
    "cases = bpp.Cases(data)\n",
    "bins = bpp.Bins(data, cases)\n",
    "vars = bpp.Variables(cases, bins)\n",
    "\n",
    "cqm, effective_dimensions = bpp.build_cqm(vars, bins, cases)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A summary of the CQM (stats) is shown below. Some observations:\n",
    "- Clearly the number of variables grows with the number of cases and bins.\n",
    "- As mentioned earlier, the CQM constraints were all described as LT, so GT is zero. If we flip any constraints, LT + GT should stay constant if the problem size is fixed, i.e, we fix the number of cases and bins.\n",
    "- If we restrict to a much simpler problem of only one bin, we see that all the quadratic constraints vanish. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \n",
      "===================================MODEL INFORMATION===================================\n",
      "          Variables                    Constraints               Sensitivity\n",
      "------------------------------ ---------------------------- ------------------\n",
      "  Binary    Integer    Continuous    Quad    Linear    One-hot    EQ      LT    GT\n",
      "--------  ---------  ------------  ------  --------  ---------  ------  ----  ----\n",
      "    1102          0            48    1848       612        298     298  2162     0\n"
     ]
    }
   ],
   "source": [
    "bpp.print_cqm_stats(cqm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We note that the CQM objective is not an equation but an expression that needs to be minimized. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.043478260869565216*y_0 + 0.34782608695652173*o_0_0 + 0.21739130434782608*o_0_1 + 0.043478260869565216*y_1 + 0.34782608695652173*o_1_0 + 0.21739130434782608*o_1_1 + 0.043478260869565216*y_2 + 0.5217391304347826*o_2_0 + 0.5217391304347826*o_2_1 + 0.043478260869565216*y_3 + 0.5217391304347826*o_3_0 + 0.5217391304347826*o_3_1 + 0.043478260869565216*y_4 + 0.5217391304347826*o_4_0 + 0.5217391304347826*o_4_1 + 0.043478260869565216*y_5 + 0.5217391304347826*o_5_0 + 0.5217391304347826*o_5_1 + 0.043478260869565216*y_6 + 0.5217391304347826*o_6_0 + 0.5217391304347826*o_6_1 + 0.043478260869565216*y_7 + 0.5217391304347826*o_7_0 + 0.5217391304347826*o_7_1 + 0.043478260869565216*y_8 + 0.5217391304347826*o_8_0 + 0.5217391304347826*o_8_1 + 0.043478260869565216*y_9 + 0.5217391304347826*o_9_0 + 0.5217391304347826*o_9_1 + 0.043478260869565216*y_10 + 0.4782608695652174*o_10_0 + 0.34782608695652173*o_10_1 + 0.043478260869565216*y_11 + 0.4782608695652174*o_11_0 + 0.34782608695652173*o_11_1 + 0.043478260869565216*y_12 + 0.4782608695652174*o_12_0 + 0.34782608695652173*o_12_1 + 0.043478260869565216*y_13 + 0.4782608695652174*o_13_0 + 0.34782608695652173*o_13_1 + 0.043478260869565216*y_14 + 0.4782608695652174*o_14_0 + 0.34782608695652173*o_14_1 + 0.043478260869565216*y_15 + 0.17391304347826086*o_15_0 + 0.3913043478260869*o_15_1 + 0.043478260869565216*y_16 + 0.17391304347826086*o_16_0 + 0.3913043478260869*o_16_1 + 0.043478260869565216*y_17 + 0.17391304347826086*o_17_0 + 0.3913043478260869*o_17_1 + 0.043478260869565216*y_18 + 0.17391304347826086*o_18_0 + 0.3913043478260869*o_18_1 + 0.043478260869565216*y_19 + 0.17391304347826086*o_19_0 + 0.3913043478260869*o_19_1 + 0.043478260869565216*y_20 + 0.17391304347826086*o_20_0 + 0.3913043478260869*o_20_1 + 0.043478260869565216*y_21 + 0.17391304347826086*o_21_0 + 0.3913043478260869*o_21_1 + 0.043478260869565216*y_22 + 0.17391304347826086*o_22_0 + 0.3913043478260869*o_22_1 + upper_bound_0 + upper_bound_1\n"
     ]
    }
   ],
   "source": [
    "print(cqm.objective.to_polystring())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quantum annealer solution\n",
    "\n",
    "Now we try to solve our CQM by calling a sampler. Note that this process is non-deterministic. We may get a different result each time we run so a global optimum is not guaranteed. Depending on the problem and the solver used  we can pass in some arguments to get more samples out per run, see [[3]](#ocean)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "best_feasible = None\n",
    "\n",
    "if QPU:\n",
    "    best_feasible = bpp.call_solver(cqm, 20)\n",
    "else:\n",
    "    # Deserialize cached solution\n",
    "    with open(cached[\"med\"][\"s\"], \"rb\") as infile:\n",
    "        best_feasible = pickle.load(infile)\n",
    "        infile.close()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's visualize our solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.plotly.v1+json": {
       "config": {
        "plotlyServerURL": "https://plot.ly"
       },
       "data": [
        {
         "hoverinfo": "text",
         "hovertext": [
          "Quantity: 22"
         ],
         "mode": "text",
         "text": "Bin 1",
         "textfont": {
          "color": "black"
         },
         "type": "scatter",
         "x": [
          15
         ],
         "y": [
          -2.5
         ]
        },
        {
         "hoverinfo": "text",
         "hovertext": [
          "Quantity: 22"
         ],
         "mode": "text",
         "text": "Bin 2",
         "textfont": {
          "color": "black"
         },
         "type": "scatter",
         "x": [
          45
         ],
         "y": [
          -2.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#636EFA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 0<br>X: 25.0, Y: 17.0<br>Size: 5.0 x 8.0"
         ],
         "type": "scatter",
         "x": [
          27.5
         ],
         "y": [
          21
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#636EFA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 0<br>X: 25.0, Y: 9.0<br>Size: 5.0 x 8.0"
         ],
         "type": "scatter",
         "x": [
          27.5
         ],
         "y": [
          13
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#636EFA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 0<br>X: 25.0, Y: 9.0<br>Size: 5.0 x 8.0"
         ],
         "type": "scatter",
         "x": [
          27.5
         ],
         "y": [
          13
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 48.0, Y: 26.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          54
         ],
         "y": [
          32
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 48.0, Y: 26.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          54
         ],
         "y": [
          32
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 0.0, Y: 0.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          6
         ],
         "y": [
          6
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 0.0, Y: 0.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          6
         ],
         "y": [
          6
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 18.0, Y: 26.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          24
         ],
         "y": [
          32
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 18.0, Y: 26.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          24
         ],
         "y": [
          32
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 0.0, Y: 12.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          6
         ],
         "y": [
          18
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 0.0, Y: 12.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          6
         ],
         "y": [
          18
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 39.0, Y: 12.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          45
         ],
         "y": [
          18
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 39.0, Y: 12.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          45
         ],
         "y": [
          18
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 0.0, Y: 24.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          6
         ],
         "y": [
          30
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 0.0, Y: 24.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          6
         ],
         "y": [
          30
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 38.0, Y: 0.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          44
         ],
         "y": [
          6
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 38.0, Y: 0.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          44
         ],
         "y": [
          6
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 30.0, Y: 24.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          36
         ],
         "y": [
          30
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 30.0, Y: 24.0<br>Size: 12.0 x 12.0"
         ],
         "type": "scatter",
         "x": [
          36
         ],
         "y": [
          30
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#00CC96",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 2<br>X: 30.0, Y: 9.0<br>Size: 8.0 x 11.0"
         ],
         "type": "scatter",
         "x": [
          34
         ],
         "y": [
          14.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#00CC96",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 2<br>X: 30.0, Y: 9.0<br>Size: 8.0 x 11.0"
         ],
         "type": "scatter",
         "x": [
          34
         ],
         "y": [
          14.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#00CC96",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 2<br>X: 52.0, Y: 0.0<br>Size: 8.0 x 11.0"
         ],
         "type": "scatter",
         "x": [
          56
         ],
         "y": [
          5.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#00CC96",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 2<br>X: 52.0, Y: 0.0<br>Size: 8.0 x 11.0"
         ],
         "type": "scatter",
         "x": [
          56
         ],
         "y": [
          5.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#00CC96",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 2<br>X: 52.0, Y: 11.0<br>Size: 8.0 x 11.0"
         ],
         "type": "scatter",
         "x": [
          56
         ],
         "y": [
          16.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#00CC96",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 2<br>X: 52.0, Y: 11.0<br>Size: 8.0 x 11.0"
         ],
         "type": "scatter",
         "x": [
          56
         ],
         "y": [
          16.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#00CC96",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 2<br>X: 12.0, Y: 18.0<br>Size: 11.0 x 8.0"
         ],
         "type": "scatter",
         "x": [
          17.5
         ],
         "y": [
          22
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#00CC96",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 2<br>X: 12.0, Y: 18.0<br>Size: 11.0 x 8.0"
         ],
         "type": "scatter",
         "x": [
          17.5
         ],
         "y": [
          22
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#00CC96",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 2<br>X: 16.0, Y: 4.0<br>Size: 8.0 x 11.0"
         ],
         "type": "scatter",
         "x": [
          20
         ],
         "y": [
          9.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#00CC96",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 2<br>X: 16.0, Y: 4.0<br>Size: 8.0 x 11.0"
         ],
         "type": "scatter",
         "x": [
          20
         ],
         "y": [
          9.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 12.0, Y: 0.0<br>Size: 4.0 x 9.0"
         ],
         "type": "scatter",
         "x": [
          14
         ],
         "y": [
          4.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 12.0, Y: 0.0<br>Size: 4.0 x 9.0"
         ],
         "type": "scatter",
         "x": [
          14
         ],
         "y": [
          4.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 51.0, Y: 22.0<br>Size: 9.0 x 4.0"
         ],
         "type": "scatter",
         "x": [
          55.5
         ],
         "y": [
          24
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 51.0, Y: 22.0<br>Size: 9.0 x 4.0"
         ],
         "type": "scatter",
         "x": [
          55.5
         ],
         "y": [
          24
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 25.0, Y: 0.0<br>Size: 4.0 x 9.0"
         ],
         "type": "scatter",
         "x": [
          27
         ],
         "y": [
          4.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 25.0, Y: 0.0<br>Size: 4.0 x 9.0"
         ],
         "type": "scatter",
         "x": [
          27
         ],
         "y": [
          4.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 30.0, Y: 20.0<br>Size: 9.0 x 4.0"
         ],
         "type": "scatter",
         "x": [
          34.5
         ],
         "y": [
          22
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 30.0, Y: 20.0<br>Size: 9.0 x 4.0"
         ],
         "type": "scatter",
         "x": [
          34.5
         ],
         "y": [
          22
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 12.0, Y: 9.0<br>Size: 4.0 x 9.0"
         ],
         "type": "scatter",
         "x": [
          14
         ],
         "y": [
          13.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 12.0, Y: 9.0<br>Size: 4.0 x 9.0"
         ],
         "type": "scatter",
         "x": [
          14
         ],
         "y": [
          13.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 16.0, Y: 0.0<br>Size: 9.0 x 4.0"
         ],
         "type": "scatter",
         "x": [
          20.5
         ],
         "y": [
          2
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 16.0, Y: 0.0<br>Size: 9.0 x 4.0"
         ],
         "type": "scatter",
         "x": [
          20.5
         ],
         "y": [
          2
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 34.0, Y: 0.0<br>Size: 4.0 x 9.0"
         ],
         "type": "scatter",
         "x": [
          36
         ],
         "y": [
          4.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 34.0, Y: 0.0<br>Size: 4.0 x 9.0"
         ],
         "type": "scatter",
         "x": [
          36
         ],
         "y": [
          4.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 30.0, Y: 0.0<br>Size: 4.0 x 9.0"
         ],
         "type": "scatter",
         "x": [
          32
         ],
         "y": [
          4.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#AB63FA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 3<br>X: 30.0, Y: 0.0<br>Size: 4.0 x 9.0"
         ],
         "type": "scatter",
         "x": [
          32
         ],
         "y": [
          4.5
         ]
        }
       ],
       "layout": {
        "shapes": [
         {
          "line": {
           "color": "black",
           "width": 3
          },
          "type": "rect",
          "x0": 0,
          "x1": 30,
          "y0": 0,
          "y1": 50
         },
         {
          "line": {
           "color": "black",
           "width": 3
          },
          "type": "rect",
          "x0": 30,
          "x1": 60,
          "y0": 0,
          "y1": 50
         },
         {
          "fillcolor": "#636EFA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 25,
          "x1": 30,
          "y0": 17,
          "y1": 25
         },
         {
          "fillcolor": "#636EFA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 25,
          "x1": 30,
          "y0": 9,
          "y1": 17
         },
         {
          "fillcolor": "#636EFA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 25,
          "x1": 30,
          "y0": 9,
          "y1": 17
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 48,
          "x1": 60,
          "y0": 26,
          "y1": 38
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 48,
          "x1": 60,
          "y0": 26,
          "y1": 38
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 0,
          "x1": 12,
          "y0": 0,
          "y1": 12
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 0,
          "x1": 12,
          "y0": 0,
          "y1": 12
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 18,
          "x1": 30,
          "y0": 26,
          "y1": 38
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 18,
          "x1": 30,
          "y0": 26,
          "y1": 38
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 0,
          "x1": 12,
          "y0": 12,
          "y1": 24
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 0,
          "x1": 12,
          "y0": 12,
          "y1": 24
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 39,
          "x1": 51,
          "y0": 12,
          "y1": 24
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 39,
          "x1": 51,
          "y0": 12,
          "y1": 24
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 0,
          "x1": 12,
          "y0": 24,
          "y1": 36
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 0,
          "x1": 12,
          "y0": 24,
          "y1": 36
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 38,
          "x1": 50,
          "y0": 0,
          "y1": 12
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 38,
          "x1": 50,
          "y0": 0,
          "y1": 12
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 30,
          "x1": 42,
          "y0": 24,
          "y1": 36
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 30,
          "x1": 42,
          "y0": 24,
          "y1": 36
         },
         {
          "fillcolor": "#00CC96",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 30,
          "x1": 38,
          "y0": 9,
          "y1": 20
         },
         {
          "fillcolor": "#00CC96",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 30,
          "x1": 38,
          "y0": 9,
          "y1": 20
         },
         {
          "fillcolor": "#00CC96",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 52,
          "x1": 60,
          "y0": 0,
          "y1": 11
         },
         {
          "fillcolor": "#00CC96",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 52,
          "x1": 60,
          "y0": 0,
          "y1": 11
         },
         {
          "fillcolor": "#00CC96",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 52,
          "x1": 60,
          "y0": 11,
          "y1": 22
         },
         {
          "fillcolor": "#00CC96",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 52,
          "x1": 60,
          "y0": 11,
          "y1": 22
         },
         {
          "fillcolor": "#00CC96",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 12,
          "x1": 23,
          "y0": 18,
          "y1": 26
         },
         {
          "fillcolor": "#00CC96",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 12,
          "x1": 23,
          "y0": 18,
          "y1": 26
         },
         {
          "fillcolor": "#00CC96",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 16,
          "x1": 24,
          "y0": 4,
          "y1": 15
         },
         {
          "fillcolor": "#00CC96",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 16,
          "x1": 24,
          "y0": 4,
          "y1": 15
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 12,
          "x1": 16,
          "y0": 0,
          "y1": 9
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 12,
          "x1": 16,
          "y0": 0,
          "y1": 9
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 51,
          "x1": 60,
          "y0": 22,
          "y1": 26
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 51,
          "x1": 60,
          "y0": 22,
          "y1": 26
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 25,
          "x1": 29,
          "y0": 0,
          "y1": 9
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 25,
          "x1": 29,
          "y0": 0,
          "y1": 9
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 30,
          "x1": 39,
          "y0": 20,
          "y1": 24
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 30,
          "x1": 39,
          "y0": 20,
          "y1": 24
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 12,
          "x1": 16,
          "y0": 9,
          "y1": 18
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 12,
          "x1": 16,
          "y0": 9,
          "y1": 18
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 16,
          "x1": 25,
          "y0": 0,
          "y1": 4
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 16,
          "x1": 25,
          "y0": 0,
          "y1": 4
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 34,
          "x1": 38,
          "y0": 0,
          "y1": 9
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 34,
          "x1": 38,
          "y0": 0,
          "y1": 9
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 30,
          "x1": 34,
          "y0": 0,
          "y1": 9
         },
         {
          "fillcolor": "#AB63FA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 30,
          "x1": 34,
          "y0": 0,
          "y1": 9
         }
        ],
        "showlegend": false,
        "template": {
         "data": {
          "bar": [
           {
            "error_x": {
             "color": "#2a3f5f"
            },
            "error_y": {
             "color": "#2a3f5f"
            },
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "bar"
           }
          ],
          "barpolar": [
           {
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "barpolar"
           }
          ],
          "carpet": [
           {
            "aaxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "baxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "type": "carpet"
           }
          ],
          "choropleth": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "choropleth"
           }
          ],
          "contour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "contour"
           }
          ],
          "contourcarpet": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "contourcarpet"
           }
          ],
          "heatmap": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmap"
           }
          ],
          "heatmapgl": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmapgl"
           }
          ],
          "histogram": [
           {
            "marker": {
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "histogram"
           }
          ],
          "histogram2d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2d"
           }
          ],
          "histogram2dcontour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2dcontour"
           }
          ],
          "mesh3d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "mesh3d"
           }
          ],
          "parcoords": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "parcoords"
           }
          ],
          "pie": [
           {
            "automargin": true,
            "type": "pie"
           }
          ],
          "scatter": [
           {
            "fillpattern": {
             "fillmode": "overlay",
             "size": 10,
             "solidity": 0.2
            },
            "type": "scatter"
           }
          ],
          "scatter3d": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatter3d"
           }
          ],
          "scattercarpet": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattercarpet"
           }
          ],
          "scattergeo": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergeo"
           }
          ],
          "scattergl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergl"
           }
          ],
          "scattermapbox": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattermapbox"
           }
          ],
          "scatterpolar": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolar"
           }
          ],
          "scatterpolargl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolargl"
           }
          ],
          "scatterternary": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterternary"
           }
          ],
          "surface": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "surface"
           }
          ],
          "table": [
           {
            "cells": {
             "fill": {
              "color": "#EBF0F8"
             },
             "line": {
              "color": "white"
             }
            },
            "header": {
             "fill": {
              "color": "#C8D4E3"
             },
             "line": {
              "color": "white"
             }
            },
            "type": "table"
           }
          ]
         },
         "layout": {
          "annotationdefaults": {
           "arrowcolor": "#2a3f5f",
           "arrowhead": 0,
           "arrowwidth": 1
          },
          "autotypenumbers": "strict",
          "coloraxis": {
           "colorbar": {
            "outlinewidth": 0,
            "ticks": ""
           }
          },
          "colorscale": {
           "diverging": [
            [
             0,
             "#8e0152"
            ],
            [
             0.1,
             "#c51b7d"
            ],
            [
             0.2,
             "#de77ae"
            ],
            [
             0.3,
             "#f1b6da"
            ],
            [
             0.4,
             "#fde0ef"
            ],
            [
             0.5,
             "#f7f7f7"
            ],
            [
             0.6,
             "#e6f5d0"
            ],
            [
             0.7,
             "#b8e186"
            ],
            [
             0.8,
             "#7fbc41"
            ],
            [
             0.9,
             "#4d9221"
            ],
            [
             1,
             "#276419"
            ]
           ],
           "sequential": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ],
           "sequentialminus": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ]
          },
          "colorway": [
           "#636efa",
           "#EF553B",
           "#00cc96",
           "#ab63fa",
           "#FFA15A",
           "#19d3f3",
           "#FF6692",
           "#B6E880",
           "#FF97FF",
           "#FECB52"
          ],
          "font": {
           "color": "#2a3f5f"
          },
          "geo": {
           "bgcolor": "white",
           "lakecolor": "white",
           "landcolor": "#E5ECF6",
           "showlakes": true,
           "showland": true,
           "subunitcolor": "white"
          },
          "hoverlabel": {
           "align": "left"
          },
          "hovermode": "closest",
          "mapbox": {
           "style": "light"
          },
          "paper_bgcolor": "white",
          "plot_bgcolor": "#E5ECF6",
          "polar": {
           "angularaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "radialaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "scene": {
           "xaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "yaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "zaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           }
          },
          "shapedefaults": {
           "line": {
            "color": "#2a3f5f"
           }
          },
          "ternary": {
           "aaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "baxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "caxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "title": {
           "x": 0.05
          },
          "xaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          },
          "yaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          }
         }
        },
        "xaxis": {
         "range": [
          -5,
          66
         ],
         "showgrid": false
        },
        "yaxis": {
         "range": [
          -5,
          55.00000000000001
         ]
        }
       }
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig = bpp.plot_rects(\n",
    "    best_feasible, vars, cases, bins, effective_dimensions\n",
    ")\n",
    "fig.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hovering over the center of a case or the text below a bin will show some details of the case/bin. The plot is rescaled automatically based on the problem size."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## VQA and QAOA\n",
    "\n",
    "Our chosen flavor of BPP (optimizing space) has many variables, many of them continuous and real-valued. Encoding continuous data into qubits is possible ([`qml.AngleEmbedding`](https://docs.pennylane.ai/en/stable/code/api/pennylane.AngleEmbedding.html)) but reading it out is challenging. In this section we simplify the BPP instance greatly, and describe a possible strategy to solve the problem on a large enough quantum computer. Note that while running this problem is impractical right now, we provide some code that show a possible approach to tackle this problem.\n",
    "\n",
    "We need to discretize space into a lattice, that looks something like this:\n",
    "\n",
    "<figure>\n",
    "  <center>\n",
    "  <img src=\"img/partition.svg\" alt=\"My image caption\" height=250>\n",
    "  <figcaption>Discretizing 2D space using two qubits for each coordinate</figcaption>\n",
    "  </center>\n",
    "</figure>\n",
    "\n",
    "The following code sets up some useful parameters:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of qubits needed to represent a floating point value in [0,1)\n",
    "BITS_PRECISION = 8\n",
    "\n",
    "# Number of layers in QAOA\n",
    "NUM_LAYERS = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we use a much smaller problem instance of 4 cases that fit exactly into 2 bins. But even with a reduced problem size, we require ~100 qubits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of cases: 4\n",
      "Minimum Number of bins required: 2\n",
      " \n",
      "===================================MODEL INFORMATION===================================\n",
      "          Variables                    Constraints               Sensitivity\n",
      "------------------------------ ---------------------------- ------------------\n",
      "  Binary    Integer    Continuous    Quad    Linear    One-hot    EQ      LT    GT\n",
      "--------  ---------  ------------  ------  --------  ---------  ------  ----  ----\n",
      "      38          0            10      24        61         13      13    72     0\n"
     ]
    }
   ],
   "source": [
    "data = bpp.read_instance(cached[\"easy\"][\"p\"])\n",
    "\n",
    "cases = bpp.Cases(data)\n",
    "bins = bpp.Bins(data, cases)\n",
    "vars = bpp.Variables(cases, bins)\n",
    "\n",
    "cqm, effective_dimensions = bpp.build_cqm(vars, bins, cases)\n",
    "\n",
    "bpp.print_cqm_stats(cqm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The small BPP instance admits a tight fit, as per the annealing solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.plotly.v1+json": {
       "config": {
        "plotlyServerURL": "https://plot.ly"
       },
       "data": [
        {
         "hoverinfo": "text",
         "hovertext": [
          "Quantity: 3"
         ],
         "mode": "text",
         "text": "Bin 1",
         "textfont": {
          "color": "black"
         },
         "type": "scatter",
         "x": [
          2.5
         ],
         "y": [
          -0.5
         ]
        },
        {
         "hoverinfo": "text",
         "hovertext": [
          "Quantity: 3"
         ],
         "mode": "text",
         "text": "Bin 2",
         "textfont": {
          "color": "black"
         },
         "type": "scatter",
         "x": [
          7.5
         ],
         "y": [
          -0.5
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#636EFA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 0<br>X: 0.0, Y: 2.0<br>Size: 5.0 x 8.0"
         ],
         "type": "scatter",
         "x": [
          2.5
         ],
         "y": [
          5.999999999999
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#636EFA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 0<br>X: 5.0, Y: 2.0<br>Size: 5.0 x 8.0"
         ],
         "type": "scatter",
         "x": [
          7.5
         ],
         "y": [
          5.999999999997
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#636EFA",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 0<br>X: 5.0, Y: 2.0<br>Size: 5.0 x 8.0"
         ],
         "type": "scatter",
         "x": [
          7.5
         ],
         "y": [
          5.999999999997
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 0.0, Y: -0.0<br>Size: 5.0 x 2.0"
         ],
         "type": "scatter",
         "x": [
          2.5
         ],
         "y": [
          0.999999999999
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 0.0, Y: -0.0<br>Size: 5.0 x 2.0"
         ],
         "type": "scatter",
         "x": [
          2.5
         ],
         "y": [
          0.999999999999
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 5.0, Y: 0.0<br>Size: 5.0 x 2.0"
         ],
         "type": "scatter",
         "x": [
          7.5
         ],
         "y": [
          1
         ]
        },
        {
         "hoverinfo": "text",
         "hoverlabel": {
          "bgcolor": "white",
          "bordercolor": "gray",
          "font": {
           "color": "#EF553B",
           "size": 16
          }
         },
         "marker": {
          "opacity": 0
         },
         "mode": "markers",
         "text": [
          "Case ID: 1<br>X: 5.0, Y: 0.0<br>Size: 5.0 x 2.0"
         ],
         "type": "scatter",
         "x": [
          7.5
         ],
         "y": [
          1
         ]
        }
       ],
       "layout": {
        "shapes": [
         {
          "line": {
           "color": "black",
           "width": 3
          },
          "type": "rect",
          "x0": 0,
          "x1": 5,
          "y0": 0,
          "y1": 10
         },
         {
          "line": {
           "color": "black",
           "width": 3
          },
          "type": "rect",
          "x0": 5,
          "x1": 10,
          "y0": 0,
          "y1": 10
         },
         {
          "fillcolor": "#636EFA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 0,
          "x1": 5,
          "y0": 1.999999999999,
          "y1": 9.999999999999
         },
         {
          "fillcolor": "#636EFA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 5,
          "x1": 10,
          "y0": 1.9999999999969997,
          "y1": 9.999999999997
         },
         {
          "fillcolor": "#636EFA",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 5,
          "x1": 10,
          "y0": 1.9999999999969997,
          "y1": 9.999999999997
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 0,
          "x1": 5,
          "y0": -1e-12,
          "y1": 1.999999999999
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 0,
          "x1": 5,
          "y0": -1e-12,
          "y1": 1.999999999999
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 5,
          "x1": 10,
          "y0": 0,
          "y1": 2
         },
         {
          "fillcolor": "#EF553B",
          "line": {
           "color": "RoyalBlue",
           "width": 2
          },
          "type": "rect",
          "x0": 5,
          "x1": 10,
          "y0": 0,
          "y1": 2
         }
        ],
        "showlegend": false,
        "template": {
         "data": {
          "bar": [
           {
            "error_x": {
             "color": "#2a3f5f"
            },
            "error_y": {
             "color": "#2a3f5f"
            },
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "bar"
           }
          ],
          "barpolar": [
           {
            "marker": {
             "line": {
              "color": "#E5ECF6",
              "width": 0.5
             },
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "barpolar"
           }
          ],
          "carpet": [
           {
            "aaxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "baxis": {
             "endlinecolor": "#2a3f5f",
             "gridcolor": "white",
             "linecolor": "white",
             "minorgridcolor": "white",
             "startlinecolor": "#2a3f5f"
            },
            "type": "carpet"
           }
          ],
          "choropleth": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "choropleth"
           }
          ],
          "contour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "contour"
           }
          ],
          "contourcarpet": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "contourcarpet"
           }
          ],
          "heatmap": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmap"
           }
          ],
          "heatmapgl": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "heatmapgl"
           }
          ],
          "histogram": [
           {
            "marker": {
             "pattern": {
              "fillmode": "overlay",
              "size": 10,
              "solidity": 0.2
             }
            },
            "type": "histogram"
           }
          ],
          "histogram2d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2d"
           }
          ],
          "histogram2dcontour": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "histogram2dcontour"
           }
          ],
          "mesh3d": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "type": "mesh3d"
           }
          ],
          "parcoords": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "parcoords"
           }
          ],
          "pie": [
           {
            "automargin": true,
            "type": "pie"
           }
          ],
          "scatter": [
           {
            "fillpattern": {
             "fillmode": "overlay",
             "size": 10,
             "solidity": 0.2
            },
            "type": "scatter"
           }
          ],
          "scatter3d": [
           {
            "line": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatter3d"
           }
          ],
          "scattercarpet": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattercarpet"
           }
          ],
          "scattergeo": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergeo"
           }
          ],
          "scattergl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattergl"
           }
          ],
          "scattermapbox": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scattermapbox"
           }
          ],
          "scatterpolar": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolar"
           }
          ],
          "scatterpolargl": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterpolargl"
           }
          ],
          "scatterternary": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "type": "scatterternary"
           }
          ],
          "surface": [
           {
            "colorbar": {
             "outlinewidth": 0,
             "ticks": ""
            },
            "colorscale": [
             [
              0,
              "#0d0887"
             ],
             [
              0.1111111111111111,
              "#46039f"
             ],
             [
              0.2222222222222222,
              "#7201a8"
             ],
             [
              0.3333333333333333,
              "#9c179e"
             ],
             [
              0.4444444444444444,
              "#bd3786"
             ],
             [
              0.5555555555555556,
              "#d8576b"
             ],
             [
              0.6666666666666666,
              "#ed7953"
             ],
             [
              0.7777777777777778,
              "#fb9f3a"
             ],
             [
              0.8888888888888888,
              "#fdca26"
             ],
             [
              1,
              "#f0f921"
             ]
            ],
            "type": "surface"
           }
          ],
          "table": [
           {
            "cells": {
             "fill": {
              "color": "#EBF0F8"
             },
             "line": {
              "color": "white"
             }
            },
            "header": {
             "fill": {
              "color": "#C8D4E3"
             },
             "line": {
              "color": "white"
             }
            },
            "type": "table"
           }
          ]
         },
         "layout": {
          "annotationdefaults": {
           "arrowcolor": "#2a3f5f",
           "arrowhead": 0,
           "arrowwidth": 1
          },
          "autotypenumbers": "strict",
          "coloraxis": {
           "colorbar": {
            "outlinewidth": 0,
            "ticks": ""
           }
          },
          "colorscale": {
           "diverging": [
            [
             0,
             "#8e0152"
            ],
            [
             0.1,
             "#c51b7d"
            ],
            [
             0.2,
             "#de77ae"
            ],
            [
             0.3,
             "#f1b6da"
            ],
            [
             0.4,
             "#fde0ef"
            ],
            [
             0.5,
             "#f7f7f7"
            ],
            [
             0.6,
             "#e6f5d0"
            ],
            [
             0.7,
             "#b8e186"
            ],
            [
             0.8,
             "#7fbc41"
            ],
            [
             0.9,
             "#4d9221"
            ],
            [
             1,
             "#276419"
            ]
           ],
           "sequential": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ],
           "sequentialminus": [
            [
             0,
             "#0d0887"
            ],
            [
             0.1111111111111111,
             "#46039f"
            ],
            [
             0.2222222222222222,
             "#7201a8"
            ],
            [
             0.3333333333333333,
             "#9c179e"
            ],
            [
             0.4444444444444444,
             "#bd3786"
            ],
            [
             0.5555555555555556,
             "#d8576b"
            ],
            [
             0.6666666666666666,
             "#ed7953"
            ],
            [
             0.7777777777777778,
             "#fb9f3a"
            ],
            [
             0.8888888888888888,
             "#fdca26"
            ],
            [
             1,
             "#f0f921"
            ]
           ]
          },
          "colorway": [
           "#636efa",
           "#EF553B",
           "#00cc96",
           "#ab63fa",
           "#FFA15A",
           "#19d3f3",
           "#FF6692",
           "#B6E880",
           "#FF97FF",
           "#FECB52"
          ],
          "font": {
           "color": "#2a3f5f"
          },
          "geo": {
           "bgcolor": "white",
           "lakecolor": "white",
           "landcolor": "#E5ECF6",
           "showlakes": true,
           "showland": true,
           "subunitcolor": "white"
          },
          "hoverlabel": {
           "align": "left"
          },
          "hovermode": "closest",
          "mapbox": {
           "style": "light"
          },
          "paper_bgcolor": "white",
          "plot_bgcolor": "#E5ECF6",
          "polar": {
           "angularaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "radialaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "scene": {
           "xaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "yaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           },
           "zaxis": {
            "backgroundcolor": "#E5ECF6",
            "gridcolor": "white",
            "gridwidth": 2,
            "linecolor": "white",
            "showbackground": true,
            "ticks": "",
            "zerolinecolor": "white"
           }
          },
          "shapedefaults": {
           "line": {
            "color": "#2a3f5f"
           }
          },
          "ternary": {
           "aaxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "baxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           },
           "bgcolor": "#E5ECF6",
           "caxis": {
            "gridcolor": "white",
            "linecolor": "white",
            "ticks": ""
           }
          },
          "title": {
           "x": 0.05
          },
          "xaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          },
          "yaxis": {
           "automargin": true,
           "gridcolor": "white",
           "linecolor": "white",
           "ticks": "",
           "title": {
            "standoff": 15
           },
           "zerolinecolor": "white",
           "zerolinewidth": 2
          }
         }
        },
        "xaxis": {
         "range": [
          -5,
          11
         ],
         "showgrid": false
        },
        "yaxis": {
         "range": [
          -5,
          11
         ]
        }
       }
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "best_feasible = None\n",
    "\n",
    "if QPU:\n",
    "    best_feasible = bpp.call_solver(cqm, 20)\n",
    "else:\n",
    "    # Deserialize cached solution\n",
    "    with open(cached[\"easy\"][\"s\"], \"rb\") as infile:\n",
    "        best_feasible = pickle.load(infile)\n",
    "        infile.close()\n",
    "\n",
    "fig = bpp.plot_rects(\n",
    "    best_feasible, vars, cases, bins, effective_dimensions\n",
    ")\n",
    "fig.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The number of qubits is shown here, after we map the CQM variables to quantum wires. We allocate a quantum register of size `BITS_PRECISION` to each continuous variable. Reducing this value will lower the number of qubits, at the cost of a significant impact on the accuracy of our solution. Reducing `BITS_PRECISION` may also make constraints harder to satisfy. In any case, since we are not running this code we will press on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of qubits required: 118\n",
      "Mapping CQM variables to quantum wires:\n",
      "{'o_0_0': Z(0), 'o_0_1': Z(1), 'o_1_0': Z(2), 'o_1_1': Z(3), 'o_2_0': Z(4), 'o_2_1': Z(5), 'o_3_0': Z(6), 'o_3_1': Z(7), 'case_1_in_bin_0': Z(8), 'case_1_in_bin_1': Z(9), 'case_2_in_bin_0': Z(10), 'case_2_in_bin_1': Z(11), 'case_3_in_bin_0': Z(12), 'case_3_in_bin_1': Z(13), 'sel_0_1_0': Z(14), 'sel_0_1_1': Z(15), 'sel_0_1_2': Z(16), 'sel_0_1_3': Z(17), 'sel_0_2_0': Z(18), 'sel_0_2_1': Z(19), 'sel_0_2_2': Z(20), 'sel_0_2_3': Z(21), 'sel_0_3_0': Z(22), 'sel_0_3_1': Z(23), 'sel_0_3_2': Z(24), 'sel_0_3_3': Z(25), 'sel_1_2_0': Z(26), 'sel_1_2_1': Z(27), 'sel_1_2_2': Z(28), 'sel_1_2_3': Z(29), 'sel_1_3_0': Z(30), 'sel_1_3_1': Z(31), 'sel_1_3_2': Z(32), 'sel_1_3_3': Z(33), 'sel_2_3_0': Z(34), 'sel_2_3_1': Z(35), 'sel_2_3_2': Z(36), 'sel_2_3_3': Z(37), 'x_0': Z(38) @ Z(39) @ Z(40) @ Z(41) @ Z(42) @ Z(43) @ Z(44) @ Z(45), 'x_1': Z(46) @ Z(47) @ Z(48) @ Z(49) @ Z(50) @ Z(51) @ Z(52) @ Z(53), 'y_0': Z(54) @ Z(55) @ Z(56) @ Z(57) @ Z(58) @ Z(59) @ Z(60) @ Z(61), 'y_1': Z(62) @ Z(63) @ Z(64) @ Z(65) @ Z(66) @ Z(67) @ Z(68) @ Z(69), 'x_2': Z(70) @ Z(71) @ Z(72) @ Z(73) @ Z(74) @ Z(75) @ Z(76) @ Z(77), 'y_2': Z(78) @ Z(79) @ Z(80) @ Z(81) @ Z(82) @ Z(83) @ Z(84) @ Z(85), 'x_3': Z(86) @ Z(87) @ Z(88) @ Z(89) @ Z(90) @ Z(91) @ Z(92) @ Z(93), 'y_3': Z(94) @ Z(95) @ Z(96) @ Z(97) @ Z(98) @ Z(99) @ Z(100) @ Z(101), 'upper_bound_0': Z(102) @ Z(103) @ Z(104) @ Z(105) @ Z(106) @ Z(107) @ Z(108) @ Z(109), 'upper_bound_1': Z(110) @ Z(111) @ Z(112) @ Z(113) @ Z(114) @ Z(115) @ Z(116) @ Z(117)}\n"
     ]
    }
   ],
   "source": [
    "assert(BITS_PRECISION > 1)\n",
    "\n",
    "# Mapping variables in CQM to tensor product of Pauli Z operators on wires\n",
    "wire_idx = 0\n",
    "wire_map = {}\n",
    "for v in list(cqm.variables):\n",
    "    if cqm.vartype(v) is dimod.BINARY:\n",
    "        wire_map[v] = qml.Z(wire_idx)\n",
    "        wire_idx += 1\n",
    "    elif cqm.vartype(v) is dimod.REAL:\n",
    "        op = qml.Z(wire_idx)\n",
    "        for i in range(1, BITS_PRECISION):\n",
    "            op = op @ qml.Z(wire_idx + i)\n",
    "        wire_map[v] = op\n",
    "        wire_idx += BITS_PRECISION\n",
    "\n",
    "print(f\"Number of qubits required: {wire_idx}\")\n",
    "print(f\"Mapping CQM variables to quantum wires:\\n{wire_map}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we attempt to parse the CQM into a quantum Hamiltonian. The following code is included for completeness, and is meant simply as an illustration of the kind of quantum circuit that is produced. It likely needs many significant changes, like how the LE constraints are handled, and actually using the constant term of the CQM (`const_term`) in our objective being minimized."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "coeffs = []\n",
    "ops = []\n",
    "const_term = 0\n",
    "\n",
    "def is_float(s):\n",
    "    try:\n",
    "        float(s)\n",
    "        return True\n",
    "    except ValueError:\n",
    "        return False\n",
    "\n",
    "def eqn_parser(eqn_str, coeffs, ops, const_term, is_obj=False):\n",
    "    '''\n",
    "    Implements an equation parser that combines both the objective and constraints\n",
    "    in the ``dimod.CQM``.\n",
    "    \n",
    "    Args:\n",
    "        eqn_str (string): An equation in the BQM\n",
    "        coeffs (list[float]): The coefficients array of the mixer Hamiltonian\n",
    "        ops (list[qml.Operation]): The array tensor product terms in the mixer Hamiltonian\n",
    "        const_term (float): Constant term in the overall cost function\n",
    "        is_obj (bool): \n",
    "    '''\n",
    "    # If eqn is an objective function, append RHS and proceed as usual\n",
    "    if is_obj:\n",
    "        eqn_str += \" <= 0\"\n",
    "    \n",
    "    parsed = str(eqn_str).split(\" \")\n",
    "    lhs = parsed[:-2]\n",
    "    rhs = parsed[-2:]\n",
    "    \n",
    "    # Equality constraint (one hot)\n",
    "    if rhs[0] == \"==\":\n",
    "        const_term += -1\n",
    "    \n",
    "    for i in range(len(lhs)):\n",
    "        # Parse constant\n",
    "        if is_float(lhs[i]):\n",
    "            const_term += float(lhs[i])\n",
    "        # Parse term\n",
    "        elif lhs[i] != \"-\" and lhs[i] != \"+\":\n",
    "            coeff = 1\n",
    "            if i > 0 and lhs[i-1] == \"-\": # Subtracted term\n",
    "                coeff = -1\n",
    "            if lhs[i][0] == '-':\n",
    "                lhs[i] = lhs[i][1:] # First term is negative\n",
    "                coeff = -1\n",
    "\n",
    "            tensor_terms = []\n",
    "            for term in lhs[i].split(\"*\"):\n",
    "                if term in wire_map.keys():\n",
    "                    tensor_terms.append(wire_map[term])\n",
    "                elif is_float(term):\n",
    "                    coeff *= float(term)\n",
    "            op = tensor_terms[0]\n",
    "            for j in range(1, len(tensor_terms)):\n",
    "                op = op @ tensor_terms[j]\n",
    "            \n",
    "            coeffs.append(coeff)\n",
    "            ops.append(op)\n",
    "\n",
    "# Parse CQM objective and constraints\n",
    "eqn_parser(cqm.objective.to_polystring(), coeffs, ops, const_term, True)\n",
    "for v in cqm.constraints.values():\n",
    "    eqn_parser(v, coeffs, ops, const_term)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A quantum device is created with the required number of wires (not intended to run)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "dev = qml.device(\"default.qubit\", wires=wire_idx)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The reason to use `eqn_parser` was to obtain a cost Hamiltonian $H_C$, useful to optimize the VQA. For QAOA, we use the standard mixer Hamiltonian $H_M$ (the same as `qml.qaoa.mixers.x_mixer`), a simple non-commuting sum of Pauli-X operations on each qubit. It is not clear whether this mixer is beneficial for BPP."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "cost_h = qml.Hamiltonian(coeffs, ops)\n",
    "mixer_h = qml.Hamiltonian([1] * wire_idx, [qml.PauliX(i) for i in range(wire_idx)])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a VQA ansatz we may use `qml.StronglyEntanglingLayers`, as well as the choice of either analytic gradients or gradients derived from numerical differentiation. These are used by a classical optimizer like `qml.AdamOptimizer` that sample the quantum circuit and update the parameters in a hybrid loop [[5]](#codebook)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "@qml.qnode(dev)\n",
    "def strongly_entangling_ansatz(observable,params):\n",
    "    \"\"\"Applies an ansatz with moderate entanglement.\n",
    "\n",
    "    Args:\n",
    "        observable (qml.op): a pennylane operator whose expectation value we want to measure.\n",
    "        params(np.array): an array with the trainable parameters of the ansatz. They have the shape of `qml.StronglyEntanglingLayers.shape(n_layers=1, n_wires=n_bits)`\n",
    "\n",
    "    Returns:\n",
    "        (np.tensor): a numpy tensor of 1 element corresponding to the expectation value of the given observable.\n",
    "    \"\"\"\n",
    "    qml.StronglyEntanglingLayers(weights=params, wires=range(wire_idx), ranges=[wire_idx-1])\n",
    "    return qml.expval(observable)\n",
    "\n",
    "def optimizer(observable,params):\n",
    "    \"\"\"Updates the parameters to minimize the cost function value.\n",
    "\n",
    "    Args:\n",
    "        observable (qml.Hamiltonian): a pennylane Hamiltonian whose expectation value we want to measure.\n",
    "        params(np.array): an array with the trainable parameters of the ansatz.\n",
    "\n",
    "    Returns:\n",
    "        (np.array): an array with the optimized trainable parameters.\n",
    "    \"\"\"\n",
    "    opt = qml.AdamOptimizer()\n",
    "    for _ in range(1000):\n",
    "        _, params = opt.step(strongly_entangling_ansatz, observable, params)\n",
    "    return params "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "QAOA is simply another ansatz that is useful in VQA. The following code is the quantum circuit for QAOA that uses built-in layers in `qml.qaoa.layers` which consist of repeated application of the cost and mixer layers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert(NUM_LAYERS >= 1)\n",
    "params=np.ones((NUM_LAYERS, 2),requires_grad=True) * 0.5\n",
    "\n",
    "def qaoa_layer(params,cost_h):\n",
    "    \"\"\"Implement one QAOA layer alternating H_C and H_M.\n",
    "\n",
    "    Args:\n",
    "        params (np.array): An array with the trainable parameters of the QAOA ansatz.\n",
    "        cost_h (qml.Hamiltonian): The cost Hamiltonian\n",
    "    \"\"\"  \n",
    "    qml.qaoa.layers.cost_layer(params[0], cost_h)\n",
    "    qml.qaoa.layers.mixer_layer(params[1], mixer_h)\n",
    "    \n",
    "def qaoa_circuit(params,L,cost_h):\n",
    "    \"\"\"Implement the initial state and p layers of the QAOA ansatz.\n",
    "\n",
    "    Args:\n",
    "        params (np.array): An array with the trainable parameters of the QAOA ansatz.\n",
    "        p (int): Number of layers of the QAOA ansatz.\n",
    "        cost_h (qml.Hamiltonian): The cost Hamiltonian\n",
    "    \"\"\"  \n",
    "    qml.Hadamard(0)\n",
    "    for i in range(L):\n",
    "        qaoa_layer(params[i],cost_h)\n",
    "    \n",
    "@qml.qnode(dev)\n",
    "def probability_circuit(params,cost_h):\n",
    "    \"\"\"QAOA circuit which returns the probabilities.\n",
    "    Args:\n",
    "        params (np.array): An array with the trainable parameters of the QAOA ansatz.\n",
    "        p (int): Number of layers of the QAOA ansatz.\n",
    "        cost_h (qml.Hamiltonian): The cost Hamiltonian\n",
    "    Returns:\n",
    "        (np.tensor): A tensor with the probabilities of measuring the quantum states.\n",
    "    \"\"\"  \n",
    "    qaoa_circuit(params,NUM_LAYERS,cost_h)\n",
    "    return qml.probs(wires=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "<a id=\"openqaoa\"></a>\n",
    "[1] OpenQAOA: https://openqaoa.entropicalabs.com/problems/bin-packing/\n",
    "\n",
    "<a id=\"dwave3d\"></a>\n",
    "[2] 3D Bin Packing sample: https://github.dev/dwave-examples/3d-bin-packing\n",
    "\n",
    "<a id=\"ocean\"></a>\n",
    "[3] Ocean Programs for Beginners: https://www.dwavesys.com/media/fmtj2fw3/20210920_ofbguide.pdf\n",
    "\n",
    "<a id=\"dwavewp\"></a>\n",
    "[4] Problem Formulation Guide: https://www.dwavesys.com/media/bu0lh5ee/problem-formulation-guide-2022-01-10.pdf\n",
    "\n",
    "<a id=\"codebook\"></a>\n",
    "[5] PennyLane Codebook: https://pennylane.ai/codebook"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pl",
   "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.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}