Logistics_Use_Case_multiple_Trucks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Latex macros\n",
    "$\n",
    "\\newcommand{\\R}{\\mathbb{R}}\n",
    "\\newcommand{\\C}{\\mathbb{C}}\n",
    "\\newcommand{\\bfb}{\\mathbf{b}}\n",
    "\\newcommand{\\bfr}{\\mathbf{r}}\n",
    "%\n",
    "\\newcommand{\\bfA}{\\mathbf{A}}\n",
    "\\newcommand{\\bfQ}{\\mathbf{Q}}\n",
    "%\n",
    "\\newcommand{\\HP}{\\mathcal{C}}\n",
    "\\newcommand{\\HM}{\\mathcal{B}}\n",
    "%\n",
    "\\newcommand{\\ket}[1]{\\left\\vert #1 \\right\\rangle}\n",
    "\\newcommand{\\bra}[1]{\\left\\langle #1 \\right\\vert}\n",
    "\\newcommand{\\braket}[1]{\\left\\langle #1 \\right\\rangle}\n",
    "\\newcommand{\\pmat}[1]{\\begin{pmatrix}#1\\end{pmatrix}}\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Use Case: Optimization of Vehicle Routing for a PickUpDeliveryProblem  <a class=\"tocSkip\"/>\n",
    "Dr. Florian Knäble, Fraunhofer IAO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Step 1: Find an appropriate problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The Vehicle Routing Problem for a PickUpDelivery Problem with time windows**\n",
    "\n",
    "- looking for an optimal subdivision of a given number of pickup and delivery tours for a given number of trucks \n",
    "- restrictions on daily driving times for every single truck\n",
    "- restrictions on time windows outside which pickups or deliveries cannot be made\n",
    "- time horizon for a whole week\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reduction a to proof-of-concept model\n",
    "\n",
    "- no time restrictions whatsoever\n",
    "- number of tours and trucks must be kept minimal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Given**\n",
    "- number of tours (each with a pickup and with a delivery location)\n",
    "- number of trucks (each with their own depot where they have to start and end their journey)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Aim**\n",
    "- minimize distances driven outside of actual PickUp-Delivery runs (those cannot be helped anyhow)   \"Leerkilometer minimieren\" \n",
    "- all PickUp-Delivery tours must be served\n",
    "- trucks must start and end at depots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Example with two trucks**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/Tourplanning_Problem.PNG\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Depots are given in green and red\n",
    "- Attention: each tour (with actually two locations is represented by a single location)\n",
    "- This abstraction is possible, but the distances between tours are then not symmetric anymore "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Distance Matrix**\n",
    "\n",
    "- distances between all possible locations are noted down\n",
    "- as said above, these are not necessarily symmetric\n",
    "- locations are given by coordinates and distances are calculated by a suitable metric (e.g. $l_1$ or $l_2$)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/distance__matrix.PNG\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Cost function (\"Leerkilometer\") is calculated by adding up the costs of all connecting rides:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/cost__function.PNG\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Binary Encoding**\n",
    "- For the Quantum Computer we have to cast our problem into the form of a binary quadratic problem.\n",
    "- Therefore we represent the order in which tours are visited by a permutation matrix \n",
    "(which has per definition binary entries)\n",
    "- To encode the order of $n$ tours for one truck, we need then $n^2$ Qubits\n",
    "- In the case of several trucks this number is multiplied with the number of trucks (we need a full permutation matrix for each truck)\n",
    "- thus if $X$ is the permutation matrix. then $x_{ij}=1$ would mean that tour number $i$ is served at position $j$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/permutation_matrix.PNG\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Quadratic Problem**\n",
    "- in this encoding we can represent the cost function $f$ to be minimized by a quadratic function in the binary variables \n",
    "- we also need restrictions to ensure that all tours are served, otherwise the zero matrix would provide a possible solution with zero cost\n",
    "- thus we require that every row contains exactly a single one\n",
    "- we also require that every column contains exactly a single one -> the truck cannot be at two locations at the same time, we need an ordering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/quadratic_single_truck.PNG\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the case of several trucks, the formula for the cost function becomes even more cumbersome.\n",
    "Here, $x_{ijk}=1$ means that tour number $i$ is served at position $j$ by truck number $k$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/quadratic_multi_truck.PNG\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Luckily, python will do these calculations for us...\n",
    "The important point is, that if we consider the matrix $x_{ij}$ or the tensor $x_{ijk}$ as a $N\\times N \\times K$-dimensional vector $\\vec{x}$ by joining the matrix rows, then we can write the above $f$ as $f(x)= x^TAx$ for some quadratic Matrix $A$ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Step 2 The Proof-of-Concept Model in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "import pickle\n",
    "from typing import List\n",
    "import numpy as np\n",
    "from qiskit_optimization import QuadraticProgram\n",
    "from qiskit_optimization.converters import QuadraticProgramConverter, LinearEqualityToPenalty\n",
    "from qiskit_optimization.algorithms import CplexOptimizer\n",
    "\n",
    "class Location():\n",
    "    def __init__(self,x:float,y:float):\n",
    "        self.x=x\n",
    "        self.y=y   \n",
    "    \n",
    "    def print(self):\n",
    "        print(f\"Location at point ({self.x},{self.y})\")\n",
    "\n",
    "class Tour():\n",
    "    def __init__(self, pickup, delivery, name):\n",
    "        self.pickupLocation=pickup\n",
    "        self.deliveryLocation=delivery\n",
    "        self.name=name\n",
    "\n",
    "class Truck():\n",
    "    def __init__(self, depot: Tour, name:str):\n",
    "        self.depot=depot\n",
    "        self.name=name\n",
    "    def print(self):\n",
    "        print(f\"Truck {self.name} at depot {self.depot.name} at {self.depot.pickupLocation.print()}\")\n",
    "\n",
    "\n",
    "class PickUpDeliveryProblem():\n",
    "    def __init__(self, tours: List, trucks:List, name: str):\n",
    "        self.name=name\n",
    "        self.truckList=trucks\n",
    "        self.numberOfTrucks=len(trucks)\n",
    "        self.tourList=tours\n",
    "        self.numberOfTours=len(tours)\n",
    "        self.adjacencymatrix = []\n",
    "        self.constraint_matrix = []\n",
    "        self.cost_matrix = []\n",
    "        self.constraint_vector = [] \n",
    "        \n",
    "        self.generate_adjacency_matrix()\n",
    "        self.generate_constraint_matrix()\n",
    "        self.generate_cost_matrix()\n",
    "        self.generate_constraint_vector()\n",
    "    \n",
    "    # any sensible distance could be used here\n",
    "    def distance(self, a:Location, b:Location):\n",
    "        return abs(a.x-b.x) + abs(a.y-b.y)\n",
    "    \n",
    "    # connects the endpoint of the first tour with the starting point of the second tour\n",
    "    def leerkilometer(self, a:Tour, b:Tour):\n",
    "        return self.distance(a.deliveryLocation, b.pickupLocation)\n",
    "\n",
    "    # This is the distance matrix D_ij from above\n",
    "    def generate_adjacency_matrix(self) -> np.ndarray:\n",
    "        self.adjacencymatrix = np.zeros((self.numberOfTours,self.numberOfTours))\n",
    "        for count1, tour1 in enumerate(self.tourList):\n",
    "            for count2, tour2 in enumerate(self.tourList):\n",
    "                self.adjacencymatrix[count1][count2]=self.leerkilometer(tour1, tour2)\n",
    "\n",
    "    # This is the matrix A from above for the formulation as a quadratic problem\n",
    "    def generate_cost_matrix(self)-> np.ndarray:\n",
    "        n=self.numberOfTours\n",
    "        self.cost_matrix = np.zeros((n*n*self.numberOfTrucks,n*n*self.numberOfTrucks))\n",
    "        for truck in range(0,self.numberOfTrucks):\n",
    "            for i in range(n*n*truck, n*n*(truck +1)):\n",
    "                tour_i,time_i = divmod(i,n)\n",
    "                tour_i= tour_i - n*truck\n",
    "\n",
    "                # Leerfahrten von/zum Depot\n",
    "                if time_i==0:\n",
    "                    self.cost_matrix[i][i]=self.leerkilometer(self.truckList[truck].depot, self.tourList[tour_i])\n",
    "                if time_i==n-1:\n",
    "                    self.cost_matrix[i][i]=self.leerkilometer(self.tourList[tour_i],self.truckList[truck].depot)\n",
    "\n",
    "                # Leerfahrten innerhalb mehrerer Touren eines LKW\n",
    "                for j in range(i,n*n*(truck +1)):\n",
    "                    tour_j,time_j = divmod(j,n)\n",
    "                    tour_j = tour_j - n*truck\n",
    "                    if time_j == (time_i+1):\n",
    "                        self.cost_matrix[i][j]=self.adjacencymatrix[tour_i][tour_j]\n",
    "                    if time_i == (time_j+1):\n",
    "                        self.cost_matrix[i][j]=self.adjacencymatrix[tour_j][tour_i]\n",
    "\n",
    "                # Tourende eines LKW und Touranfang eines anderen mit entsprechenden Depot-Leerfahrten  \n",
    "                for j in range(n*n*(truck +1),n*n*self.numberOfTrucks):\n",
    "                    truck_j, _ = divmod(j,n*n)  \n",
    "                    tour_j,time_j = divmod(j,n)\n",
    "                    tour_j = tour_j - n*truck_j\n",
    "                    if time_j == (time_i+1):\n",
    "                        self.cost_matrix[i][j]=self.leerkilometer(self.tourList[tour_i],self.truckList[truck].depot) + self.leerkilometer(self.truckList[truck_j].depot,self.tourList[tour_j])\n",
    "                    if time_i == (time_j+1):\n",
    "                        self.cost_matrix[i][j]=self.leerkilometer(self.tourList[tour_j],self.truckList[truck_j].depot) + self.leerkilometer(self.truckList[truck].depot,self.tourList[tour_i])\n",
    "\n",
    "    # here the constraint matrix C to ensure we have an actual permutation matrix is generated\n",
    "    def generate_constraint_matrix(self)-> np.ndarray:\n",
    "        n=self.numberOfTours\n",
    "        self.constraint_matrix = np.zeros((2*n,n*n*self.numberOfTrucks))\n",
    "        for row_index in range(0, n):\n",
    "            for truck in range(0, self.numberOfTrucks):\n",
    "                offset = row_index * n\n",
    "                self.constraint_matrix[row_index, offset + n*n*truck :offset + n + n*n*truck] = 1\n",
    "\n",
    "        for row_index in range(n, 2* n):\n",
    "            offset = row_index - self.numberOfTours\n",
    "            for col_index in range(0, n * self.numberOfTrucks):\n",
    "                self.constraint_matrix[row_index, n * col_index + offset] = 1\n",
    "    \n",
    "    # here the constraint righthandside e to ensure we have an actual permutation matrix is generated: Cx=e\n",
    "    def generate_constraint_vector(self)-> np.ndarray:\n",
    "        self.constraint_vector = np.ones(2* self.numberOfTours)\n",
    "\n",
    "\n",
    "    # this function translates A, C and e into the quadratic problem for x\n",
    "    def generate_Quadratic_Program(self, name:str) -> QuadraticProgram:\n",
    "\n",
    "        qp=QuadraticProgram(name)\n",
    "        for truck in self.truckList:\n",
    "            for tour in self.tourList:\n",
    "                qp.binary_var_list(\n",
    "                    keys=[ f\"{tour.name}_at_Position_{t}_served_by_{truck.name}\" for t in range(1, self.numberOfTours +1 ) ],\n",
    "                    name=\"\"\n",
    "                )\n",
    "\n",
    "        \n",
    "        for row_index in range(0, self.constraint_matrix.shape[0]):\n",
    "            qp.linear_constraint(\n",
    "                linear=self.constraint_matrix[row_index, :],\n",
    "                rhs=self.constraint_vector[row_index],\n",
    "                sense=\"==\",\n",
    "                name = f\"row_{row_index} sums to one\")\n",
    "\n",
    "        qp.minimize(quadratic = self.cost_matrix)\n",
    "            \n",
    "        return qp\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**An Example with a single truck**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "class PDPExample1(PickUpDeliveryProblem):\n",
    "    def __init__(self):\n",
    "        trucklist=[]\n",
    "        depot=Tour(Location(0,0),Location(0,0),\"depot1\")\n",
    "        trucklist.append(Truck(depot, \"truck1\"))\n",
    "        \n",
    "        tourlist=[]\n",
    "        tourlist.append(Tour(Location(2,3), Location(3,2), \"tour1\"))\n",
    "        tourlist.append(Tour(Location(0,0), Location(2,3), \"tour2\"))\n",
    "        tourlist.append(Tour(Location(3,3), Location(0,4), \"tour3\"))\n",
    "        super().__init__(tourlist, trucklist, \"1Truck_3Tours\")\n",
    "\n",
    "\n",
    "pdp1=PDPExample1()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images\\one_truck_problem2.png\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[5. 2. 0. 0. 5. 0. 0. 1. 0.]\n",
      " [0. 0. 2. 0. 0. 5. 3. 0. 1.]\n",
      " [0. 0. 5. 0. 0. 0. 0. 3. 0.]\n",
      " [0. 0. 0. 0. 5. 0. 0. 1. 0.]\n",
      " [0. 0. 0. 0. 0. 5. 4. 0. 1.]\n",
      " [0. 0. 0. 0. 0. 5. 0. 4. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 6. 4. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 4.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 4.]]\n"
     ]
    }
   ],
   "source": [
    "print(pdp1.cost_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1. 1. 1. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 1. 1. 1. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 1. 1. 1.]\n",
      " [1. 0. 0. 1. 0. 0. 1. 0. 0.]\n",
      " [0. 1. 0. 0. 1. 0. 0. 1. 0.]\n",
      " [0. 0. 1. 0. 0. 1. 0. 0. 1.]]\n"
     ]
    }
   ],
   "source": [
    "pdp1=PDPExample1()\n",
    "print(pdp1.constraint_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-- cannot find parameters matching version: 22.1.0.0, using: 20.1.0.0\n",
      "Warning: An error occurred while setting parameter 'distmip.rampup.dettimelimit' (id: 2164) to value 1e+75: 'CPLEX Error  1013: Bad parameter number to CPLEX parameter routine.' - ignored\n",
      "Warning: An error occurred while setting parameter 'distmip.rampup.duration' (id: 2163) to value 0: 'CPLEX Error  1013: Bad parameter number to CPLEX parameter routine.' - ignored\n",
      "Warning: An error occurred while setting parameter 'distmip.rampup.timelimit' (id: 2165) to value 1e+75: 'CPLEX Error  1013: Bad parameter number to CPLEX parameter routine.' - ignored\n",
      "minimum point: p_min =  [0. 1. 0. 1. 0. 0. 0. 0. 1.]\n",
      "minimum value: f_1(p_min) =  5.0\n",
      "Q = \n",
      " [[5. 2. 0. 0. 5. 0. 0. 1. 0.]\n",
      " [0. 0. 2. 0. 0. 5. 3. 0. 1.]\n",
      " [0. 0. 5. 0. 0. 0. 0. 3. 0.]\n",
      " [0. 0. 0. 0. 5. 0. 0. 1. 0.]\n",
      " [0. 0. 0. 0. 0. 5. 4. 0. 1.]\n",
      " [0. 0. 0. 0. 0. 5. 0. 4. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 6. 4. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 4.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 4.]]\n"
     ]
    }
   ],
   "source": [
    "pdp1=PDPExample1()\n",
    "qp=pdp1.generate_Quadratic_Program(\"QP\")\n",
    "\n",
    "\n",
    "#print(qp)\n",
    "cplex_optimizer = CplexOptimizer()\n",
    "\n",
    "qcio_minimization_result = cplex_optimizer.solve(qp)\n",
    "\n",
    "print(\"minimum point: p_min = \", qcio_minimization_result.x)\n",
    "print(\"minimum value: f_1(p_min) = \", qcio_minimization_result.fval)\n",
    "\n",
    "optimal_value= qcio_minimization_result.fval\n",
    "print(\"Q = \\n\", qp.objective.quadratic.to_array())\n",
    "#print(qp.binary_var_list)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The minimum x-value in vector notation [0 1 0 1 0 0 0 0 1]\n",
    "translates to the permutation matrix:\n",
    "\n",
    "$\\left( \\begin{array}{rrr}\n",
    "0 & 1 & 0 \\\\ \n",
    "1 & 0 & 0 \\\\\n",
    "0 & 0 & 1 \\\\ \n",
    "\\end{array}\\right)$\n",
    " This means we start with tour 2, then tour 1, then tour 3.\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images\\one_truck_problem2.PNG\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**An Example with two trucks and three tours** "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PDPExample2(PickUpDeliveryProblem):\n",
    "    def __init__(self):\n",
    "        trucklist=[]\n",
    "        depot1=Tour(Location(4,2),Location(4,2),\"depot1\")\n",
    "        trucklist.append(Truck(depot1, \"truck1\"))\n",
    "        depot2=Tour(Location(0,0),Location(0,0),\"depot2\")\n",
    "        trucklist.append(Truck(depot2, \"truck2\"))\n",
    "        \n",
    "        tourlist=[]\n",
    "        tourlist.append(Tour(Location(0,1), Location(2,1), \"tour1\"))\n",
    "        tourlist.append(Tour(Location(4,3), Location(2,3), \"tour2\"))\n",
    "        tourlist.append(Tour(Location(3,0), Location(1,0), \"tour3\"))\n",
    "        super().__init__(tourlist, trucklist, \"2Trucks_3Tours\")\n",
    "\n",
    "pdp2=PDPExample2()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/two_trucks_problem5.png\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 5.  2.  0.  0.  4.  0.  0.  2.  0.  0.  4.  0.  0. 10.  0.  0.  6.  0.]\n",
      " [ 0.  0.  2.  4.  0.  4.  2.  0.  2.  8.  0.  4. 10.  0. 10.  6.  0.  6.]\n",
      " [ 0.  0.  3.  0.  4.  0.  0.  2.  0.  0.  8.  0.  0. 10.  0.  0.  6.  0.]\n",
      " [ 0.  0.  0.  1.  2.  0.  0.  4.  0.  0.  4.  0.  0. 10.  0.  0.  6.  0.]\n",
      " [ 0.  0.  0.  0.  0.  2.  6.  0.  4.  4.  0.  4.  6.  0. 10.  2.  0.  6.]\n",
      " [ 0.  0.  0.  0.  0.  3.  0.  6.  0.  0.  4.  0.  0.  6.  0.  0.  2.  0.]\n",
      " [ 0.  0.  0.  0.  0.  0.  3.  2.  0.  0.  6.  0.  0. 12.  0.  0.  8.  0.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  2.  6.  0.  6.  8.  0. 12.  4.  0.  8.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  5.  0.  6.  0.  0.  8.  0.  0.  4.  0.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  1.  2.  0.  0.  4.  0.  0.  2.  0.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  2.  4.  0.  4.  2.  0.  2.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  3.  0.  4.  0.  0.  2.  0.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  7.  2.  0.  0.  4.  0.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  2.  6.  0.  4.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  5.  0.  6.  0.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  3.  2.  0.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  2.]\n",
      " [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  1.]]\n"
     ]
    }
   ],
   "source": [
    "print(pdp2.cost_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1. 1. 1. 0. 0. 0. 0. 0. 0. 1. 1. 1. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 1. 1. 1. 0. 0. 0. 0. 0. 0. 1. 1. 1. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 1. 1. 1. 0. 0. 0. 0. 0. 0. 1. 1. 1.]\n",
      " [1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0.]\n",
      " [0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0.]\n",
      " [0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1. 0. 0. 1.]]\n"
     ]
    }
   ],
   "source": [
    "print(pdp2.constraint_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-- cannot find parameters matching version: 22.1.0.0, using: 20.1.0.0\n",
      "Warning: An error occurred while setting parameter 'distmip.rampup.dettimelimit' (id: 2164) to value 1e+75: 'CPLEX Error  1013: Bad parameter number to CPLEX parameter routine.' - ignored\n",
      "Warning: An error occurred while setting parameter 'distmip.rampup.duration' (id: 2163) to value 0: 'CPLEX Error  1013: Bad parameter number to CPLEX parameter routine.' - ignored\n",
      "Warning: An error occurred while setting parameter 'distmip.rampup.timelimit' (id: 2165) to value 1e+75: 'CPLEX Error  1013: Bad parameter number to CPLEX parameter routine.' - ignored\n",
      "minimum point: p_min =  [0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 1.]\n",
      "minimum value: f_1(p_min) =  8.0\n",
      "<bound method QuadraticProgram.binary_var_list of \\ This file has been generated by DOcplex\n",
      "\\ ENCODING=ISO-8859-1\n",
      "\\Problem name: QP\n",
      "\n",
      "Minimize\n",
      " obj: [ 10 tour1_at_Position_1_served_by_truck1^2\n",
      "      + 4 tour1_at_Position_1_served_by_truck1*tour1_at_Position_2_served_by_truck1\n",
      "      + 8 tour1_at_Position_1_served_by_truck1*tour2_at_Position_2_served_by_truck1\n",
      "      + 4 tour1_at_Position_1_served_by_truck1*tour3_at_Position_2_served_by_truck1\n",
      "      + 8 tour1_at_Position_1_served_by_truck1*tour1_at_Position_2_served_by_truck2\n",
      "      + 20 tour1_at_Position_1_served_by_truck1*tour2_at_Position_2_served_by_truck2\n",
      "      + 12 tour1_at_Position_1_served_by_truck1*tour3_at_Position_2_served_by_truck2\n",
      "      + 4 tour1_at_Position_2_served_by_truck1*tour1_at_Position_3_served_by_truck1\n",
      "      + 8 tour1_at_Position_2_served_by_truck1*tour2_at_Position_1_served_by_truck1\n",
      "      + 8 tour1_at_Position_2_served_by_truck1*tour2_at_Position_3_served_by_truck1\n",
      "      + 4 tour1_at_Position_2_served_by_truck1*tour3_at_Position_1_served_by_truck1\n",
      "      + 4 tour1_at_Position_2_served_by_truck1*tour3_at_Position_3_served_by_truck1\n",
      "      + 16 tour1_at_Position_2_served_by_truck1*tour1_at_Position_1_served_by_truck2\n",
      "      + 8 tour1_at_Position_2_served_by_truck1*tour1_at_Position_3_served_by_truck2\n",
      "      + 20 tour1_at_Position_2_served_by_truck1*tour2_at_Position_1_served_by_truck2\n",
      "      + 20 tour1_at_Position_2_served_by_truck1*tour2_at_Position_3_served_by_truck2\n",
      "      + 12 tour1_at_Position_2_served_by_truck1*tour3_at_Position_1_served_by_truck2\n",
      "      + 12 tour1_at_Position_2_served_by_truck1*tour3_at_Position_3_served_by_truck2\n",
      "      + 6 tour1_at_Position_3_served_by_truck1^2\n",
      "      + 8 tour1_at_Position_3_served_by_truck1*tour2_at_Position_2_served_by_truck1\n",
      "      + 4 tour1_at_Position_3_served_by_truck1*tour3_at_Position_2_served_by_truck1\n",
      "      + 16 tour1_at_Position_3_served_by_truck1*tour1_at_Position_2_served_by_truck2\n",
      "      + 20 tour1_at_Position_3_served_by_truck1*tour2_at_Position_2_served_by_truck2\n",
      "      + 12 tour1_at_Position_3_served_by_truck1*tour3_at_Position_2_served_by_truck2\n",
      "      + 2 tour2_at_Position_1_served_by_truck1^2\n",
      "      + 4 tour2_at_Position_1_served_by_truck1*tour2_at_Position_2_served_by_truck1\n",
      "      + 8 tour2_at_Position_1_served_by_truck1*tour3_at_Position_2_served_by_truck1\n",
      "      + 8 tour2_at_Position_1_served_by_truck1*tour1_at_Position_2_served_by_truck2\n",
      "      + 20 tour2_at_Position_1_served_by_truck1*tour2_at_Position_2_served_by_truck2\n",
      "      + 12 tour2_at_Position_1_served_by_truck1*tour3_at_Position_2_served_by_truck2\n",
      "      + 4 tour2_at_Position_2_served_by_truck1*tour2_at_Position_3_served_by_truck1\n",
      "      + 12 tour2_at_Position_2_served_by_truck1*tour3_at_Position_1_served_by_truck1\n",
      "      + 8 tour2_at_Position_2_served_by_truck1*tour3_at_Position_3_served_by_truck1\n",
      "      + 8 tour2_at_Position_2_served_by_truck1*tour1_at_Position_1_served_by_truck2\n",
      "      + 8 tour2_at_Position_2_served_by_truck1*tour1_at_Position_3_served_by_truck2\n",
      "      + 12 tour2_at_Position_2_served_by_truck1*tour2_at_Position_1_served_by_truck2\n",
      "      + 20 tour2_at_Position_2_served_by_truck1*tour2_at_Position_3_served_by_truck2\n",
      "      + 4 tour2_at_Position_2_served_by_truck1*tour3_at_Position_1_served_by_truck2\n",
      "      + 12 tour2_at_Position_2_served_by_truck1*tour3_at_Position_3_served_by_truck2\n",
      "      + 6 tour2_at_Position_3_served_by_truck1^2\n",
      "      + 12 tour2_at_Position_3_served_by_truck1*tour3_at_Position_2_served_by_truck1\n",
      "      + 8 tour2_at_Position_3_served_by_truck1*tour1_at_Position_2_served_by_truck2\n",
      "      + 12 tour2_at_Position_3_served_by_truck1*tour2_at_Position_2_served_by_truck2\n",
      "      + 4 tour2_at_Position_3_served_by_truck1*tour3_at_Position_2_served_by_truck2\n",
      "      + 6 tour3_at_Position_1_served_by_truck1^2\n",
      "      + 4 tour3_at_Position_1_served_by_truck1*tour3_at_Position_2_served_by_truck1\n",
      "      + 12 tour3_at_Position_1_served_by_truck1*tour1_at_Position_2_served_by_truck2\n",
      "      + 24 tour3_at_Position_1_served_by_truck1*tour2_at_Position_2_served_by_truck2\n",
      "      + 16 tour3_at_Position_1_served_by_truck1*tour3_at_Position_2_served_by_truck2\n",
      "      + 4 tour3_at_Position_2_served_by_truck1*tour3_at_Position_3_served_by_truck1\n",
      "      + 12 tour3_at_Position_2_served_by_truck1*tour1_at_Position_1_served_by_truck2\n",
      "      + 12 tour3_at_Position_2_served_by_truck1*tour1_at_Position_3_served_by_truck2\n",
      "      + 16 tour3_at_Position_2_served_by_truck1*tour2_at_Position_1_served_by_truck2\n",
      "      + 24 tour3_at_Position_2_served_by_truck1*tour2_at_Position_3_served_by_truck2\n",
      "      + 8 tour3_at_Position_2_served_by_truck1*tour3_at_Position_1_served_by_truck2\n",
      "      + 16 tour3_at_Position_2_served_by_truck1*tour3_at_Position_3_served_by_truck2\n",
      "      + 10 tour3_at_Position_3_served_by_truck1^2\n",
      "      + 12 tour3_at_Position_3_served_by_truck1*tour1_at_Position_2_served_by_truck2\n",
      "      + 16 tour3_at_Position_3_served_by_truck1*tour2_at_Position_2_served_by_truck2\n",
      "      + 8 tour3_at_Position_3_served_by_truck1*tour3_at_Position_2_served_by_truck2\n",
      "      + 2 tour1_at_Position_1_served_by_truck2^2\n",
      "      + 4 tour1_at_Position_1_served_by_truck2*tour1_at_Position_2_served_by_truck2\n",
      "      + 8 tour1_at_Position_1_served_by_truck2*tour2_at_Position_2_served_by_truck2\n",
      "      + 4 tour1_at_Position_1_served_by_truck2*tour3_at_Position_2_served_by_truck2\n",
      "      + 4 tour1_at_Position_2_served_by_truck2*tour1_at_Position_3_served_by_truck2\n",
      "      + 8 tour1_at_Position_2_served_by_truck2*tour2_at_Position_1_served_by_truck2\n",
      "      + 8 tour1_at_Position_2_served_by_truck2*tour2_at_Position_3_served_by_truck2\n",
      "      + 4 tour1_at_Position_2_served_by_truck2*tour3_at_Position_1_served_by_truck2\n",
      "      + 4 tour1_at_Position_2_served_by_truck2*tour3_at_Position_3_served_by_truck2\n",
      "      + 6 tour1_at_Position_3_served_by_truck2^2\n",
      "      + 8 tour1_at_Position_3_served_by_truck2*tour2_at_Position_2_served_by_truck2\n",
      "      + 4 tour1_at_Position_3_served_by_truck2*tour3_at_Position_2_served_by_truck2\n",
      "      + 14 tour2_at_Position_1_served_by_truck2^2\n",
      "      + 4 tour2_at_Position_1_served_by_truck2*tour2_at_Position_2_served_by_truck2\n",
      "      + 8 tour2_at_Position_1_served_by_truck2*tour3_at_Position_2_served_by_truck2\n",
      "      + 4 tour2_at_Position_2_served_by_truck2*tour2_at_Position_3_served_by_truck2\n",
      "      + 12 tour2_at_Position_2_served_by_truck2*tour3_at_Position_1_served_by_truck2\n",
      "      + 8 tour2_at_Position_2_served_by_truck2*tour3_at_Position_3_served_by_truck2\n",
      "      + 10 tour2_at_Position_3_served_by_truck2^2\n",
      "      + 12 tour2_at_Position_3_served_by_truck2*tour3_at_Position_2_served_by_truck2\n",
      "      + 6 tour3_at_Position_1_served_by_truck2^2\n",
      "      + 4 tour3_at_Position_1_served_by_truck2*tour3_at_Position_2_served_by_truck2\n",
      "      + 4 tour3_at_Position_2_served_by_truck2*tour3_at_Position_3_served_by_truck2\n",
      "      + 2 tour3_at_Position_3_served_by_truck2^2 ]/2\n",
      "Subject To\n",
      " row_0_sums_to_one: tour1_at_Position_1_served_by_truck1\n",
      "                    + tour1_at_Position_2_served_by_truck1\n",
      "                    + tour1_at_Position_3_served_by_truck1\n",
      "                    + tour1_at_Position_1_served_by_truck2\n",
      "                    + tour1_at_Position_2_served_by_truck2\n",
      "                    + tour1_at_Position_3_served_by_truck2 = 1\n",
      " row_1_sums_to_one: tour2_at_Position_1_served_by_truck1\n",
      "                    + tour2_at_Position_2_served_by_truck1\n",
      "                    + tour2_at_Position_3_served_by_truck1\n",
      "                    + tour2_at_Position_1_served_by_truck2\n",
      "                    + tour2_at_Position_2_served_by_truck2\n",
      "                    + tour2_at_Position_3_served_by_truck2 = 1\n",
      " row_2_sums_to_one: tour3_at_Position_1_served_by_truck1\n",
      "                    + tour3_at_Position_2_served_by_truck1\n",
      "                    + tour3_at_Position_3_served_by_truck1\n",
      "                    + tour3_at_Position_1_served_by_truck2\n",
      "                    + tour3_at_Position_2_served_by_truck2\n",
      "                    + tour3_at_Position_3_served_by_truck2 = 1\n",
      " row_3_sums_to_one: tour1_at_Position_1_served_by_truck1\n",
      "                    + tour2_at_Position_1_served_by_truck1\n",
      "                    + tour3_at_Position_1_served_by_truck1\n",
      "                    + tour1_at_Position_1_served_by_truck2\n",
      "                    + tour2_at_Position_1_served_by_truck2\n",
      "                    + tour3_at_Position_1_served_by_truck2 = 1\n",
      " row_4_sums_to_one: tour1_at_Position_2_served_by_truck1\n",
      "                    + tour2_at_Position_2_served_by_truck1\n",
      "                    + tour3_at_Position_2_served_by_truck1\n",
      "                    + tour1_at_Position_2_served_by_truck2\n",
      "                    + tour2_at_Position_2_served_by_truck2\n",
      "                    + tour3_at_Position_2_served_by_truck2 = 1\n",
      " row_5_sums_to_one: tour1_at_Position_3_served_by_truck1\n",
      "                    + tour2_at_Position_3_served_by_truck1\n",
      "                    + tour3_at_Position_3_served_by_truck1\n",
      "                    + tour1_at_Position_3_served_by_truck2\n",
      "                    + tour2_at_Position_3_served_by_truck2\n",
      "                    + tour3_at_Position_3_served_by_truck2 = 1\n",
      "\n",
      "Bounds\n",
      " 0 <= tour1_at_Position_1_served_by_truck1 <= 1\n",
      " 0 <= tour1_at_Position_2_served_by_truck1 <= 1\n",
      " 0 <= tour1_at_Position_3_served_by_truck1 <= 1\n",
      " 0 <= tour2_at_Position_1_served_by_truck1 <= 1\n",
      " 0 <= tour2_at_Position_2_served_by_truck1 <= 1\n",
      " 0 <= tour2_at_Position_3_served_by_truck1 <= 1\n",
      " 0 <= tour3_at_Position_1_served_by_truck1 <= 1\n",
      " 0 <= tour3_at_Position_2_served_by_truck1 <= 1\n",
      " 0 <= tour3_at_Position_3_served_by_truck1 <= 1\n",
      " 0 <= tour1_at_Position_1_served_by_truck2 <= 1\n",
      " 0 <= tour1_at_Position_2_served_by_truck2 <= 1\n",
      " 0 <= tour1_at_Position_3_served_by_truck2 <= 1\n",
      " 0 <= tour2_at_Position_1_served_by_truck2 <= 1\n",
      " 0 <= tour2_at_Position_2_served_by_truck2 <= 1\n",
      " 0 <= tour2_at_Position_3_served_by_truck2 <= 1\n",
      " 0 <= tour3_at_Position_1_served_by_truck2 <= 1\n",
      " 0 <= tour3_at_Position_2_served_by_truck2 <= 1\n",
      " 0 <= tour3_at_Position_3_served_by_truck2 <= 1\n",
      "\n",
      "Binaries\n",
      " tour1_at_Position_1_served_by_truck1 tour1_at_Position_2_served_by_truck1\n",
      " tour1_at_Position_3_served_by_truck1 tour2_at_Position_1_served_by_truck1\n",
      " tour2_at_Position_2_served_by_truck1 tour2_at_Position_3_served_by_truck1\n",
      " tour3_at_Position_1_served_by_truck1 tour3_at_Position_2_served_by_truck1\n",
      " tour3_at_Position_3_served_by_truck1 tour1_at_Position_1_served_by_truck2\n",
      " tour1_at_Position_2_served_by_truck2 tour1_at_Position_3_served_by_truck2\n",
      " tour2_at_Position_1_served_by_truck2 tour2_at_Position_2_served_by_truck2\n",
      " tour2_at_Position_3_served_by_truck2 tour3_at_Position_1_served_by_truck2\n",
      " tour3_at_Position_2_served_by_truck2 tour3_at_Position_3_served_by_truck2\n",
      "End\n",
      ">\n"
     ]
    }
   ],
   "source": [
    "qp=pdp2.generate_Quadratic_Program(\"QP\")\n",
    "cplex_optimizer = CplexOptimizer()\n",
    "qcio_minimization_result = cplex_optimizer.solve(qp)\n",
    "\n",
    "print(\"minimum point: p_min = \", qcio_minimization_result.x)\n",
    "print(\"minimum value: f_1(p_min) = \", qcio_minimization_result.fval)\n",
    "\n",
    "optimal_value= qcio_minimization_result.fval\n",
    "print(qp.binary_var_list)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The minimal x-value of [0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 1. 0. 0. 0. 0. 0. 0. 1.]\n",
    "\n",
    "translates into a partition of a permutation matrix into two matrices, namely \n",
    "\n",
    "\n",
    "$\\left( \\begin{array}{rrr}\n",
    "0 & 0 & 0 \\\\ \n",
    "1 & 0 & 0 \\\\\n",
    "0 & 0 & 0 \\\\ \n",
    "\\end{array}\\right)$\n",
    "\n",
    "$\\left( \\begin{array}{rrr}\n",
    "0 & 1 & 0 \\\\ \n",
    "0 & 0 & 0 \\\\\n",
    "0 & 0 & 1 \\\\ \n",
    "\\end{array}\\right)$\n",
    "\n",
    "\n",
    " meaning tour 1 and tour 3 are served (in that order) by truck 2\n",
    " while tour 2 is served by truck number 1. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"images/two_trucks_problem5.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Proof of concept Model in Qiskit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit_optimization.converters import QuadraticProgramConverter, LinearEqualityToPenalty\n",
    "\n",
    "class Converter(QuadraticProgramConverter):\n",
    "    def __init__(self, penalty: float=None) -> None:\n",
    "        super().__init__()\n",
    "        self._penalty = penalty\n",
    "        self.linear_equality_to_penalty_converter = LinearEqualityToPenalty(penalty)\n",
    "\n",
    "    def convert(self, quadratic_program: QuadraticProgram) -> QuadraticProgram:\n",
    "        return self.linear_equality_to_penalty_converter.convert(quadratic_program)\n",
    "    \n",
    "    def interpret(self, x) -> np.ndarray:\n",
    "        return self.linear_equality_to_penalty_converter.interpret()\n",
    "\n",
    "qp=pdp2.generate_Quadratic_Program(\"QP\")\n",
    "penalty=10\n",
    "converter=Converter(penalty=penalty)\n",
    "qubo=converter.convert(qp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.providers.aer import AerSimulator\n",
    "from qiskit.utils import QuantumInstance\n",
    "from qiskit.opflow import CircuitSampler\n",
    "\n",
    "aer_simulator = AerSimulator()\n",
    "quantum_instance = QuantumInstance(aer_simulator, shots=8000)\n",
    "\n",
    "aer_simulator_statevector = AerSimulator(method=\"statevector\")\n",
    "quantum_instance_statevector = QuantumInstance(aer_simulator_statevector)\n",
    "\n",
    "circuit_sampler = CircuitSampler(quantum_instance_statevector)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit.providers.aer import AerSimulator\n",
    "from qiskit.utils import QuantumInstance\n",
    "from qiskit.opflow import CircuitSampler\n",
    "from qiskit.utils import algorithm_globals\n",
    "\n",
    "algorithm_globals.massive=True\n",
    "aer_simulator = AerSimulator()\n",
    "quantum_instance = QuantumInstance(aer_simulator, shots=8000)\n",
    "\n",
    "aer_simulator_qasm = AerSimulator(method=\"automatic\")\n",
    "quantum_instance_qasm = QuantumInstance(aer_simulator_qasm)\n",
    "\n",
    "circuit_sampler = CircuitSampler(quantum_instance_qasm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PDPExample3(PickUpDeliveryProblem):\n",
    "    def __init__(self):\n",
    "        trucklist=[]\n",
    "        depot1=Tour(Location(4,2),Location(4,2),\"depot1\")\n",
    "        trucklist.append(Truck(depot1, \"truck1\"))\n",
    "        depot2=Tour(Location(0,0),Location(0,0),\"depot2\")\n",
    "        trucklist.append(Truck(depot2, \"truck2\"))\n",
    "        \n",
    "        tourlist=[]\n",
    "        tourlist.append(Tour(Location(0,1), Location(2,1), \"tour1\"))\n",
    "        tourlist.append(Tour(Location(4,3), Location(2,3), \"tour2\"))\n",
    "        super().__init__(tourlist, trucklist, \"2Trucks_2Tours\")\n",
    "\n",
    "pdp3=PDPExample3()\n",
    "\n",
    "qp=pdp1.generate_Quadratic_Program(\"QP\")\n",
    "penalty=10\n",
    "converter=Converter(penalty=penalty)\n",
    "qubo=converter.convert(qp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.plotly.v1+json": {
       "config": {
        "plotlyServerURL": "https://plot.ly"
       },
       "data": [
        {
         "line": {
          "color": "black",
          "width": 1.5
         },
         "name": "simulation,<br>shot noise: False",
         "type": "scatter",
         "x": [
          "000000000",
          "000000001",
          "000000010",
          "000000011",
          "000000100",
          "000000101",
          "000000110",
          "000000111",
          "000001000",
          "000001001",
          "000001010",
          "000001011",
          "000001100",
          "000001101",
          "000001110",
          "000001111",
          "000010000",
          "000010001",
          "000010010",
          "000010011",
          "000010100",
          "000010101",
          "000010110",
          "000010111",
          "000011000",
          "000011001",
          "000011010",
          "000011011",
          "000011100",
          "000011101",
          "000011110",
          "000011111",
          "000100000",
          "000100001",
          "000100010",
          "000100011",
          "000100100",
          "000100101",
          "000100110",
          "000100111",
          "000101000",
          "000101001",
          "000101010",
          "000101011",
          "000101100",
          "000101101",
          "000101110",
          "000101111",
          "000110000",
          "000110001",
          "000110010",
          "000110011",
          "000110100",
          "000110101",
          "000110110",
          "000110111",
          "000111000",
          "000111001",
          "000111010",
          "000111011",
          "000111100",
          "000111101",
          "000111110",
          "000111111",
          "001000000",
          "001000001",
          "001000010",
          "001000011",
          "001000100",
          "001000101",
          "001000110",
          "001000111",
          "001001000",
          "001001001",
          "001001010",
          "001001011",
          "001001100",
          "001001101",
          "001001110",
          "001001111",
          "001010000",
          "001010001",
          "001010010",
          "001010011",
          "001010100",
          "001010101",
          "001010110",
          "001010111",
          "001011000",
          "001011001",
          "001011010",
          "001011011",
          "001011100",
          "001011101",
          "001011110",
          "001011111",
          "001100000",
          "001100001",
          "001100010",
          "001100011",
          "001100100",
          "001100101",
          "001100110",
          "001100111",
          "001101000",
          "001101001",
          "001101010",
          "001101011",
          "001101100",
          "001101101",
          "001101110",
          "001101111",
          "001110000",
          "001110001",
          "001110010",
          "001110011",
          "001110100",
          "001110101",
          "001110110",
          "001110111",
          "001111000",
          "001111001",
          "001111010",
          "001111011",
          "001111100",
          "001111101",
          "001111110",
          "001111111",
          "010000000",
          "010000001",
          "010000010",
          "010000011",
          "010000100",
          "010000101",
          "010000110",
          "010000111",
          "010001000",
          "010001001",
          "010001010",
          "010001011",
          "010001100",
          "010001101",
          "010001110",
          "010001111",
          "010010000",
          "010010001",
          "010010010",
          "010010011",
          "010010100",
          "010010101",
          "010010110",
          "010010111",
          "010011000",
          "010011001",
          "010011010",
          "010011011",
          "010011100",
          "010011101",
          "010011110",
          "010011111",
          "010100000",
          "010100001",
          "010100010",
          "010100011",
          "010100100",
          "010100101",
          "010100110",
          "010100111",
          "010101000",
          "010101001",
          "010101010",
          "010101011",
          "010101100",
          "010101101",
          "010101110",
          "010101111",
          "010110000",
          "010110001",
          "010110010",
          "010110011",
          "010110100",
          "010110101",
          "010110110",
          "010110111",
          "010111000",
          "010111001",
          "010111010",
          "010111011",
          "010111100",
          "010111101",
          "010111110",
          "010111111",
          "011000000",
          "011000001",
          "011000010",
          "011000011",
          "011000100",
          "011000101",
          "011000110",
          "011000111",
          "011001000",
          "011001001",
          "011001010",
          "011001011",
          "011001100",
          "011001101",
          "011001110",
          "011001111",
          "011010000",
          "011010001",
          "011010010",
          "011010011",
          "011010100",
          "011010101",
          "011010110",
          "011010111",
          "011011000",
          "011011001",
          "011011010",
          "011011011",
          "011011100",
          "011011101",
          "011011110",
          "011011111",
          "011100000",
          "011100001",
          "011100010",
          "011100011",
          "011100100",
          "011100101",
          "011100110",
          "011100111",
          "011101000",
          "011101001",
          "011101010",
          "011101011",
          "011101100",
          "011101101",
          "011101110",
          "011101111",
          "011110000",
          "011110001",
          "011110010",
          "011110011",
          "011110100",
          "011110101",
          "011110110",
          "011110111",
          "011111000",
          "011111001",
          "011111010",
          "011111011",
          "011111100",
          "011111101",
          "011111110",
          "011111111",
          "100000000",
          "100000001",
          "100000010",
          "100000011",
          "100000100",
          "100000101",
          "100000110",
          "100000111",
          "100001000",
          "100001001",
          "100001010",
          "100001011",
          "100001100",
          "100001101",
          "100001110",
          "100001111",
          "100010000",
          "100010001",
          "100010010",
          "100010011",
          "100010100",
          "100010101",
          "100010110",
          "100010111",
          "100011000",
          "100011001",
          "100011010",
          "100011011",
          "100011100",
          "100011101",
          "100011110",
          "100011111",
          "100100000",
          "100100001",
          "100100010",
          "100100011",
          "100100100",
          "100100101",
          "100100110",
          "100100111",
          "100101000",
          "100101001",
          "100101010",
          "100101011",
          "100101100",
          "100101101",
          "100101110",
          "100101111",
          "100110000",
          "100110001",
          "100110010",
          "100110011",
          "100110100",
          "100110101",
          "100110110",
          "100110111",
          "100111000",
          "100111001",
          "100111010",
          "100111011",
          "100111100",
          "100111101",
          "100111110",
          "100111111",
          "101000000",
          "101000001",
          "101000010",
          "101000011",
          "101000100",
          "101000101",
          "101000110",
          "101000111",
          "101001000",
          "101001001",
          "101001010",
          "101001011",
          "101001100",
          "101001101",
          "101001110",
          "101001111",
          "101010000",
          "101010001",
          "101010010",
          "101010011",
          "101010100",
          "101010101",
          "101010110",
          "101010111",
          "101011000",
          "101011001",
          "101011010",
          "101011011",
          "101011100",
          "101011101",
          "101011110",
          "101011111",
          "101100000",
          "101100001",
          "101100010",
          "101100011",
          "101100100",
          "101100101",
          "101100110",
          "101100111",
          "101101000",
          "101101001",
          "101101010",
          "101101011",
          "101101100",
          "101101101",
          "101101110",
          "101101111",
          "101110000",
          "101110001",
          "101110010",
          "101110011",
          "101110100",
          "101110101",
          "101110110",
          "101110111",
          "101111000",
          "101111001",
          "101111010",
          "101111011",
          "101111100",
          "101111101",
          "101111110",
          "101111111",
          "110000000",
          "110000001",
          "110000010",
          "110000011",
          "110000100",
          "110000101",
          "110000110",
          "110000111",
          "110001000",
          "110001001",
          "110001010",
          "110001011",
          "110001100",
          "110001101",
          "110001110",
          "110001111",
          "110010000",
          "110010001",
          "110010010",
          "110010011",
          "110010100",
          "110010101",
          "110010110",
          "110010111",
          "110011000",
          "110011001",
          "110011010",
          "110011011",
          "110011100",
          "110011101",
          "110011110",
          "110011111",
          "110100000",
          "110100001",
          "110100010",
          "110100011",
          "110100100",
          "110100101",
          "110100110",
          "110100111",
          "110101000",
          "110101001",
          "110101010",
          "110101011",
          "110101100",
          "110101101",
          "110101110",
          "110101111",
          "110110000",
          "110110001",
          "110110010",
          "110110011",
          "110110100",
          "110110101",
          "110110110",
          "110110111",
          "110111000",
          "110111001",
          "110111010",
          "110111011",
          "110111100",
          "110111101",
          "110111110",
          "110111111",
          "111000000",
          "111000001",
          "111000010",
          "111000011",
          "111000100",
          "111000101",
          "111000110",
          "111000111",
          "111001000",
          "111001001",
          "111001010",
          "111001011",
          "111001100",
          "111001101",
          "111001110",
          "111001111",
          "111010000",
          "111010001",
          "111010010",
          "111010011",
          "111010100",
          "111010101",
          "111010110",
          "111010111",
          "111011000",
          "111011001",
          "111011010",
          "111011011",
          "111011100",
          "111011101",
          "111011110",
          "111011111",
          "111100000",
          "111100001",
          "111100010",
          "111100011",
          "111100100",
          "111100101",
          "111100110",
          "111100111",
          "111101000",
          "111101001",
          "111101010",
          "111101011",
          "111101100",
          "111101101",
          "111101110",
          "111101111",
          "111110000",
          "111110001",
          "111110010",
          "111110011",
          "111110100",
          "111110101",
          "111110110",
          "111110111",
          "111111000",
          "111111001",
          "111111010",
          "111111011",
          "111111100",
          "111111101",
          "111111110",
          "111111111"
         ],
         "y": [
          0.00004788027815085088,
          0.0015602650084465938,
          0.0005153979969136228,
          0.0006601542709813321,
          0.00012589057945861876,
          0.0018234866204624787,
          0.0017971363664869195,
          0.0003950985657563531,
          0.0036710470178131826,
          0.0009234719754817693,
          0.007906140934754228,
          0.0035642337303629706,
          0.0024286751277080194,
          0.0010015589858924847,
          0.0005000269033959677,
          0.0003413303742574769,
          0.000764290881053289,
          0.0013206576130213212,
          0.008816136987240363,
          0.0013146924864137492,
          0.0015013604953639185,
          0.006015671652495861,
          0.000016518311173778798,
          0.000059242650256066806,
          0.00030079834112526596,
          0.006559695252699237,
          0.005742750899993736,
          0.00012257078477330297,
          0.0005957562480898524,
          0.006267395432333564,
          0.00031647594743654695,
          0.0004662781860704066,
          0.0006142081314703752,
          0.0003011889638527752,
          0.003990989412543274,
          0.00017190488379938097,
          0.00013191419768597177,
          0.0009208896098491973,
          0.0004330388824423888,
          0.0009795628489729076,
          0.001953796417668664,
          0.0006967052991463003,
          0.00020585395956824844,
          0.001004363547548082,
          0.0028777180277748966,
          0.010991286350263595,
          0.002185234566437207,
          0.005197103955413801,
          0.001099003442767746,
          0.00016850602392827032,
          0.002614107741366717,
          0.0005669338256114719,
          0.0019263727427206428,
          0.005716897656903441,
          0.004516659542906314,
          0.0007045230841987287,
          0.00017837287494990983,
          0.00016386067671014603,
          0.002133725609399486,
          0.0009402235298360718,
          0.0007275203492258277,
          0.003563381454445672,
          0.006531186509816567,
          0.0010149899889232452,
          0.0029412623678144677,
          0.00441437840012919,
          0.0006614286907424387,
          0.006169904531866694,
          0.0012681219174254972,
          0.00018687657311940511,
          0.001903147156353963,
          0.0012303496597008813,
          0.0022595930417230376,
          0.002047179731463197,
          0.00021293067550429476,
          0.002322437225618634,
          0.0008752581318440332,
          0.0002625949701300321,
          0.0032697960889768113,
          0.0016589819253945656,
          0.00038897739626864505,
          0.00239224095778813,
          0.004100414999342812,
          0.0006739236335459456,
          0.0013075432757593067,
          0.0007031284534232033,
          0.002323847289979601,
          0.0002389657583847796,
          0.00012578178671595485,
          0.002950857592570928,
          0.0028665211621154776,
          0.00024283410472427413,
          0.003069019101644652,
          0.00010546539357565222,
          0.003927572699732477,
          0.0003164581823615399,
          0.00010186350777289396,
          0.0012500645714180149,
          0.0019977176539616314,
          0.0026578533655971627,
          0.00239775725152942,
          0.001979945312243181,
          0.008991405878176038,
          0.0009675666962127856,
          0.00017700066683544693,
          0.004930540998545305,
          0.0005884529646271539,
          0.0011645401597806448,
          0.0015050181936868876,
          0.00036605726466016144,
          0.0012681926427332434,
          0.0011870902086094399,
          0.0013699555235014054,
          0.0018137478260855978,
          0.001289063555941513,
          0.0002414090835587088,
          0.0008208651345287292,
          0.0036604974990704173,
          0.0029219055783700917,
          0.00039552286771377327,
          0.003134218577511877,
          0.0064011676275394684,
          0.0016160667713591337,
          0.000553967195318699,
          0.0006504162120665975,
          0.001849341077327502,
          0.0015121347146221712,
          0.000052528143098287013,
          0.003563769421502966,
          0.0027149058715506386,
          0.003166074631376945,
          0.0002537467806065929,
          0.0005650113224747652,
          0.004544631833315883,
          0.003232322940704558,
          0.0002039036644712315,
          0.0019449496330985752,
          0.00045277433719101244,
          0.0012227606140496018,
          0.0017851849774262157,
          0.0007320934305013758,
          0.0018559662526861046,
          0.002708435304189019,
          0.003964140374434139,
          0.0016201199215233805,
          0.0007851559659760996,
          0.00005642692135152675,
          0.0014156196799822239,
          0.004608715175769366,
          0.0001194329869745848,
          0.002264593977291701,
          0.006599451088394792,
          0.00021365690189964752,
          0.0030732505104471724,
          0.0007726155220537548,
          0.0002824103886751276,
          0.000054435386861815006,
          0.001332135026092022,
          0.0001473958640132609,
          0.0006989128278653597,
          0.0003578032070997339,
          0.0016995577157720013,
          0.00465895549598651,
          0.0008277989491140125,
          0.00012144095579851781,
          0.0013582206057716904,
          0.0025380030450326964,
          0.0025625887892363566,
          0.0008872757059011633,
          0.003150163727103523,
          0.0018819378506569125,
          0.0012744345896324128,
          0.003938506227017184,
          0.00006393202339900974,
          0.0011840968753409511,
          0.0031718128006281783,
          0.007726675793342051,
          0.006309464296724925,
          0.0007418781848030372,
          0.006440220907169207,
          0.0008214352375772229,
          0.00010961756169377459,
          0.0010051933446302737,
          0.0011474280520470577,
          0.001577266397799173,
          0.0008197017362738836,
          0.001278053950761542,
          0.0007852712114434414,
          0.0000974821842146077,
          0.0005952253254200355,
          0.0005519531909018356,
          0.0007708278877685623,
          0.0026743028771853503,
          0.0027170631708724677,
          0.0027259241826642615,
          0.00042589060432645027,
          0.0018551669744666687,
          0.006981720314498772,
          0.0018686042753742226,
          0.00037973882871584526,
          0.000179725223269728,
          0.0028634282133311716,
          0.00292566432483691,
          0.0011699676564473887,
          0.0006818480894296056,
          0.001660115536869985,
          0.004063724863266593,
          0.0010685703708541102,
          0.0004162013135812989,
          0.0008915067555196109,
          0.002837930776092086,
          0.000941579606551031,
          0.002312118316636227,
          0.000645808636278793,
          0.0004957662348367423,
          0.002806216542712959,
          0.00009944693914184549,
          0.0004467954474708496,
          0.001637370844892974,
          0.000578097884087699,
          0.0062398326620954295,
          0.004738296584829811,
          0.0021004507589213366,
          0.0065006740384630415,
          0.00040878993578693113,
          0.0029446431131999688,
          0.0025731016666374457,
          0.0011485158989776557,
          0.005602884223780746,
          0.0034583151209216173,
          0.0010255432234467974,
          0.0017028959090322083,
          0.0024028687836776695,
          0.003932171822841199,
          0.0008454420183347912,
          0.0018820977418467463,
          0.0023467205028750897,
          0.00014853240580835837,
          0.00042118993146827234,
          0.00009491656833710292,
          0.00033321940400506367,
          0.00023912728824301586,
          0.0008280230979359152,
          0.003641188384737529,
          0.001748821289423602,
          0.0012263427880729475,
          0.0015113210255612128,
          0.0011355477552839222,
          0.002018160669043325,
          0.00034558838403544177,
          0.005303937833439869,
          0.009397872325669503,
          0.0009412335406483444,
          0.002845685736031857,
          0.001217587247598849,
          0.0010924905487290136,
          0.00035549855695456135,
          0.0047328898859159245,
          0.001312489833902524,
          0.0004825041684480062,
          0.0053508025094093515,
          0.003210181421019686,
          0.0004743162334697792,
          0.0013405836995450781,
          0.0007059440988351312,
          0.001988799309206404,
          0.0002506200286653295,
          0.006150255987459745,
          0.003055115428053462,
          0.0003768445977556291,
          0.00020770273791764288,
          0.0032405566867155394,
          0.0005679825242531777,
          0.0002646137703427158,
          0.000018182846134278064,
          0.0013995301149436487,
          0.0045431238050950154,
          0.0010328887821095963,
          0.005094659617146114,
          0.007888610838478975,
          0.00037636644342264815,
          0.0005541436008232635,
          0.0006183354681522441,
          0.00005797765708641518,
          0.002739322895900835,
          0.003850441461834004,
          0.0010185330093879915,
          0.000308436478480537,
          0.0016915484711295212,
          0.00038489249884474856,
          0.0013718729283964074,
          0.006270903100192554,
          0.001583119784621232,
          0.0009127969665317844,
          0.00026887593945282913,
          0.00031831702375377123,
          0.0014062509615367354,
          0.0024834034594561757,
          0.0002351257724335738,
          0.0006579326618477889,
          0.007546699467707247,
          0.0004580444533605769,
          0.00020713022906483514,
          0.0003650586100961955,
          0.005035613891178432,
          0.004000164956462553,
          0.0015092902066306392,
          0.011635415677736205,
          0.0010766131796694223,
          0.00073970249070353,
          0.001926072031038911,
          0.0007587404991322716,
          0.0005193322599651906,
          0.00024112522718187156,
          0.0014158777019657137,
          0.004625355857659769,
          0.001010610686826014,
          0.0004170913853964462,
          0.0010454094751669743,
          0.000045830728505209737,
          0.006303862209528179,
          0.0013841021952507749,
          0.002405391882868686,
          0.002006099482533322,
          0.001452426558741095,
          0.0027640116347486597,
          0.0009195935084265038,
          0.002140489241739799,
          0.0009672166950372899,
          0.0019502400686747076,
          0.0002443495535921719,
          0.0015855410535034267,
          0.0020583829606863942,
          0.000337529757083864,
          0.00044416586727166356,
          0.006409521316352193,
          0.0006746095856706122,
          0.00011653505570985986,
          0.0014975191384599689,
          0.001090536583581074,
          0.0011440369595256965,
          0.0012374330350066322,
          0.00024239410680511848,
          0.0026171315451936922,
          0.0006468315414254527,
          0.003079884947815827,
          0.0003097344928308461,
          0.0014901690632199345,
          0.004734964687723063,
          0.0028201912022134544,
          0.0021149549095784894,
          0.004195386976214853,
          0.002411081094617903,
          0.002747886057564006,
          0.00019004797790208582,
          0.00027094650241305435,
          0.0008791099430281558,
          0.00005895218631412151,
          0.00007653846982413766,
          0.012524986271140246,
          0.005994304648567167,
          0.0009582189182279711,
          0.000546490522305729,
          0.0009470241376089473,
          0.00012443920053030328,
          0.0006004781064336365,
          0.00028241995005511006,
          0.003723164041121346,
          0.002770309225758321,
          0.0008625429244559367,
          0.001020453228508675,
          0.00035805037570236375,
          0.0010007182477156798,
          0.0009230244467567186,
          0.00047348190505229807,
          0.0022391065608787443,
          0.00988448903243421,
          0.0006234046627248332,
          0.0031454364710199597,
          0.003594030856179763,
          0.00026276669715016404,
          0.0005992204966028022,
          0.00020526549187527285,
          0.0026880094542083904,
          0.0008781234804781806,
          0.0016123343630995404,
          0.00024098975569048026,
          0.00027841622298175895,
          0.0013297860010987805,
          0.00038881032679351804,
          0.0006015033609210846,
          0.00042811345329709375,
          0.005083901286250716,
          0.002664836771458547,
          0.0010953428723125891,
          0.006650218536864174,
          0.001066006038474841,
          0.0001242815877109718,
          0.005750573722681389,
          0.0006448915372305612,
          0.0012999209409468478,
          0.004311116691432814,
          0.0021611339296872065,
          0.0016627361289756053,
          0.0040016216274141704,
          0.0007694871422242893,
          0.002458899114145794,
          0.0009425571350411503,
          0.004542809631119357,
          0.0011522316047725303,
          0.003188958756894319,
          0.0012359224658576508,
          0.0013930538517316702,
          0.0008905120462554392,
          0.0007713914677031771,
          0.0018343105317906883,
          0.0005901491217257442,
          0.0006908403161720667,
          0.000822913949805681,
          0.00028710054491350287,
          0.000276837566663282,
          0.0005231617922528055,
          0.004562508377758758,
          0.001489119233585654,
          0.003351243407701673,
          0.0009505993661813206,
          0.0026097222425953246,
          0.00017305538291627858,
          0.002871879923878852,
          0.0020455223171706046,
          0.00616041814174541,
          0.003219871228672525,
          0.005984865291383264,
          0.002156240437085953,
          0.0005623957048212359,
          0.0005097319747179976,
          0.0017913311150670318,
          0.0017786474949981032,
          0.00011921455449388427,
          0.0014726407684308494,
          0.0014613575006864176,
          0.001229036083717712,
          0.00009144304968530424,
          0.001822717052389615,
          0.0011057397099152337,
          0.003690335919671371,
          0.0049498840588489855,
          0.003378091374562932,
          0.005516679436401119,
          0.004062284809477608,
          0.0028239726561716896,
          0.0025797906731220375,
          0.0009944687652017653,
          0.0003787240213679471,
          0.002460801369832362,
          0.0017051663075448953,
          0.00011698621138014813,
          0.00012178865385315197,
          0.003305507585090931,
          0.00159563948746339,
          0.0009079118921514142,
          0.00040377972741345136,
          0.0013792044659810747,
          0.00037815318898437616,
          0.002308128596045981,
          0.0021514436907307407,
          0.0009049704283433248,
          0.00418624534450865,
          0.0001471961026262544,
          0.002218515478188369,
          0.002595086801981637,
          0.0009709911157590722,
          0.00214771002327785,
          0.002587796101461299,
          0.004297939568077051,
          0.0010628964687193776,
          0.002711497972538579,
          0.0023313698989366324,
          0.0022036829510175895,
          0.0017554918339928803,
          0.00032436180858525925,
          0.00016236126249045144,
          0.004076340717845648,
          0.002926822875282361,
          0.003634135853096667,
          0.005911284957169678,
          0.003911155114075986,
          0.000305641875537007,
          0.00044766494823373634,
          0.001062532716113752,
          0.0014244707566684921,
          0.0013958529488212446,
          0.004700085460157672,
          0.003775185281866251,
          0.00004667910688819893,
          0.0014764773297392443,
          0.001228954159163111,
          0.000275979957695769,
          0.000186016799819736,
          0.00006260555164026653,
          0.005417153467403923,
          0.0021455940947352333,
          0.0003479202776313055,
          0.00175681430086957,
          0.001973650831443917,
          0.0008006505316651929,
          0.004308239678572302,
          0.002652568647531333,
          0.000604686842219739,
          0.0020301185938370984,
          0.001510653581551554,
          0.0015186746457324534
         ]
        },
        {
         "marker": {
          "color": "red",
          "size": 12,
          "symbol": "arrow-down"
         },
         "mode": "markers",
         "name": "optimal solution",
         "type": "scatter",
         "x": [],
         "y": []
        },
        {
         "marker": {
          "color": "blue",
          "size": 12,
          "symbol": "cross"
         },
         "mode": "markers",
         "name": "feasible solution",
         "type": "scatter",
         "x": [
          "001010100",
          "001100010",
          "010001100",
          "010100001",
          "100001010",
          "100010001"
         ],
         "y": [
          0.0013075432757593067,
          0.0019977176539616314,
          0.0007320934305013758,
          0.0016995577157720013,
          0.0002506200286653295,
          0.0002646137703427158
         ]
        }
       ],
       "layout": {
        "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": [
           {
            "marker": {
             "colorbar": {
              "outlinewidth": 0,
              "ticks": ""
             }
            },
            "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
          }
         }
        },
        "title": {
         "font": {
          "size": 12
         },
         "text": "example_3tours, penalty: 10.000; QAOA: p=1<br>betas: 1.000, gammas: 3.000, "
        },
        "xaxis": {
         "tickfont": {
          "size": 8
         }
        },
        "yaxis": {
         "title": {
          "font": {
           "size": 12
          },
          "text": "probability"
         }
        }
       }
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "from ast import And\n",
    "from qiskit.circuit.library.n_local import QAOAAnsatz\n",
    "from qiskit.opflow import CircuitStateFn, OperatorStateFn, VectorStateFn, DictStateFn, CircuitSampler\n",
    "\n",
    "import plotly.graph_objects as go\n",
    "import pandas as pd\n",
    "\n",
    "\n",
    "def generate_bitstrings(number_bits: int):\n",
    "    return [bin(k)[2:].zfill(number_bits) for k in range(2**number_bits)]\n",
    "\n",
    "def generate_bitarrays(number_bits: int):\n",
    "    return [np.array(list(bin(k)[2:].zfill(number_bits))[::-1], dtype=int) for k in range(2**number_bits)]\n",
    "\n",
    "number_binary_variables = qubo.get_num_binary_vars()\n",
    "\n",
    "ising, ising_offset = qubo.to_ising()\n",
    "number_of_shots=8000\n",
    "qaoa_reps=1\n",
    "simulator_with_shot_noise = False\n",
    "\n",
    "betas=[1]\n",
    "gammas=[3]\n",
    "\n",
    "#%%\n",
    "qaoa_ansatz = QAOAAnsatz(cost_operator=ising, reps=qaoa_reps)\n",
    "wave_function = CircuitStateFn(qaoa_ansatz)\n",
    "observable = OperatorStateFn(ising, is_measurement=True)\n",
    "expectation_operator = observable @ wave_function\n",
    "\n",
    "aer_simulator_statevector = AerSimulator(method=\"statevector\", shots=number_of_shots)\n",
    "quantum_instance = QuantumInstance(aer_simulator_statevector)\n",
    "circuit_sampler = CircuitSampler(quantum_instance, statevector=not simulator_with_shot_noise)\n",
    "\n",
    "def run_qaoa(parameter_values):\n",
    "    \"parameter_values is expected to be of the form [beta_0, beta_1, ..., gamma_0, gamma_1, ...]\"\n",
    "    parameter_bindings = dict(zip(qaoa_ansatz.parameters, parameter_values))\n",
    "    wave_function_sampled = circuit_sampler.convert(wave_function, params=parameter_bindings)\n",
    "    return wave_function_sampled\n",
    "\n",
    "#%%\n",
    "# Be careful: the data type of wave_function_sampled depends if shot noise is present\n",
    "wave_function_sampled = run_qaoa([*betas, *gammas])\n",
    "\n",
    "if isinstance(wave_function_sampled, DictStateFn): # data type returned in case with shot noise\n",
    "    probabilities = np.real(wave_function_sampled.to_matrix()**2)\n",
    "elif isinstance(wave_function_sampled, VectorStateFn): # data type returned in case without shot noise\n",
    "    probabilities = np.abs(wave_function_sampled.to_matrix())**2\n",
    "assert np.isclose(probabilities.sum(), 1), \"Error: probabilities don't sum up to 1.\"\n",
    "\n",
    "df_simulation = pd.DataFrame(index=generate_bitstrings(number_binary_variables))\n",
    "df_simulation['probability'] = probabilities\n",
    "\n",
    "#%%\n",
    "df_further_info = pd.DataFrame(index=generate_bitstrings(number_binary_variables))\n",
    "df_further_info[\"bitarray\"] = generate_bitarrays(number_binary_variables)\n",
    "df_further_info[\"cost\"] = df_further_info[\"bitarray\"].apply(qp.objective.evaluate)\n",
    "df_further_info[\"is_feasible\"] = df_further_info[\"bitarray\"].apply(qp.is_feasible)\n",
    "df_further_info[\"is_optimal\"] = (df_further_info[\"cost\"] - optimal_value).apply(lambda x: np.isclose(x, 0)) \n",
    "df_further_info[\"is_optimal_and_feasible\"] = df_further_info[\"is_optimal\"] & df_further_info[\"is_feasible\"]\n",
    "\n",
    "\n",
    "\n",
    "#%%\n",
    "fig = go.Figure()\n",
    "fig.add_trace(go.Scatter(\n",
    "    x=df_simulation.index,\n",
    "    y=df_simulation[\"probability\"],\n",
    "    line_color=\"black\",\n",
    "    line_width=1.5,\n",
    "    name=f\"simulation,<br>shot noise: {simulator_with_shot_noise}\"\n",
    "))\n",
    "fig.add_trace(go.Scatter(\n",
    "    x=df_simulation[df_further_info[\"is_optimal_and_feasible\"]].index,\n",
    "    y=df_simulation[df_further_info[\"is_optimal_and_feasible\"]][\"probability\"],\n",
    "    mode=\"markers\",\n",
    "    marker_symbol=\"arrow-down\",\n",
    "    marker_size=12,\n",
    "    marker_color=\"red\",\n",
    "    name=\"optimal solution\"\n",
    "))\n",
    "fig.add_trace(go.Scatter(\n",
    "    x=df_simulation[df_further_info[\"is_feasible\"]].index,\n",
    "    y=df_simulation[df_further_info[\"is_feasible\"]][\"probability\"],\n",
    "    mode=\"markers\",\n",
    "    marker_symbol=\"cross\",\n",
    "    marker_size=12,\n",
    "    marker_color=\"blue\",\n",
    "    name=\"feasible solution\"\n",
    "))\n",
    "fig.update_xaxes(\n",
    "    tickfont_size=8,\n",
    ")\n",
    "fig.update_yaxes(\n",
    "    title=\"probability\",\n",
    "    title_font_size=12\n",
    ")\n",
    "title_betas = \"\".join([f\"{beta:.3f}, \" for beta in betas])\n",
    "title_gammas = \"\".join([f\"{gamma:.3f}, \" for gamma in gammas])\n",
    "fig.update_layout(\n",
    "    title=f\"example_3tours, penalty: {penalty:.3f}; QAOA: p={qaoa_reps}<br>\" \\\n",
    "        + \"betas: \" + title_betas + \"gammas: \" + title_gammas,\n",
    "    title_font_size=12\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                              bitarray  cost  is_feasible  is_optimal  \\\n",
      "000000000  [0, 0, 0, 0, 0, 0, 0, 0, 0]   0.0        False       False   \n",
      "101011101  [1, 0, 1, 1, 1, 0, 1, 0, 1]  35.0        False       False   \n",
      "101011100  [0, 0, 1, 1, 1, 0, 1, 0, 1]  25.0        False       False   \n",
      "101011011  [1, 1, 0, 1, 1, 0, 1, 0, 1]  36.0        False       False   \n",
      "101011010  [0, 1, 0, 1, 1, 0, 1, 0, 1]  24.0        False       False   \n",
      "...                                ...   ...          ...         ...   \n",
      "100001010  [0, 1, 0, 1, 0, 0, 0, 0, 1]   5.0         True       False   \n",
      "100010001  [1, 0, 0, 0, 1, 0, 0, 0, 1]  15.0         True       False   \n",
      "001010100  [0, 0, 1, 0, 1, 0, 1, 0, 0]  15.0         True       False   \n",
      "010001100  [0, 0, 1, 1, 0, 0, 0, 1, 0]   9.0         True       False   \n",
      "001100010  [0, 1, 0, 0, 0, 1, 1, 0, 0]  19.0         True       False   \n",
      "\n",
      "           is_optimal_and_feasible  \n",
      "000000000                    False  \n",
      "101011101                    False  \n",
      "101011100                    False  \n",
      "101011011                    False  \n",
      "101011010                    False  \n",
      "...                            ...  \n",
      "100001010                    False  \n",
      "100010001                    False  \n",
      "001010100                    False  \n",
      "010001100                    False  \n",
      "001100010                    False  \n",
      "\n",
      "[512 rows x 5 columns]\n"
     ]
    }
   ],
   "source": [
    "print(df_further_info.sort_values(by=\"is_feasible\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**The same result for p=1 without a fixed depot**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"plots/Simulationen/example_3Tours_p=1.PNG\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Simulation for p=2**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"plots/Simulationen/example_3Tours_p=2.PNG\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**p=3**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"plots/Simulationen/example_3Tours_p=3.PNG\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**p=3 with shot noise**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"plots/Simulationen/example_3Tours_p=3_shotNoise.png\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "INSTALLED VERSIONS\n",
      "------------------\n",
      "commit           : 945c9ed766a61c7d2c0a7cbb251b6edebf9cb7d5\n",
      "python           : 3.9.13.final.0\n",
      "python-bits      : 64\n",
      "OS               : Windows\n",
      "OS-release       : 10\n",
      "Version          : 10.0.19045\n",
      "machine          : AMD64\n",
      "processor        : Intel64 Family 6 Model 142 Stepping 10, GenuineIntel\n",
      "byteorder        : little\n",
      "LC_ALL           : None\n",
      "LANG             : None\n",
      "LOCALE           : de_DE.cp1252\n",
      "\n",
      "pandas           : 1.3.4\n",
      "numpy            : 1.21.4\n",
      "pytz             : 2021.3\n",
      "dateutil         : 2.8.2\n",
      "pip              : 22.1.2\n",
      "setuptools       : 58.1.0\n",
      "Cython           : 0.29.25\n",
      "pytest           : None\n",
      "hypothesis       : None\n",
      "sphinx           : None\n",
      "blosc            : None\n",
      "feather          : None\n",
      "xlsxwriter       : None\n",
      "lxml.etree       : 4.6.4\n",
      "html5lib         : 1.1\n",
      "pymysql          : None\n",
      "psycopg2         : None\n",
      "jinja2           : 3.0.3\n",
      "IPython          : 7.30.1\n",
      "pandas_datareader: None\n",
      "bs4              : None\n",
      "bottleneck       : None\n",
      "fsspec           : None\n",
      "fastparquet      : None\n",
      "gcsfs            : None\n",
      "matplotlib       : 3.5.0\n",
      "numexpr          : None\n",
      "odfpy            : None\n",
      "openpyxl         : None\n",
      "pandas_gbq       : None\n",
      "pyarrow          : None\n",
      "pyxlsb           : None\n",
      "s3fs             : None\n",
      "scipy            : 1.7.3\n",
      "sqlalchemy       : None\n",
      "tables           : None\n",
      "tabulate         : None\n",
      "xarray           : None\n",
      "xlrd             : None\n",
      "xlwt             : None\n",
      "numba            : None\n"
     ]
    }
   ],
   "source": [
    "import qiskit\n",
    "pd.show_versions()"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Copyright 2023 Florian Knäble, Fraunhofer IAO**\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\"); you may not use this file except in compliance with the License. You may obtain a copy of the License at\n",
    "\n",
    "http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13 (main, Aug 25 2022, 23:51:50) [MSC v.1916 64 bit (AMD64)]"
  },
  "vscode": {
   "interpreter": {
    "hash": "22af032344c768e1d157e1b38d6a78b920a14047785a8ab4488015d1714ac992"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}