{
 "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": [
    "# 部分和問題\n",
    "\n",
    "このページでは、Amplify SDK を用いた定式化と求解の簡単な例として、部分和問題を扱います。\n",
    "\n",
    "部分和問題とは、以下のような問題です。\n",
    "\n",
    "```{card}\n",
    "$N$, $K$ を正の整数とします。$N$ 個の正の整数からなる数列 $A_0, A_1, \\ldots, A_{N - 1}$ があります。 この数列の部分列であって、要素の総和が $K$ に最も近くなるものを求めてください。\n",
    "```\n",
    "\n",
    "あるいは、以下のような言い換えが考えられます。\n",
    "\n",
    "```{card}\n",
    "$N$ 本の動画があり、その長さはさまざまです。これらの中からいくつかを選んで、合計時間が $K$ 分に最も近くなるようにするには、どの動画を選ぶべきでしょうか?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 問題の作成\n",
    "\n",
    "Amplify SDK を用いて部分和問題を解く前に、まずは部分和問題を作成し、プログラムコード上で表現します。今回は例題として、要素数 $N=10$ の簡単な問題を扱います。"
   ]
  },
  {
   "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": [
    "## Amplify SDK による定式化\n",
    "\n",
    "Amplify SDK による定式化を行うためには、部分和問題を多項式の最小化問題に言い換える必要があります。\n",
    "\n",
    "まず、「部分列の要素の和が $K$ に最も近いもの」は、「部分列の要素の和と $K$ の差を 2 乗した値が最小となるもの」に言い換えられます。また、「部分列の要素の和」は、数列の $i$ 番目の要素が選ばれるなら $1$, そうでないなら $0$ をとる変数 $q_i$ を用いて、$q_0 A_0 + q_1 A_1 + \\cdots + q_{N-1} A_{N-1}$ と書くことができます。\n",
    "\n",
    "したがって、部分和問題は以下のように定式化されます。\n",
    "\n",
    "```{card}\n",
    "変数 $q_0, q_1, \\ldots, q_{N-1}$ が $0$ または $1$ の値をとるとき、\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",
    "\n",
    "上記の $\\quad (q_0 A_0 + q_1 A_1 + \\cdots + q_{N-1} A_{N-1} - K)^2$ のことを目的関数とよびます。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以上を Amplify SDK 上で表現していきましょう。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "決定変数 (組合せ最適化において最適化対象の変数) を作成します。まず、変数を発行するためのクラス {py:class}`~amplify.VariableGenerator` をインスタンス化します。必要な変数は、 $0$ または $1$ の値をとる変数が $N$ 個です。$0$ または $1$ の値をとる変数はバイナリ変数といい、Amplify SDK では簡単に作成できます。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from amplify import VariableGenerator\n",
    "\n",
    "gen = VariableGenerator()\n",
    "q = gen.array(\"Binary\", N)  # 第一引数に変数の種類を、第二引数に変数の数を与える\n",
    "\n",
    "q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "目的関数 $\\quad (q_0 A_0 + q_1 A_1 + \\cdots + q_{N-1} A_{N-1} - K)^2$ を作成します。NumPy-like な記法を用いて、以下のように書くことができます。"
   ]
  },
  {
   "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",
    "もちろん、古典的な Python 風に\n",
    "\n",
    "```\n",
    "objective = sum(x * a for x, a in zip(q, A))\n",
    "```\n",
    "\n",
    "などと書くこともできます。ただし、このような書き方は問題やデータサイズによっては時間がかかる場合があるため、`objective = (q * A) ** 2`{l=python} のような NumPy-like な書き方を推奨しています。詳しくは [](optimization.md) を参照してください。\n",
    "````"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "作成した目的関数を使って、組合せ最適化モデルを構築します。"
   ]
  },
  {
   "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": [
    "これで組合せ最適化モデルの構築が完了しました。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ソルバーの設定\n",
    "\n",
    "Amplify SDK を用いて、さまざまな組合せ最適化ソルバーに求解を行わせることができます。このページでは、例として、クラウドサービスとして提供されている Fixstars Amplify AE を使用します。\n",
    "\n",
    "まず、どのソルバーを使用するかを指定するために、Amplify AE に対応する Amplify SDK のソルバークライアント {py:class}`~amplify.FixstarsClient` を作成します。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from amplify import FixstarsClient\n",
    "\n",
    "client = FixstarsClient()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ソルバーで求解を行うために必要なトークンと、ソルバーのパラメータを設定します。"
   ]
  },
  {
   "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": [
    "これでソルバーの設定は完了です。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Amplify SDK による求解\n",
    "\n",
    "上記で作成した組合せ最適化モデルとソルバークライアントを使用して、求解を実行します。以下のコードを実行することで、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": [
    "変数 $q = (q_0, q_1, \\ldots, q_{N-1})$ の値は、以下のように得ることができます。"
   ]
  },
  {
   "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": [
    "バイナリ変数 $q_i$ は、数列 $A$ の $i$ 番目の要素が選ばれるなら $1$、そうでないときは $0$ をとるので、部分和問題の最適解は以下のように表示できます。"
   ]
  },
  {
   "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": [
    "和が $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
}