tutorial/313_setpacking.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rQhM7XnNFGMM"
   },
   "source": [
    "# Set Packing Problem\n",
    "\n",
    "It's similar to tutorial007_exact_cover_en.ipynb\n",
    "\n",
    "Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.\n",
    "\n",
    "Suppose one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint (in other words, no two of them share an element).\n",
    "\n",
    "https://en.wikipedia.org/wiki/Set_packing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "XhmMF4YCFGMQ"
   },
   "source": [
    "## Installation\n",
    "\n",
    "Please install blueqat first\n",
    "\n",
    "```bash\n",
    "pip install blueqat\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ty3rdG-HFGMS"
   },
   "source": [
    "Import libraries and prepare instance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "bc9Kbt4fFGMT"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from blueqat import vqe\n",
    "from blueqat.pauli import qubo_bit as q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0gSFrTTSFGMZ"
   },
   "source": [
    "## create a QUBO\n",
    "\n",
    "This time we have the cost function \n",
    "\n",
    "$ E = E_{A} + E_{B} $\n",
    "\n",
    "And each of $E_{A}, E_{B}$ are defined as \n",
    "\n",
    "$ E _ { A } = A \\sum _ { i , j : V _ { i } \\cap V _ { j } \\neq \\emptyset } x _ { i } x _ { j }$\n",
    "\n",
    "$E _ { B } = - B \\sum _ { i } x _ { i }$\n",
    "\n",
    "For $A, B$  we need $A > B$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "AL-gIZBxFGMZ"
   },
   "outputs": [],
   "source": [
    "A = 1.0\n",
    "B = 0.9\n",
    "\n",
    "def get_qubo(V):\n",
    "    Q = 0\n",
    "\n",
    "    for i in range(len(V)):\n",
    "        for j in range(i, len(V)):\n",
    "            if i == j:\n",
    "                Q += -B*q(i)*q(i)\n",
    "            elif len(V[i]) + len(V[j]) != len( set(V[i]) | set(V[j]) ):\n",
    "                Q +=  A*q(i)*q(j)\n",
    "\n",
    "    return Q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "xJGAeigeFGMd"
   },
   "source": [
    "And function for showing result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "pQ0cYNbpFGMf"
   },
   "outputs": [],
   "source": [
    "def show_answer(list_x, energies = None, show_graph = False):\n",
    "    print(\"Result x:\", list_x)\n",
    "    text = \"\"\n",
    "    for i in range(len(list_x)):\n",
    "        if(list_x[i]):\n",
    "            text += str(V[i])\n",
    "    print(\"Picked {} group(s): {}\".format(sum(list_x), text))\n",
    "    if energies is not None:\n",
    "        print(\"Energy:\", a.E[-1])\n",
    "    if show_graph:\n",
    "        plt.plot(a.E)\n",
    "        plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "yA8TZXDoFGMj"
   },
   "source": [
    "Let's start it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 442
    },
    "colab_type": "code",
    "id": "B3xi5q02FGMl",
    "outputId": "9b142c9f-cb0f-406b-a08d-ae5de4476fed"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(((1, 1, 0, 0, 1, 1, 0, 0), 0.6495540692699742), ((0, 0, 0, 1, 1, 0, 1, 0), 0.03135518519092012), ((0, 0, 0, 1, 0, 1, 1, 0), 0.026352599379227085), ((1, 1, 0, 0, 0, 1, 0, 0), 0.013504476013302623), ((0, 0, 0, 1, 1, 1, 0, 0), 0.011876329866058126), ((0, 0, 0, 1, 1, 1, 1, 0), 0.010771038182339607), ((0, 0, 0, 0, 1, 1, 1, 0), 0.010763815783676035), ((1, 1, 1, 0, 1, 0, 0, 0), 0.010757079587478789), ((0, 1, 0, 0, 1, 1, 0, 0), 0.009222771696860848), ((1, 0, 0, 0, 1, 1, 0, 0), 0.009222771696860817), ((0, 0, 1, 1, 0, 0, 0, 0), 0.009179261244600865), ((1, 1, 1, 0, 1, 1, 0, 0), 0.007637822138419922))\n"
     ]
    }
   ],
   "source": [
    "V = [ [1,2], [3,4,5,6], [7,8,9,10], [1,3,5], [10], [7,9], [2,4,6,8], [1,2,3,4,5,6,8,10] ]\n",
    "\n",
    "h = get_qubo(V)\n",
    "step = 200\n",
    "result = vqe.Vqe(vqe.QaoaAnsatz(h, step)).run()\n",
    "print(result.most_common(12))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1dUZCeUOFGMu"
   },
   "source": [
    "The correct answer is {1,3,5},{10},{7,9},{2,4,6,8}. Sometimes different answer selected."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "6pa6QtTAFGMv"
   },
   "source": [
    "This Set Packing problem has similarity to Maximal Independent Set (MIS) Problem. These 2 problems are the same."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "tutorial014_set_packing_en.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}