OpenJij/OpenJij

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Knapsack Problem\n",
    "Here we show how to solve the knapsack problem using OpenJij, [JijModeling](https://www.ref.documentation.jijzept.com/jijmodeling/), and [JijModeling Transpiler](https://www.ref.documentation.jijzept.com/jijmodeling-transpiler/). This problem is also mentioned in 5.2. Knapsack with Integer Weights in [Lucas, 2014, \"Ising formulations of many NP problems\"](https://doi.org/10.3389/fphy.2014.00005).\n",
    "\n",
    "## Overview of the Knapsack Problem\n",
    "\n",
    "The knapsack problem is the problem of finding the optimal solution in the following situations.\n",
    "It is known as one of the most famous NP-hard integer programming problems. First, let us consider an example.\n",
    "\n",
    "### Example\n",
    "\n",
    "As an example of this problem, consider the following story.\n",
    "\n",
    "> In a cave, an explorer unexpectedly discovered several treasures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "||Treasure A|Treasure B|Treasure C|Treasure D|Treasure E|Treasure F|\n",
    "|---|---|---|---|---|---|---|\n",
    "|Price|\\$5000|\\$7000|\\$2000|\\$1000|\\$4000|\\$3000|\n",
    "|Weight|800g|1000g|600g|400g|500g|300g|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Unfortunately, the explorer only has a small knapsack.\n",
    "> This knapsack can only hold up to 2 kg. The explorer wants to get as much value as possible for the treasure in this knapsack, so which treasures should he bring back?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Generalizing the Problem\n",
    "\n",
    "To generalize this problem, assume that there is a set $\\{ 0, 1, \\dots, i, \\dots, N-1\\}$ of $N$ items to put in the knapsack and that each item has $i$ as its index.  \n",
    "We can represent the problem by making a list of costs $\\boldsymbol{v}$ and a list of weights $\\boldsymbol{w}$ for each luggage $i$ to be put in the knapsack.\n",
    "\n",
    "$$\n",
    "\\nonumber\n",
    "\\boldsymbol{v} = \\{v_0, v_1, \\dots, v_i, \\dots, v_{N-1}\\}\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\nonumber\n",
    "\\boldsymbol{w} = \\{w_0, w_1, \\dots, w_i, \\dots, w_{N-1}\\}\n",
    "$$\n",
    "\n",
    "Let $x_i$ further denote the binary variable that represents the $i$th package selected.\n",
    "It is $x_i = 1$ when $i$ is placed in the knapsack and $x_i = 0$ when $i$ is not.\n",
    "Finally, let $W$ be the maximum capacity of the knapsack.  \n",
    "We want to maximize the total value of luggage we can put in the knapsack, and we express this as an objective function.\n",
    "Given the further constraint that the knapsack must be below the capacity limit, the knapsack problem can be expressed as the following expression:\n",
    "\n",
    "$$\n",
    "\\max \\ \\sum_{i=0}^{N-1} v_i x_i\n",
    "$$(1)\n",
    "\n",
    "$$\n",
    "\\mathrm{s.t.} \\quad \\sum_{i=0}^{N-1} w_i x_i \\leq W\n",
    "$$(2)\n",
    "\n",
    "$$\n",
    "x_i \\in \\{0, 1\\} \\quad (\\forall i \\in \\{0, 1, \\dots, N-1\\})\n",
    "$$(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Modeling by JijModeling\n",
    "\n",
    "### Variables\n",
    "\n",
    "Let us define the variables $\\boldsymbol{v}, \\boldsymbol{w}, N, W, x_i, i$ used in expressions (1), (2) and (3) as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import jijmodeling as jm\n",
    "\n",
    "\n",
    "# define variables\n",
    "v = jm.Placeholder('v', dim=1)\n",
    "N = v.shape[0].set_latex('N')\n",
    "w = jm.Placeholder('w', shape=(N,))\n",
    "W = jm.Placeholder('W')\n",
    "x = jm.Binary('x', shape=(N,))\n",
    "i = jm.Element('i', (0, N))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "`v = jm.Placeholder('v', dim=1)` declares a one-dimensional list of values of things to put in the knapsack, and the number of elements is `N`.\n",
    "`N` has `set_latex()` expression so that the representation changes ([link](https://www.ref.documentation.jijzept.com/jijmodeling/reference/jijmodeling/#jijmodeling.expression.expression.Expression.set_latex)).\n",
    "Using that `N`, we can guarantee that `v` and `w` have the same length by defining a one-dimensional list representing the weight of the items to put in the knapsack as `w = jm.Placeholder('w', shape=(N))`.\n",
    "`W = jm.Placeholder('W')` defines $W$ to represent the knapsack capacity limit.\n",
    "`x = jm.Binary('x', shape=(N))` defines a binary variable list `x` of the same length as `v, w`.\n",
    "Finally, `i = jm.Element('i', (0, N))` defines the indices of $v_i, w_i, x_i$, which are integers in the range $0\\leq i < N$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Objective Function\n",
    "\n",
    "Expression (1) is implemented as an objective function.\n",
    "Note that we added a negative sign to make this a minimization problem.\n",
    "Let us create a problem and add an objective function to it.\n",
    "By `Sum(i, formula)`, we can sum the expression part to the subscript `i`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# set problem\n",
    "problem = jm.Problem('Knapsack')    \n",
    "# set objective function\n",
    "obj = - jm.Sum(i, v[i]*x[i])\n",
    "problem += obj"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Constraint\n",
    "\n",
    "Let us implement the constraint in expression (2) by using `Constraint(constraint name, constraint expression)`.\n",
    "This gives the appropriate constraint name to the constraint expression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$\\begin{alignat*}{4}\\text{Problem} & \\text{: Knapsack} \\\\\\min & \\quad - \\sum_{ i = 0 }^{ N - 1 } v_{i} \\cdot x_{i} \\\\\\text{s.t.} & \\\\& \\text{weight} :\\\\ &\\quad \\quad \\sum_{ i = 0 }^{ N - 1 } w_{i} \\cdot x_{i} \\leq W,\\\\[8pt]& x_{i_{0}} \\in \\{0, 1\\}\\end{alignat*}$$"
      ],
      "text/plain": [
       "<jijmodeling.problem.problem.Problem at 0x1119652e0>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# set total weight constraint\n",
    "total_weight = jm.Sum(i, w[i]*x[i])\n",
    "problem += jm.Constraint('weight', total_weight<=W)\n",
    "problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Instance\n",
    "\n",
    "Let us set up an instance of the explorer story from earlier.\n",
    "The value of the treasure is normalized to \\$1000, and the weight of the treasure is also normalized to 100g."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# set a list of values & weights \n",
    "inst_v = [5, 7, 2, 1, 4, 3]\n",
    "inst_w = [8, 10, 6, 4, 5, 3]\n",
    "# set maximum weight\n",
    "inst_W = 20\n",
    "instance_data = {'v': inst_v, 'w': inst_w, 'W': inst_W}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Undetermined Multiplier\n",
    "\n",
    "This knapsack problem has one constraint, and we need to set the weight of that constraint.\n",
    "We will set it to match the name we gave in the `Constraint` part earlier using a dictionary type."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# set multipliers\n",
    "lam1 = 1.0\n",
    "multipliers = {'weight': lam1}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conversion to PyQUBO by JijModeling Transpiler\n",
    "\n",
    "JijModeling has executed all the implementations so far.\n",
    "By converting this to [PyQUBO](https://pyqubo.readthedocs.io/en/latest/), it is possible to perform combinatorial optimization calculations using OpenJij and other solvers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from jijmodeling.transpiler.pyqubo import to_pyqubo\n",
    "\n",
    "# convert to pyqubo\n",
    "pyq_model, pyq_chache = to_pyqubo(problem, instance_data, {})\n",
    "qubo, bias = pyq_model.compile().to_qubo(feed_dict=multipliers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "The PyQUBO model is created by `to_pyqubo` with the `problem` created by JijModeling and the `instance_data` we set to a value as arguments.\n",
    "Next, we compile it into a QUBO model that can be computed by OpenJij or other solver.\n",
    "\n",
    "### Optimization by OpenJij\n",
    "\n",
    "This time, we will use OpenJij's simulated annealing to solve the optimization problem.\n",
    "We set the `SASampler` and input the QUBO into that sampler to get the result of the calculation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "import openjij as oj\n",
    "# set sampler\n",
    "sampler = oj.SASampler(num_reads=100)\n",
    "# solve problem\n",
    "response = sampler.sample_qubo(qubo)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Decoding and Displaying the Solution\n",
    "\n",
    "Decode the returned results to facilitate analysis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# decode solution\n",
    "result = pyq_chache.decode(response)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "From the result thus obtained, let us see which treasures we decide to put in the knapsack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Indices of x = 1:  [1, 4, 5]\n",
      "Value of objective function:  [-14.0]\n",
      "Value of constraint term:  [0.0]\n",
      "Total weight:  18\n"
     ]
    }
   ],
   "source": [
    "indices, _, _ = result.lowest().record.solution['x'][0]\n",
    "inst_w = instance_data['w']\n",
    "sum_w = 0\n",
    "for i in indices[0]:\n",
    "    sum_w += inst_w[i]\n",
    "print('Indices of x = 1: ', indices[0])\n",
    "print('Value of objective function: ', result.lowest()[0].evaluation.objective)\n",
    "print('Value of constraint term: ', result.lowest()[0].evaluation.constraint_violations['weight'])\n",
    "print('Total weight: ', sum_w)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The value of the objective function multiplied by the minus sign is the total value of the treasure in the knapsack.\n",
    "`result.evaluation.constraint_violations[constraint name]` shows how many of its constraints are not satisfied."
   ]
  }
 ],
 "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.15"
  },
  "vscode": {
   "interpreter": {
    "hash": "2e8d7574d7ec71e14cb1575cf43673432d6fae464c836a7b3733d4f6c20243fb"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}