OpenJij/OpenJij

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 整数長ジョブシーケンス問題\n",
    "\n",
    "こちらでは、[Lucas, 2014, \"Ising formulations of many NP problems\"](https://doi.org/10.3389/fphy.2014.00005)の 6.3. Job Sequencing with Integer Lengths を OpenJij と [JijModeling](https://www.ref.documentation.jijzept.com/jijmodeling/)、そして[JijModeling transpiler](https://www.ref.documentation.jijzept.com/jijmodeling-transpiler/) を用いて解く方法をご紹介します。\n",
    "\n",
    "## 概要: 整数長ジョブシーケンス問題とは\n",
    "\n",
    "タスク1は実行するのに1時間、タスク2は実行に3時間、というように、整数の長さを持つタスクがいくつかあったとします。\n",
    "これらを複数の実行するコンピュータに配分するとき、偏りを作ることなくコンピュータの実行時間を分散させるにはどのような組合せがあるでしょうか、というのを考える問題です。\n",
    "\n",
    "### 具体例\n",
    "\n",
    "分かりやすくするために具体的に以下のような状況を考えてみましょう。 \n",
    "\n",
    "> ここに10個のタスクと3個のコンピュータがあります。10個の仕事の長さはそれぞれ$1, 2, \\dots, 10$とします。\n",
    "> これらのタスクをどのようにコンピュータに仕事を割り振れば仕事にかかる時間の最大値を最小化できるか考えます。\n",
    "> この場合、例えば1つ目のコンピュータには9, 10、2つ目には1, 2, 7, 8、3つ目には3, 4, 5, 6とするととなり、3つのコンピュータの実行時間の最大値は19となり、これが最適解です。\n",
    "\n",
    "![](../../../assets/integer_jobs_01.png)\n",
    "\n",
    "### 問題の一般化\n",
    "\n",
    "$N$個のタスク$\\{0, 1, \\dots, N-1\\}$と$M$個のコンピュータ$\\{0, 1, \\dots, M-1\\}$を考えましょう。各タスクの実行にかかる時間のリストを$\\bm{L} = \\{L_0, L_1, \\dots, L_{N-1}\\}$とします。\n",
    "$j$番目のコンピュータで実行される仕事の集合を$V_j$としたとき、コンピュータ$j$でタスクを終えるまでの時間は$A_j = \\sum_{i \\in V_j} L_i$となります。\n",
    "$i$番目のタスクをコンピュータ$j$で行うことを表すバイナリ変数を$x_{i, j}$とします。\n",
    "\n",
    "**制約: タスクはどれか1つのコンピュータで実行されなければならない**\n",
    "\n",
    "例えば、タスク3をコンピュータ1と2の両方で実行することは許されません。これを数式にすると\n",
    "\n",
    "$$\n",
    "\\sum_{j=0}^{M-1} x_{i, j} = 1 \\quad (\\forall i \\in \\{ 0, 1, \\dots, N-1 \\})\n",
    "\\tag{1}\n",
    "$$\n",
    "\n",
    "**目的関数: コンピュータ1の実行時間と他の実行時間の差を小さくする**\n",
    "\n",
    "コンピュータ1の実行時間を基準とし、それと他のコンピュータの実行時間の差を最小にすることを考えます。これにより実行時間のばらつきが抑えられ、タスクが分散されるようになります。\n",
    "\n",
    "$$\n",
    "\\min\\left\\{ \\sum_{j=1}^{M-1} (A_1 -A_j)^2\\right\\} \n",
    "\\tag{2}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## JijModelingを用いた実装\n",
    "\n",
    "### 変数の定義\n",
    "\n",
    "式(1), (2)で用いられている変数を、以下のようにして定義しましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import jijmodeling as jm\n",
    "\n",
    "# defin variables\n",
    "L = jm.Placeholder(\"L\", ndim=1)\n",
    "N = L.len_at(0, latex=\"N\")\n",
    "M = jm.Placeholder(\"M\")\n",
    "x = jm.BinaryVar(\"x\", shape=(N, M))\n",
    "i = jm.Element(\"i\", belong_to=(0, N))\n",
    "j = jm.Element(\"j\", belong_to=(0, M))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`L=jm.Placeholder('L', ndim=1)`でコンピュータに実行させるタスクの実行時間のリストを定義します。\n",
    "そのリストの長さを`N=L.len_at(0, latex=\"N\")`として定義します。`M`はコンピュータの台数、`x`はバイナリ変数です。\n",
    "最後に$x_{i, j}$のように、変数の添字として使うものを`i, j`として定義します。\n",
    "\n",
    "### 制約と目的関数の実装\n",
    "\n",
    "式(1), (2)を実装しましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# set problem\n",
    "problem = jm.Problem('Integer Jobs')\n",
    "# set constraint: job must be executed using a certain node\n",
    "problem += jm.Constraint('onehot', x[i, :].sum()==1, forall=i)\n",
    "# set objective function: minimize difference between node 0 and others\n",
    "problem += jm.sum((j, j!=0), jm.sum(i, L[i]*(x[i, 0]-x[i, j]))**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`x[i, :].sum()`とすることで、$\\sum_j x_{i, j}$を簡潔に実装することができます。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "実装した数式をJupyter Notebookで表示してみましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{array}{cccc}\\text{Problem:} & \\text{Integer Jobs} & & \\\\& & \\min \\quad \\displaystyle \\sum_{\\substack{j = 0\\\\j \\neq 0}}^{M - 1} \\left(\\left(\\sum_{i = 0}^{N - 1} L_{i} \\cdot \\left(x_{i, 0} - x_{i, j}\\right)\\right)^{2}\\right) & \\\\\\text{{s.t.}} & & & \\\\ & \\text{onehot} & \\displaystyle \\sum_{\\ast_{1} = 0}^{M - 1} x_{i, \\ast_{1}} = 1 & \\forall i \\in \\left\\{0,\\ldots,N - 1\\right\\} \\\\\\text{{where}} & & & \\\\& x & 2\\text{-dim binary variable}\\\\\\end{array}$$"
      ],
      "text/plain": [
       "<jijmodeling.Problem at 0x2663790>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### インスタンスの作成\n",
    "\n",
    "インスタンスを以下のようにします。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# set a list of jobs\n",
    "inst_L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n",
    "# set the number of Nodes\n",
    "inst_M = 3\n",
    "instance_data = {'L': inst_L, 'M': inst_M}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "先程の具体例と同様に、$\\{1, 2, \\dots, 10\\}$の10個のタスクを、3台のコンピュータに分散させる状況を考えます。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### JijModeling transpilerによるPyQUBOへの変換\n",
    "\n",
    "ここまで行われてきた実装は、全てJijModelingによるものでした。\n",
    "これを[PyQUBO](https://pyqubo.readthedocs.io/en/latest/)に変換することで、OpenJijはもちろん、他のソルバーを用いた組合せ最適化計算を行うことが可能になります。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import jijmodeling_transpiler as jmt\n",
    "\n",
    "# compile\n",
    "compiled_model = jmt.core.compile_model(problem, instance_data, {})\n",
    "# get qubo model\n",
    "pubo_builder = jmt.core.pubo.transpile_to_pubo(compiled_model=compiled_model, relax_method=jmt.core.pubo.RelaxationMethod.AugmentedLagrangian)\n",
    "qubo, const = pubo_builder.get_qubo_dict(multipliers={\"onehot\": 1.0})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### OpenJijによる最適化計算の実行\n",
    "\n",
    "今回はOpenJijのシミュレーテッド・アニーリングを用いて、最適化問題を解いてみましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import openjij as oj\n",
    "\n",
    "# set sampler\n",
    "sampler = oj.SASampler()\n",
    "# solve problem\n",
    "response = sampler.sample_qubo(qubo, num_reads=100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`SASampler`を設定し、そのサンプラーに先程作成したQUBOモデルの`qubo`を入力することで、計算結果が得られます。\n",
    "\n",
    "### デコードと解の表示\n",
    "\n",
    "計算結果をデコードします。\n",
    "また実行可能解の中から目的関数値が最小のものを選び出してみましょう。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "このようにして得られた結果から、タスク実行が分散されている様子を見てみましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjMAAAGwCAYAAABcnuQpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAr20lEQVR4nO3de1SVdaLG8ecVY0sGGCooR0DTNO9WmqWNolFK5qWasnNMUTrjaKgZXTkzjpkZ6pSHTJfO1ORlnVJnxjQn0y6MYqZmimhOplgoTHkrDQRtp/CeP1ru5Q4ve+uGd//k+1nrXYv3994eWLvl0+99996Wbdu2AAAADFXL6QAAAACXgzIDAACMRpkBAABGo8wAAACjUWYAAIDRKDMAAMBolBkAAGC02k4HqGoVFRX69ttvFR4eLsuynI4DAAB8YNu2jh8/rtjYWNWqdeG5lyu+zHz77beKi4tzOgYAALgERUVFatKkyQX3ueLLTHh4uKSf/xgREREOpwEAAL4oKSlRXFyc59/xC7niy8yZW0sRERGUGQAADOPLIyI8AAwAAIxGmQEAAEajzAAAAKNRZgAAgNEoMwAAwGiUGQAAYDTKDAAAMBplBgAAGI0yAwAAjEaZAQAARqPMAAAAo1FmAACA0SgzAADAaJQZAABgNMoMAAAwWm2nAwAAzNb02ZVOR4CD9k3t53QEZmYAAIDZKDMAAMBolBkAAGA0ygwAADAaZQYAABiNMgMAAIxGmQEAAEajzAAAAKNRZgAAgNEoMwAAwGiUGQAAYDTKDAAAMBplBgAAGI0yAwAAjOZomVm3bp369++v2NhYWZal5cuXe20vLS3VmDFj1KRJE4WFhalNmzaaO3euM2EBAEBQcrTMlJWVqWPHjpo9e/Y5t6enp2v16tX6v//7P+3atUvjx4/XmDFjtGLFimpOCgAAglVtJy+enJys5OTk827fsGGDUlJSlJiYKEkaOXKk/vSnP2nz5s0aMGDAOY9xu91yu92e9ZKSkoBmBgAAwcXRMnMx3bp104oVK5SamqrY2FitXbtWe/bs0f/+7/+e95jMzExNmjSp2jI2fXZltV0LwWff1H5OR+A1WMMFw2sQcFpQPwD86quvqk2bNmrSpIlCQ0PVt29fzZ49Wz169DjvMRkZGSouLvYsRUVF1ZgYAABUt6CemXn11Ve1adMmrVixQgkJCVq3bp3S0tIUGxurpKSkcx7jcrnkcrmqOSkAAHBK0JaZkydP6n/+53+0bNky9ev38zRqhw4dlJeXp5deeum8ZQYAANQsQXub6dSpUzp16pRq1fKOGBISooqKCodSAQCAYOPozExpaan27t3rWS8oKFBeXp6ioqIUHx+vnj176qmnnlJYWJgSEhKUk5OjhQsXasaMGQ6mBgAAwcTRMrNlyxb16tXLs56eni5JSklJ0fz587V48WJlZGRoyJAhOnr0qBISEjRlyhSNGjXKqcgAACDIOFpmEhMTZdv2ebc3atRI8+bNq8ZEAADANEH7zAwAAIAvKDMAAMBolBkAAGA0ygwAADAaZQYAABiNMgMAAIxGmQEAAEajzAAAAKNRZgAAgNEoMwAAwGiUGQAAYDTKDAAAMBplBgAAGI0yAwAAjEaZAQAARqPMAAAAo1FmAACA0SgzAADAaJQZAABgNMoMAAAwGmUGAAAYjTIDAACMRpkBAABGo8wAAACjUWYAAIDRKDMAAMBojpaZdevWqX///oqNjZVlWVq+fHmlfXbt2qUBAwYoMjJSdevWVZcuXVRYWFj9YQEAQFBytMyUlZWpY8eOmj179jm3f/XVV7r99tt1ww03aO3atdqxY4cmTJigOnXqVHNSAAAQrGo7efHk5GQlJyefd/vvfvc73X333Zo+fbpnrHnz5hc8p9vtltvt9qyXlJRcflAAABC0gvaZmYqKCq1cuVItW7ZUnz59FB0dra5du57zVtTZMjMzFRkZ6Vni4uKqJzAAAHBE0JaZw4cPq7S0VFOnTlXfvn31wQcf6N5779V9992nnJyc8x6XkZGh4uJiz1JUVFSNqQEAQHVz9DbThVRUVEiSBg4cqMcff1yS1KlTJ23YsEFz585Vz549z3mcy+WSy+WqtpwAAMBZQTsz06BBA9WuXVtt2rTxGm/dujXvZgIAAB5BW2ZCQ0PVpUsX7d6922t8z549SkhIcCgVAAAINo7eZiotLdXevXs96wUFBcrLy1NUVJTi4+P11FNPafDgwerRo4d69eql1atX6x//+IfWrl3rXGgAABBUHC0zW7ZsUa9evTzr6enpkqSUlBTNnz9f9957r+bOnavMzEyNGzdOrVq10tKlS3X77bc7FRkAAAQZR8tMYmKibNu+4D6pqalKTU2tpkQAAMA0QfvMDAAAgC8oMwAAwGiUGQAAYDTKDAAAMBplBgAAGI0yAwAAjEaZAQAARqPMAAAAo1FmAACA0SgzAADAaJQZAABgNMoMAAAwGmUGAAAYjTIDAACMRpkBAABGo8wAAACjUWYAAIDRKDMAAMBolBkAAGA0ygwAADAaZQYAABiNMgMAAIxGmQEAAEajzAAAAKNRZgAAgNEoMwAAwGiOlpl169apf//+io2NlWVZWr58+Xn3HTVqlCzLUlZWVrXlAwAAwc/RMlNWVqaOHTtq9uzZF9xv2bJl2rRpk2JjY6spGQAAMEVtJy+enJys5OTkC+7zzTffaOzYsXr//ffVr1+/i57T7XbL7XZ71ktKSi47JwAACF5B/cxMRUWFhg4dqqeeekpt27b16ZjMzExFRkZ6lri4uCpOCQAAnBTUZWbatGmqXbu2xo0b5/MxGRkZKi4u9ixFRUVVmBAAADjN0dtMF7J161a98sorys3NlWVZPh/ncrnkcrmqMBkAAAgmQTsz8/HHH+vw4cOKj49X7dq1Vbt2be3fv19PPPGEmjZt6nQ8AAAQJIJ2Zmbo0KFKSkryGuvTp4+GDh2qESNGOJQKAAAEG0fLTGlpqfbu3etZLygoUF5enqKiohQfH6/69et77X/VVVepUaNGatWqVXVHBQAAQcrRMrNlyxb16tXLs56eni5JSklJ0fz58x1KBQAATOJomUlMTJRt2z7vv2/fvqoLAwAAjBS0DwADAAD4gjIDAACMRpkBAABGo8wAAACjUWYAAIDRKDMAAMBolBkAAGA0ygwAADAaZQYAABiNMgMAAIxGmQEAAEajzAAAAKNRZgAAgNEoMwAAwGiUGQAAYDTKDAAAMBplBgAAGO2Sy8xPP/2k3bt36/Tp04HMAwAA4Be/y8yJEyf0yCOP6Oqrr1bbtm1VWFgoSRo7dqymTp0a8IAAAAAX4neZycjI0Pbt27V27VrVqVPHM56UlKQlS5YENBwAAMDF1Pb3gOXLl2vJkiW69dZbZVmWZ7xt27b66quvAhoOAADgYvyemTly5Iiio6MrjZeVlXmVGwAAgOrgd5np3LmzVq5c6Vk/U2Bef/113XbbbYFLBgAA4AO/bzO9+OKLSk5O1hdffKHTp0/rlVde0RdffKENGzYoJyenKjICAACcl98zM7fffrvy8vJ0+vRptW/fXh988IGio6O1ceNG3XzzzVWREQAA4Lz8npmRpObNm+u1114LdBYAAAC/XfKH5h0+fFg7d+7Ujh07vBZ/rFu3Tv3791dsbKwsy9Ly5cs9206dOqVnnnlG7du3V926dRUbG6thw4bp22+/vdTIAADgCuT3zMzWrVuVkpKiXbt2ybZtr22WZam8vNznc5WVlaljx45KTU3Vfffd57XtxIkTys3N1YQJE9SxY0cdO3ZMjz32mAYMGKAtW7b4GxsAAFyh/C4zqampatmypf7yl78oJibmst6OnZycrOTk5HNui4yM1Icffug1NmvWLN1yyy0qLCxUfHz8OY9zu91yu92e9ZKSkkvOBwAAgp/fZebrr7/W0qVL1aJFi6rIc0HFxcWyLEv16tU77z6ZmZmaNGlS9YUCAACO8vuZmTvuuEPbt2+viiwX9OOPP+qZZ57Rf/7nfyoiIuK8+2VkZKi4uNizFBUVVWNKAABQ3fyemXn99deVkpKinTt3ql27drrqqqu8tg8YMCBg4c44deqUHnzwQdm2rTlz5lxwX5fLJZfLFfAMAAAgOPldZjZu3KhPPvlEq1atqrTN3weAfXGmyOzfv1///Oc/LzgrAwAAah6/bzONHTtWDz/8sA4cOKCKigqvpaqKTH5+vj766CPVr18/oOcHAADm83tm5vvvv9fjjz+umJiYy754aWmp9u7d61kvKChQXl6eoqKi1LhxY/36179Wbm6u3n33XZWXl+vgwYOSpKioKIWGhl729QEAgPn8LjP33Xef1qxZo+bNm1/2xbds2aJevXp51tPT0yVJKSkpeu6557RixQpJUqdOnbyOW7NmjRITEy/7+gAAwHx+l5mWLVsqIyND69evV/v27Ss9ADxu3Difz5WYmFjpg/fOdqFtAAAA0iW+m+maa65RTk5OpW/JtizLrzIDAABwufwuMwUFBVWRAwAA4JJc8hdNAgAABAOfZmbS09M1efJk1a1b1/OQ7vnMmDEjIMEAAAB84VOZ2bZtm06dOuX5GQAAIFj4VGbWrFlzzp8BAACc5vczM6mpqTp+/Hil8bKyMqWmpgYkFAAAgK/8LjMLFizQyZMnK42fPHlSCxcuDEgoAAAAX/n81uySkhLZti3btnX8+HHVqVPHs628vFzvvfeeoqOjqyQkAADA+fhcZurVqyfLsmRZllq2bFlpu2VZmjRpUkDDAQAAXIzPZWbNmjWybVu9e/fW0qVLFRUV5dkWGhqqhIQExcbGVklIAACA8/G5zPTs2VPSz58AHB8fL8uyqiwUAACAr/z+OoOEhISqyAEAAHBJ+DoDAABgNMoMAAAwGmUGAAAYjTIDAACM5neZOXTokIYOHarY2FjVrl1bISEhXgsAAEB18vvdTMOHD1dhYaEmTJigxo0b8xZtAADgKL/LzPr16/Xxxx+rU6dOVRAHAADAP37fZoqLi5Nt21WRBQAAwG9+l5msrCw9++yz2rdvXxXEAQAA8I/ft5kGDx6sEydOqHnz5rr66qt11VVXeW0/evRowMIBAABcjN9lJisrqwpiAAAAXBq/y0xKSkpV5AAAALgkfpcZSSovL9fy5cu1a9cuSVLbtm01YMAAPmcGAABUO78fAN67d69at26tYcOG6e2339bbb7+thx9+WG3bttVXX33l17nWrVun/v37KzY2VpZlafny5V7bbdvWH/7wBzVu3FhhYWFKSkpSfn6+v5EBAMAVzO8yM27cODVv3lxFRUXKzc1Vbm6uCgsL1axZM40bN86vc5WVlaljx46aPXv2ObdPnz5dM2fO1Ny5c/Xpp5+qbt266tOnj3788Ud/YwMAgCuU37eZcnJytGnTJkVFRXnG6tevr6lTp6p79+5+nSs5OVnJycnn3GbbtrKysvT73/9eAwcOlCQtXLhQMTExWr58uR566KFzHud2u+V2uz3rJSUlfmUCAABm8XtmxuVy6fjx45XGS0tLFRoaGpBQklRQUKCDBw8qKSnJMxYZGamuXbtq48aN5z0uMzNTkZGRniUuLi5gmQAAQPDxu8zcc889GjlypD799FPZti3btrVp0yaNGjVKAwYMCFiwgwcPSpJiYmK8xmNiYjzbziUjI0PFxcWepaioKGCZAABA8PH7NtPMmTOVkpKi2267zfOBeadPn9aAAQP0yiuvBDygv1wul1wul9MxAABANfG7zNSrV0/vvPOO8vPz9eWXX0qSWrdurRYtWgQ0WKNGjSRJhw4dUuPGjT3jhw4d4ksuAQCAxyV9zowkXX/99br++usDmcVLs2bN1KhRI2VnZ3vKS0lJiT799FONHj26yq4LAADM4lOZSU9P1+TJk1W3bl2lp6dfcN8ZM2b4fPHS0lLt3bvXs15QUKC8vDxFRUUpPj5e48eP1wsvvKDrr79ezZo104QJExQbG6tBgwb5fA0AAHBl86nMbNu2TadOnfL8HChbtmxRr169POtnilJKSormz5+vp59+WmVlZRo5cqR++OEH3X777Vq9erXq1KkTsAwAAMBsPpWZNWvWnPPny5WYmCjbts+73bIsPf/883r++ecDdk0AAHBl8fut2ampqef8nJmysjKlpqYGJBQAAICv/C4zCxYs0MmTJyuNnzx5UgsXLgxIKAAAAF/5/G6mkpISz4fkHT9+3Ou5lfLycr333nuKjo6ukpAAAADn43OZqVevnizLkmVZatmyZaXtlmVp0qRJAQ0HAABwMT6XmTVr1si2bfXu3VtLly71+qLJ0NBQJSQkKDY2tkpCAgAAnI/PZaZnz56Sfv4smPj4eFmWVWWhAAAAfOX3JwDv379f+/fvP+/2Hj16XFYgAAAAf/hdZhITEyuNnT1LU15eflmBAAAA/OH3W7OPHTvmtRw+fFirV69Wly5d9MEHH1RFRgAAgPPye2YmMjKy0tidd96p0NBQpaena+vWrQEJBgAA4Au/Z2bOJyYmRrt37w7U6QAAAHzi98zMjh07vNZt29aBAwc0depUderUKVC5AAAAfOJ3menUqZMsy6r0BZG33nqr3njjjYAFAwAA8IXfZaagoMBrvVatWmrYsKHX1xsAAABUF7/LTEJCQlXkAAAAuCR+PwA8btw4zZw5s9L4rFmzNH78+EBkAgAA8JnfZWbp0qXq3r17pfFu3brp73//e0BCAQAA+MrvMvP999+f87NmIiIi9N133wUkFAAAgK/8LjMtWrTQ6tWrK42vWrVK1113XUBCAQAA+MrvB4DT09M1ZswYHTlyRL1795YkZWdn6+WXX1ZWVlag8wEAAFyQ32UmNTVVbrdbU6ZM0eTJkyVJTZs21Zw5czRs2LCABwQAALgQv8uMJI0ePVqjR4/WkSNHFBYWpmuuuSbQuQAAAHxySd/NdPr0aX300Ud6++23PZ8E/O2336q0tDSg4QAAAC7G75mZ/fv3q2/fviosLJTb7dadd96p8PBwTZs2TW63W3Pnzq2KnAAAAOfk98zMY489ps6dO+vYsWMKCwvzjN97773Kzs4OaDgAAICL8Xtm5uOPP9aGDRsUGhrqNd60aVN98803AQsGAADgC79nZioqKlReXl5p/N///rfCw8MDEuqM8vJyTZgwQc2aNVNYWJiaN2+uyZMnV/rGbgAAUHP5XWbuuusur8+TsSxLpaWlmjhxou6+++5AZtO0adM0Z84czZo1S7t27dK0adM0ffp0vfrqqwG9DgAAMJfft5lefvll9enTR23atNGPP/6o//qv/1J+fr4aNGigRYsWBTTchg0bNHDgQPXr10/Sz7eyFi1apM2bNwf0OgAAwFx+l5kmTZpo+/btWrJkibZv367S0lI98sgjGjJkiNcDwYHQrVs3/fnPf9aePXvUsmVLbd++XevXr9eMGTPOe4zb7Zbb7fasl5SUBDQTAAAILn6XmSNHjqhhw4YaMmSIhgwZ4rXt888/V/v27QMW7tlnn1VJSYluuOEGhYSEqLy8XFOmTKl03bNlZmZq0qRJAcsAAACCm9/PzLRv314rV66sNP7SSy/plltuCUioM/7617/qzTff1FtvvaXc3FwtWLBAL730khYsWHDeYzIyMlRcXOxZioqKApoJAAAEl0v6osn7779fI0aM0IwZM3T06FENGzZMn3/+ud56662Ahnvqqaf07LPP6qGHHpL0c5Hav3+/MjMzlZKScs5jXC6XXC5XQHMAAIDg5ffMzNNPP62NGzfq448/VocOHdShQwe5XC7t2LFD9957b0DDnThxQrVqeUcMCQlRRUVFQK8DAADMdUlfNNmiRQu1a9dOS5culSQNHjxYjRo1CmgwSerfv7+mTJmi+Ph4tW3bVtu2bdOMGTOUmpoa8GsBAAAz+T0z88knn6hDhw7Kz8/Xjh07NGfOHI0dO1aDBw/WsWPHAhru1Vdf1a9//Ws9+uijat26tZ588kn99re/1eTJkwN6HQAAYC6/y0zv3r01ePBgbdq0Sa1bt9Z///d/a9u2bSosLAzoO5kkKTw8XFlZWdq/f79Onjypr776Si+88EKlr1IAAAA1l9+3mT744AP17NnTa6x58+b65JNPNGXKlIAFAwAA8IXfMzO/LDKeE9WqpQkTJlx2IAAAAH/4XGbuvvtuFRcXe9anTp2qH374wbP+/fffq02bNgENBwAAcDE+l5n333/f62sCXnzxRR09etSzfvr0ae3evTuw6QAAAC7C5zJj2/YF1wEAAJzg9zMzAAAAwcTnMmNZlizLqjQGAADgJJ/fmm3btoYPH+753qMff/xRo0aNUt26dSXJ63kaAACA6uJzmfnlFzs+/PDDlfYZNmzY5ScCAADwg89lZt68eVWZAwAA4JLwADAAADAaZQYAABiNMgMAAIxGmQEAAEajzAAAAKNRZgAAgNEoMwAAwGiUGQAAYDTKDAAAMBplBgAAGI0yAwAAjEaZAQAARqPMAAAAo1FmAACA0SgzAADAaJQZAABgtKAvM998840efvhh1a9fX2FhYWrfvr22bNnidCwAABAkajsd4EKOHTum7t27q1evXlq1apUaNmyo/Px8XXvttU5HAwAAQSKoy8y0adMUFxenefPmecaaNWvmYCIAABBsgvo204oVK9S5c2c98MADio6O1o033qjXXnvtgse43W6VlJR4LQAA4MoV1GXm66+/1pw5c3T99dfr/fff1+jRozVu3DgtWLDgvMdkZmYqMjLSs8TFxVVjYgAAUN2CusxUVFTopptu0osvvqgbb7xRI0eO1G9+8xvNnTv3vMdkZGSouLjYsxQVFVVjYgAAUN2Cusw0btxYbdq08Rpr3bq1CgsLz3uMy+VSRESE1wIAAK5cQV1munfvrt27d3uN7dmzRwkJCQ4lAgAAwSaoy8zjjz+uTZs26cUXX9TevXv11ltv6c9//rPS0tKcjgYAAIJEUJeZLl26aNmyZVq0aJHatWunyZMnKysrS0OGDHE6GgAACBJB/TkzknTPPffonnvucToGAAAIUkE9MwMAAHAxlBkAAGA0ygwAADAaZQYAABiNMgMAAIxGmQEAAEajzAAAAKNRZgAAgNEoMwAAwGiUGQAAYDTKDAAAMBplBgAAGI0yAwAAjEaZAQAARqPMAAAAo1FmAACA0SgzAADAaJQZAABgNMoMAAAwGmUGAAAYjTIDAACMRpkBAABGo8wAAACjUWYAAIDRKDMAAMBolBkAAGA0o8rM1KlTZVmWxo8f73QUAAAQJIwpM5999pn+9Kc/qUOHDk5HAQAAQcSIMlNaWqohQ4botdde07XXXut0HAAAEESMKDNpaWnq16+fkpKSLrqv2+1WSUmJ1wIAAK5ctZ0OcDGLFy9Wbm6uPvvsM5/2z8zM1KRJk6o4FQAACBZBPTNTVFSkxx57TG+++abq1Knj0zEZGRkqLi72LEVFRVWcEgAAOCmoZ2a2bt2qw4cP66abbvKMlZeXa926dZo1a5bcbrdCQkK8jnG5XHK5XNUdFQAAOCSoy8wdd9yhzz//3GtsxIgRuuGGG/TMM89UKjIAAKDmCeoyEx4ernbt2nmN1a1bV/Xr1680DgAAaqagfmYGAADgYoJ6ZuZc1q5d63QEAAAQRJiZAQAARqPMAAAAo1FmAACA0SgzAADAaJQZAABgNMoMAAAwGmUGAAAYjTIDAACMRpkBAABGo8wAAACjUWYAAIDRKDMAAMBolBkAAGA0ygwAADAaZQYAABiNMgMAAIxGmQEAAEajzAAAAKNRZgAAgNEoMwAAwGiUGQAAYDTKDAAAMBplBgAAGI0yAwAAjEaZAQAARqPMAAAAowV9mcnMzFSXLl0UHh6u6OhoDRo0SLt373Y6FgAACBJBX2ZycnKUlpamTZs26cMPP9SpU6d01113qayszOloAAAgCNR2OsDFrF692mt9/vz5io6O1tatW9WjRw+HUgEAgGAR9GXml4qLiyVJUVFR59zudrvldrs96yUlJdWSCwAAOCPobzOdraKiQuPHj1f37t3Vrl27c+6TmZmpyMhIzxIXF1fNKQEAQHUyqsykpaVp586dWrx48Xn3ycjIUHFxsWcpKiqqxoQAAKC6GXObacyYMXr33Xe1bt06NWnS5Lz7uVwuuVyuakwGAACcFPRlxrZtjR07VsuWLdPatWvVrFkzpyMBAIAgEvRlJi0tTW+99ZbeeecdhYeH6+DBg5KkyMhIhYWFOZwOAAA4LeifmZkzZ46Ki4uVmJioxo0be5YlS5Y4HQ0AAASBoJ+ZsW3b6QgAACCIBf3MDAAAwIVQZgAAgNEoMwAAwGiUGQAAYDTKDAAAMBplBgAAGI0yAwAAjEaZAQAARqPMAAAAo1FmAACA0SgzAADAaJQZAABgNMoMAAAwGmUGAAAYjTIDAACMRpkBAABGo8wAAACjUWYAAIDRKDMAAMBolBkAAGA0ygwAADAaZQYAABiNMgMAAIxGmQEAAEajzAAAAKNRZgAAgNGMKDOzZ89W06ZNVadOHXXt2lWbN292OhIAAAgSQV9mlixZovT0dE2cOFG5ubnq2LGj+vTpo8OHDzsdDQAABIGgLzMzZszQb37zG40YMUJt2rTR3LlzdfXVV+uNN95wOhoAAAgCtZ0OcCE//fSTtm7dqoyMDM9YrVq1lJSUpI0bN57zGLfbLbfb7VkvLi6WJJWUlFRJxgr3iSo5L8xQVa8rf/AarNl4DcJpVfUaPHNe27Yvum9Ql5nvvvtO5eXliomJ8RqPiYnRl19+ec5jMjMzNWnSpErjcXFxVZIRNVtkltMJUNPxGoTTqvo1ePz4cUVGRl5wn6AuM5ciIyND6enpnvWKigodPXpU9evXl2VZDia78pSUlCguLk5FRUWKiIhwOg5qIF6DcBqvwapj27aOHz+u2NjYi+4b1GWmQYMGCgkJ0aFDh7zGDx06pEaNGp3zGJfLJZfL5TVWr169qooISREREfxHDEfxGoTTeA1WjYvNyJwR1A8Ah4aG6uabb1Z2drZnrKKiQtnZ2brtttscTAYAAIJFUM/MSFJ6erpSUlLUuXNn3XLLLcrKylJZWZlGjBjhdDQAABAEgr7MDB48WEeOHNEf/vAHHTx4UJ06ddLq1asrPRSM6udyuTRx4sRKt/WA6sJrEE7jNRgcLNuX9zwBAAAEqaB+ZgYAAOBiKDMAAMBolBkAAGA0ygwAADAaZQaXZPbs2WratKnq1Kmjrl27avPmzU5HQg2ybt069e/fX7GxsbIsS8uXL3c6EmqYzMxMdenSReHh4YqOjtagQYO0e/dup2PVWJQZ+G3JkiVKT0/XxIkTlZubq44dO6pPnz46fPiw09FQQ5SVlaljx46aPXu201FQQ+Xk5CgtLU2bNm3Shx9+qFOnTumuu+5SWVmZ09FqJN6aDb917dpVXbp00axZsyT9/KnMcXFxGjt2rJ599lmH06GmsSxLy5Yt06BBg5yOghrsyJEjio6OVk5Ojnr06OF0nBqHmRn45aefftLWrVuVlJTkGatVq5aSkpK0ceNGB5MBgHOKi4slSVFRUQ4nqZkoM/DLd999p/Ly8kqfwBwTE6ODBw86lAoAnFNRUaHx48ere/fuateundNxaqSg/zoDAACCWVpamnbu3Kn169c7HaXGoszALw0aNFBISIgOHTrkNX7o0CE1atTIoVQA4IwxY8bo3Xff1bp169SkSROn49RY3GaCX0JDQ3XzzTcrOzvbM1ZRUaHs7GzddtttDiYDgOpj27bGjBmjZcuW6Z///KeaNWvmdKQajZkZ+C09PV0pKSnq3LmzbrnlFmVlZamsrEwjRoxwOhpqiNLSUu3du9ezXlBQoLy8PEVFRSk+Pt7BZKgp0tLS9NZbb+mdd95ReHi455nByMhIhYWFOZyu5uGt2bgks2bN0h//+EcdPHhQnTp10syZM9W1a1enY6GGWLt2rXr16lVpPCUlRfPnz6/+QKhxLMs65/i8efM0fPjw6g0DygwAADAbz8wAAACjUWYAAIDRKDMAAMBolBkAAGA0ygwAADAaZQYAABiNMgMAAIxGmQEAAEajzABAFVi7dq0sy9IPP/zgdBTgikeZAQx28OBBjR07Vtddd51cLpfi4uLUv39/ry8CDWbz589XvXr1nI4BwHB80SRgqH379ql79+6qV6+e/vjHP6p9+/Y6deqU3n//faWlpenLL790OmK1KS8vl2VZqlXryv//s59++kmhoaFOxwCCypX/Xz5whXr00UdlWZY2b96s+++/Xy1btlTbtm2Vnp6uTZs2efYrLCzUwIEDdc011ygiIkIPPvigDh065Nn+3HPPqVOnTnrjjTcUHx+va665Ro8++qjKy8s1ffp0NWrUSNHR0ZoyZYrX9S3L0pw5c5ScnKywsDBdd911+vvf/+7Zfq7bLHl5ebIsS/v27dPatWs1YsQIFRcXy7IsWZal5557TpLkdrv15JNP6j/+4z9Ut25dde3aVWvXrvWc58yMzooVK9SmTRu5XC4VFhZW+hudyZCdna3OnTvr6quvVrdu3bR7927PPsOHD9egQYO8jhs/frwSExM964mJiRo7dqzGjx+va6+9VjExMXrttdc83xYfHh6uFi1aaNWqVZUyfPLJJ+rQoYPq1KmjW2+9VTt37vTavn79ev3qV79SWFiY4uLiNG7cOJWVlXm2N23aVJMnT9awYcMUERGhkSNH6qefftKYMWPUuHFj1alTRwkJCcrMzKx0baCmoMwABjp69KhWr16ttLQ01a1bt9L2M7duKioqNHDgQB09elQ5OTn68MMP9fXXX2vw4MFe+3/11VdatWqVVq9erUWLFukvf/mL+vXrp3//+9/KycnRtGnT9Pvf/16ffvqp13ETJkzQ/fffr+3bt2vIkCF66KGHtGvXLp9+h27duikrK0sRERE6cOCADhw4oCeffFKSNGbMGG3cuFGLFy/Wjh079MADD6hv377Kz8/3HH/ixAlNmzZNr7/+uv71r38pOjr6vNf63e9+p5dffllbtmxR7dq1lZqa6lPGsy1YsEANGjTQ5s2bNXbsWI0ePVoPPPCAunXrptzcXN11110aOnSoTpw44XXcU089pZdfflmfffaZGjZsqP79++vUqVOSfv679+3bV/fff7927NihJUuWaP369RozZozXOV566SV17NhR27Zt04QJEzRz5kytWLFCf/3rX7V79269+eabatq0qd+/E3DFsAEY59NPP7Ul2W+//fYF9/vggw/skJAQu7Cw0DP2r3/9y5Zkb9682bZt2544caJ99dVX2yUlJZ59+vTpYzdt2tQuLy/3jLVq1crOzMz0rEuyR40a5XW9rl272qNHj7Zt27bXrFljS7KPHTvm2b5t2zZbkl1QUGDbtm3PmzfPjoyM9DrH/v377ZCQEPubb77xGr/jjjvsjIwMz3GS7Ly8vAv+/mcyfPTRR56xlStX2pLskydP2rZt2ykpKfbAgQO9jnvsscfsnj17etZ79uxp33777Z7106dP23Xr1rWHDh3qGTtw4IAtyd64caPXtRcvXuzZ5/vvv7fDwsLsJUuW2LZt24888og9cuRIr2t//PHHdq1atTz5EhIS7EGDBnntM3bsWLt37952RUXFBX9/oKbgmRnAQLZt+7Tfrl27FBcXp7i4OM9YmzZtVK9ePe3atUtdunSR9POtjPDwcM8+MTExCgkJ8XoGJSYmRocPH/Y6/2233VZpPS8vz99fx8vnn3+u8vJytWzZ0mvc7Xarfv36nvXQ0FB16NDBp3OevV/jxo0lSYcPH1Z8fLzPuc4+R0hIiOrXr6/27dt7xmJiYjznPdvZf6OoqCi1atXKM3u1fft27dixQ2+++aZnH9u2VVFRoYKCArVu3VqS1LlzZ69zDh8+XHfeeadatWqlvn376p577tFdd93l8+8CXGkoM4CBrr/+elmWFbCHfK+66iqvdcuyzjlWUVHh8znPFKGzi9eZ2ysXUlpaqpCQEG3dulUhISFe26655hrPz2FhYbIsy6csZ/8uZ44587vUqlWrUjk8V86L/Y1+eV5flJaW6re//a3GjRtXadvZReuXtxJvuukmFRQUaNWqVfroo4/04IMPKikpyeuZJaAm4ZkZwEBRUVHq06ePZs+e7fWw6BlnHrpt3bq1ioqKVFRU5Nn2xRdf6IcfflCbNm0uO8fZDxqfWT8zm9CwYUNJ0oEDBzzbfzlrExoaqvLycq+xG2+8UeXl5Tp8+LBatGjhtTRq1OiyM/9Sw4YNvTKeK+flOPtvdOzYMe3Zs8fzN7rpppv0xRdfVPo9W7RocdF3LEVERGjw4MF67bXXtGTJEi1dulRHjx4NWG7AJJQZwFCzZ89WeXm5brnlFi1dulT5+fnatWuXZs6c6bm1kZSUpPbt22vIkCHKzc3V5s2bNWzYMPXs2bPSrYtL8be//U1vvPGG9uzZo4kTJ2rz5s2eh1dbtGihuLg4Pffcc8rPz9fKlSv18ssvex3ftGlTlZaWKjs7W999951OnDihli1basiQIRo2bJjefvttFRQUaPPmzcrMzNTKlSsvO/Mv9e7dW1u2bNHChQuVn5+viRMnVnrH0eV4/vnnlZ2drZ07d2r48OFq0KCB591TzzzzjDZs2KAxY8YoLy9P+fn5eueddyo9APxLM2bM0KJFi/Tll19qz549+tvf/qZGjRrxmT2osSgzgKGuu+465ebmqlevXnriiSfUrl073XnnncrOztacOXMk/Xzr45133tG1116rHj16KCkpSdddd52WLFkSkAyTJk3S4sWL1aFDBy1cuFCLFi3yzPhcddVVnn9wO3TooGnTpumFF17wOr5bt24aNWqUBg8erIYNG2r69OmSpHnz5mnYsGF64okn1KpVKw0aNEifffaZX8+4+KpPnz6aMGGCnn76aXXp0kXHjx/XsGHDAnb+qVOn6rHHHtPNN9+sgwcP6h//+Idn1qVDhw7KycnRnj179Ktf/Uo33nij/vCHPyg2NvaC5wwPD9f06dPVuXNndenSRfv27dN7771XIz5nBzgXy/b1SUIAOItlWVq2bFmlz2gBgOpGjQcAAEajzAAAAKPx1mwAl4Q71ACCBTMzAADAaJQZAABgNMoMAAAwGmUGAAAYjTIDAACMRpkBAABGo8wAAACjUWYAAIDR/h88DN8+o0AUCgAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "# decode a result to JijModeling sampleset\n",
    "sampleset = jmt.core.pubo.decode_from_openjij(response, pubo_builder, compiled_model)\n",
    "# get feasible samples from sampleset\n",
    "feasible_samples = sampleset.feasible()\n",
    "# get the values of objective function of feasible samples\n",
    "feasible_objectives = [objective for objective in feasible_samples.evaluation.objective]\n",
    "if len(feasible_objectives) == 0:\n",
    "    print(\"No feasible solution found ...\")\n",
    "else:\n",
    "    # get the index of the loweest objective value\n",
    "    lowest_index = np.argmin(feasible_objectives)\n",
    "    # get the indices of x == 1\n",
    "    tasks, nodes = feasible_samples.record.solution[\"x\"][lowest_index][0]\n",
    "    # initialize execution time\n",
    "    exec_time = [0] * inst_M\n",
    "    # compute summation of execution each nodes\n",
    "    for i, j in zip(tasks, nodes):\n",
    "        exec_time[j] += inst_L[i]\n",
    "    # make plot\n",
    "    y_axis = range(0, max(exec_time)+1, 2)\n",
    "    node_names = [str(j) for j in range(inst_M)]\n",
    "    fig = plt.figure()\n",
    "    plt.bar(node_names, exec_time)\n",
    "    plt.yticks(y_axis)\n",
    "    plt.xlabel('Computer numbers')\n",
    "    plt.ylabel('Execution time')\n",
    "    fig.savefig('integer_jobs.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3つのコンピュータの実行時間がほぼ均等な解が得られました。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "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.5"
  },
  "vscode": {
   "interpreter": {
    "hash": "5de874e2fc479b2d8c72d9b9d7199763e296392b542125e77f5cad711bb306ce"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}