{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "remove-cell"
    ]
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "sys.path.insert(1, \"../../\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Subset Sum Problem\n",
    "\n",
    "This page discuss the subset sum problem as a simple example of formulation and solving with the Amplify SDK.\n",
    "\n",
    "A subset sum problem is the following problem.\n",
    "\n",
    "```{card}\n",
    "Let $N$ and $K$ be positive integers. There is a sequence $A_0, A_1, \\ldots, A_{N - 1}$ consisting of $N$ positive integers. Find a subsequence of this sequence whose sum of elements is closest to $K$.\n",
    "```\n",
    "\n",
    "Alternatively, the following problem is a subset sum problem.\n",
    "\n",
    "```{card}\n",
    "There are $N$ videos of varying lengths. Which of these videos should you select to make the total time closest to $K$ minutes?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating the Problem\n",
    "\n",
    "Before solving a subset sum problem with the Amplify SDK, we first create a subset sum problem and express it in program code. In this example, we will work with a simple problem with $N=10$ elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "N = 10\n",
    "K = 27\n",
    "A = np.array([2, 10, 3, 8, 5, 7, 9, 5, 3, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Formulation with the Amplify SDK\n",
    "\n",
    "To perform the formulation with Amplify SDK, we need to reformulate the subset sum problem as a polynomial minimization problem.\n",
    "\n",
    "First, \"the sum of the elements of the subsequence closest to $K$\" can be reformulated as \"the difference between the sum of the elements of the subsequence and $K$ squared is the least\". Also, \"the sum of the elements of the subsequence\" can be written as $q_0 A_0 + q_1 A_1 + \\cdots + q_{N-1} A_{N-1}$, where the variable $q_i$ takes $1$ if the $i$-th element of the sequence is chosen, $0$ otherwise.\n",
    "\n",
    "Thus, we can formulate the subset sum problem as follows.\n",
    "\n",
    "```{card}\n",
    "If the variables $q_0, q_1, \\cdots, q_{N-1}$ take the values $0$ or $1$, minimize the function value below.\n",
    "\n",
    "$$\n",
    "\\quad (q_0 A_0 + q_1 A_1 + \\cdots + q_{N-1} A_{N-1} - K)^2\n",
    "$$\n",
    "\n",
    "```\n",
    "\n",
    "The above $\\quad (q_0 A_0 + q_1 A_1 + \\cdots + q_{N-1} A_{N-1} - K)^2$ is called the objective function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's express the above in the Amplify SDK. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, create the decision variables (the variables we will optimize in combinatorial optimization). First, instantiate a class {py:class}`~amplify.VariableGenerator` to issue variables. $N$ variables are required, all of which take $0$ or $1$ values. Variables that take $0$ or $1$ values are called binary variables, and we can create them easily using the Amplify SDK."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from amplify import VariableGenerator\n",
    "\n",
    "gen = VariableGenerator()\n",
    "\n",
    "# The variable type as the 1st and the number of variables as the 2nd arguments.\n",
    "q = gen.array(\"Binary\", N)\n",
    "\n",
    "q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we create the objective function $(q_0 A_0 + q_1 A_1 + \\cdots + q_{N-1} A_{N-1} - K)^2$. Using NumPy-like notation, we can implement as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "objective = ((q * A).sum() - K) ** 2\n",
    "\n",
    "print(objective)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "````{note}\n",
    "Of course, in classic Python style, you can implement it as follows.\n",
    "\n",
    "```\n",
    "objective = sum(x * a for x, a in zip(q, A)).\n",
    "```\n",
    "\n",
    "However, depending on the problem and the data size, such writing can be time-consuming. We recommend a NumPy-like writing like `objective = (q * A) ** 2`{l=python}. See [](optimization.md) for details.\n",
    "````"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we use the objective function to construct a combinatorial optimization model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from amplify import Model\n",
    "\n",
    "model = Model(objective)\n",
    "\n",
    "print(model)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have completed the model construction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solver setup\n",
    "\n",
    "You can configure various combinatorial optimization solvers with the Amplify SDK. On this page, we will use Fixstars Amplify AE, which is provided as a cloud service.\n",
    "\n",
    "First, create a solver client {py:class}`~amplify.FixstarsClient` for the Amplify SDK corresponding to Amplify AE to specify which solver to use."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from amplify import FixstarsClient\n",
    "\n",
    "client = FixstarsClient()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we set up the token and solver's parameters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "skip-execution"
    ]
   },
   "outputs": [],
   "source": [
    "from datetime import timedelta\n",
    "\n",
    "client.token = \"xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\"\n",
    "client.parameters.timeout = timedelta(milliseconds=1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": [
     "remove-cell"
    ]
   },
   "outputs": [],
   "source": [
    "from datetime import timedelta\n",
    "\n",
    "client.token = \"\"\n",
    "client.parameters.timeout = timedelta(milliseconds=1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This completes the solver setup."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solver execution with the Amplify SDK\n",
    "\n",
    "Let the Amplify SDK obtain the solution of the combinatorial optimization model created above by executing the solver corresponding to the solver client. The following code executes the Amplify AE."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from amplify import solve\n",
    "\n",
    "result = solve(model, client)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The value of the variables $q = (q_0, q_1, \\ldots, q_{N-1})$ can be obtained as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q_values = q.evaluate(result.best.values)\n",
    "\n",
    "print(q_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The binary variables $q_i$ take $1$ if the $i$-th element of the number sequence $A$ is chosen and $0$ otherwise. The optimal solution to the subset sum problem is as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"selected numbers: {[a for x, a in zip(q_values, A) if x == 1]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can see that the sum is close to $K=27$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\n",
    "    f\"{K=}, sum of selected numbers = {sum(a for x, a in zip(q_values, A) if x == 1)}\"\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "amplify-lrEeNlW4",
   "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}