# 組合せ最適化問題の求解

このページでは、「[モデルの定式化](model.md)」と「[クライアントの作成](clients.md)」で作成したモデル {py:class}`~amplify.Model` およびソルバークライアントを使用して、組合せ最適化問題の求解を行う方法を解説します。

## Solve 関数

組合せ最適化を実行するために、{py:func}`~amplify.solve` 関数が用意されています。この関数は第一引数に {py:class}`~amplify.Model` を、第二引数にソルバークライアントオブジェクトを受け取り、
ソルバークライアントに対応するソルバーを用いてモデルの最適化を行います。

次の例を Amplify AE を用いて最適化します。

```{math}
\begin{align*}
    \text{minimize: } \quad & f = q_0 q_1 - q_2 \\
    \text{subject to: } \quad &  q_0 + q_1 + q_2 = 1, \\
    & q_0, q_1, q_2 \in \{0, 1\}
\end{align*}
```

目的関数と制約条件を構築して、モデルを作成します。

```{testcode}
from amplify import VariableGenerator, one_hot, FixstarsClient, solve

gen = VariableGenerator()
q = gen.array("Binary", 3)

objective = q[0] * q[1] - q[2]
constraint = one_hot(q)

model = objective + constraint
```

Amplify AE のソルバークライアントを作成して、タイムアウト時間を 1000 ミリ秒に設定します。

```{testcode}
from datetime import timedelta

client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = timedelta(milliseconds=1000)
```

次のようにしてモデルとソルバークライアントを {py:func}`~amplify.solve` 関数に与え求解を実行します。

```{testcode}
result = solve(model, client)
```

得られた結果は、以下のようにして確かめることができます。詳細は[結果の取得](solver-result)を参照してください。

```{doctest}
>>> print(f"objective = {result.best.objective}")
objective = -1.0
>>> print(f"q = {q.evaluate(result.best.values)}")
q = [0. 0. 1.]
```

```{seealso}
Amplify SDK は、入力されたモデルをクライアントが受け取れる形にするために、ペナルティ関数の計算、変数変換や次数下げ、グラフ埋め込みといったモデル変換を必要に応じて自動で行います。{py:func}`~amplify.solve` 関数には、このモデル変換で使用するいくつかのパラメータを指定することができます。各パラメータの詳細については「[](#conversion-parameters)」下の各ページを参照してください。
```

### モデル構築の省略

モデルが目的関数のみ、または制約条件のみから構成される場合、{py:func}`~amplify.solve` 関数の第 1 引数に直接 {py:class}`~amplify.Poly` クラスのオブジェクトや {py:class}`~amplify.Constraint` または {py:class}`~amplify.ConstraintList` クラスのオブジェクトを渡すことが可能です。

```{testcode}
from amplify import VariableGenerator, one_hot, FixstarsClient, solve
from datetime import timedelta

gen = VariableGenerator()
q = gen.array("Binary", 3)
objective = q[0] * q[1] - q[2]
constraint1 = one_hot(q[0] + q[1])
constraint2 = one_hot(q[1] + q[2])

client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = timedelta(milliseconds=1000)
```

制約条件のない組合せ最適化問題を解く:

```{testcode}
result = solve(objective, client)
```

単一の制約条件からなる組合せ最適化問題を解く:

```{testcode}
result = solve(constraint1, client)
```

制約条件のみからなる組合せ最適化問題を解く:

```{testcode}
result = solve(constraint1 + constraint2, client)
```

(solver-result)=

## 結果の取得

{py:func}`~amplify.solve` 関数が返す {py:class}`~amplify.Result` オブジェクトには、ソルバーが返した解の情報や実行にかかった時間の情報が含まれています。

```{testcode}
from amplify import VariableGenerator, one_hot, FixstarsClient, solve
from datetime import timedelta

gen = VariableGenerator()
q = gen.array("Binary", 3)
objective = q[0] * q[1] - q[2]
constraint = one_hot(q)
model = objective + constraint

client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = timedelta(milliseconds=1000)

result = solve(model, client)
```

{py:class}`~amplify.Result` に含まれる解の個数は {py:func}`len` 関数により取得できます。デフォルトでは、制約条件をすべてみたす解のみが{py:class}`~amplify.Result` に含まれています。

```{doctest}
>>> len(result)
1
```

{py:class}`~amplify.Result` に 1 個以上の解が含まれている場合、{py:class}`~amplify.Result.best` プロパティにより最良解を取得できます。

```{doctest}
>>> type(result.best)
<class 'amplify.Result.Solution'>
```

{py:class}`~amplify.Result.best` プロパティにより取得できる最良解は {py:class}`~amplify.Result.Solution` クラスのインスタンスです。このクラスは以下のアトリビュートを持ちます。

```{list-table}
- * {py:attr}`~amplify.Result.Solution.objective`
  * 目的関数の値
- * {py:attr}`~amplify.Result.Solution.values`
  * 解における各変数の値
- * {py:attr}`~amplify.Result.Solution.feasible`
  * 制約条件がみたされているかどうか
- * {py:attr}`~amplify.Result.Solution.time`
  * 解が得られた時刻
```

以下のようにして、最良解における目的関数の値、変数の値、制約条件がすべてみたされているかどうか、解が得られた時刻をそれぞれ取得できます。

```{doctest}
>>> result.best.objective
-1.0
>>> result.best.values
Values({Poly(q_0): 0, Poly(q_1): 0, Poly(q_2): 1})
>>> result.best.feasible
True
>>> result.best.time # doctest: +SKIP
datetime.timedelta(microseconds=27965)
```

変数配列の {py:meth}`~amplify.PolyArray.evaluate` メソッドに {py:attr}`~amplify.Result.Solution.values` を渡すことで、変数配列の各変数に対応する解の値を変数配列と同じ形の {py:class}`~numpy.ndarray` として得ることができます。

```{doctest}
>>> print(q.evaluate(result.best.values))
[0. 0. 1.]
```

```{attention}
使用したソルバーによっては、解が得られた時刻を取得できない場合があります。その場合、{py:attr}`~amplify.Result.Solution.time` アトリビュートにはソルバーの実行時間 {py:attr}`~amplify.Result.execution_time` と同じ値が入ります。詳しくは [](timing.md) を参照してください。
```

{py:class}`~amplify.Result` には最良解だけでなく複数の解が含まれている場合があります。それぞれの解は、{py:class}`~amplify.Result` に対するインデックスアクセスにより {py:class}`~amplify.Result.Solution` クラスのインスタンスを取得できます。

```{doctest}
>>> result[0].objective
-1.0
>>> result[0].feasible
True
```

イテレートによるアクセスも可能です。

```{doctest}
>>> for r in result:
...     print(r.objective)
...     print(r.values)
...     print(r.feasible)
...     print(r.time) # doctest: +SKIP
-1.0
amplify.Values({Poly(q_0): 0.0, Poly(q_1): 0.0, Poly(q_2): 1.0})
True
0:00:00.028060
```

```{seealso}
{py:class}`~amplify.Result` オブジェクトには、ほかにモデル変換やグラフ埋め込み、実行時間の情報も含まれています。{py:class}`~amplify.Result` の各プロパティに関する詳細は [](evaluation.md) を参照してください。
```

## 実行結果の出力オプション

デフォルトでは、{py:func}`~amplify.solve` 関数が返す {py:class}`~amplify.Result` オブジェクトには、制約条件をみたす解のみが目的関数の値が小さい順に入っています。{py:func}`~amplify.solve` 関数に `filter_solution` キーワード引数および `sort_solution` キーワード引数を指定することで、この動作を変更することができます。

(filter-solution)=

### 解のフィルター

{py:func}`~amplify.solve` 関数の `filter_solution` キーワード引数に {py:obj}`False` を指定すると、制約条件をみたさない解も {py:class}`~amplify.Result` に含めることができます。

```{testcode}
from amplify import VariableGenerator, equal_to, Model, FixstarsClient, solve
from datetime import timedelta

gen = VariableGenerator()
q = gen.array("Binary", 3)
constraint1 = equal_to(q, 1)
constraint2 = equal_to(q, 2)
model = Model(constraint1 + constraint2)

client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"
client.parameters.timeout = timedelta(milliseconds=1000)
```

```{doctest}
>>> result1 = solve(model, client)
>>> len(result1)
0
>>> result2 = solve(model, client, filter_solution=False)
>>> len(result2)
1
>>> result2.best.feasible
False
```

{py:func}`~amplify.solve` 関数を呼んだあとでも、{py:class}`~amplify.Result` の {py:attr}`~amplify.Result.filter_solution` プロパティを {py:obj}`False` に指定することで、制約条件をみたさない解が {py:class}`~amplify.Result` に含まれるようにできます。

```{doctest}
>>> result = solve(model, client)
>>> len(result)
0
>>> result.filter_solution = False
>>> len(result)
1
```

### 解のソート

デフォルトでは、{py:class}`~amplify.Result` に含まれる解は良い順にソートされています。 {py:func}`~amplify.solve` 関数の `sort_solution` キーワード引数に {py:obj}`False` を指定すると、{py:class}`~amplify.Result` に入る解の順番はソルバーが返した解の順番のままになります。 

```{testcode}
result = solve(model, client, sort_solution=False)
```

{py:class}`~amplify.Result` の {py:meth}`~amplify.Result.sort` メソッドにより、あとから解をソートすることも可能です。

```{testcode}
result.sort()
```

```{note}
Amplify SDK では、解の良さを以下の順に判定します。
1. 制約条件をみたしているかどうか
2. 目的関数の値が小さいかどうか

したがって、{py:class}`~amplify.Result` の {py:attr}`~amplify.Result.best` プロパティにより取得できる解は、制約条件をみたしている解があればその中で最も目的関数の値が小さいものとなります。制約条件をみたしている解がない場合は、{py:attr}`~amplify.Result.filter_solution` が {py:obj}`False` ならば最も目的関数の値が小さいものが返ります。
```

## dry-run オプション

{py:func}`~amplify.solve` 関数の `dry_run` キーワード引数に {py:obj}`True` を指定することで、ソルバーにモデルを送る直前までの処理が行われます。多くのソルバークライアントでは、API トークンを指定しなくても `dry_run` を指定した {py:func}`~amplify.solve` 関数の実行が可能です。

このオプションにより、求解したいモデルがソルバーに入力可能なのか、また、その際にどのようなモデル変換やグラフ埋め込みが行われ、どのようなリクエストデータが送られるのかを、ソルバーに接続する前に確認することができます。

```{testcode}
from amplify import VariableGenerator, equal_to, Model, FixstarsClient, solve
from datetime import timedelta

gen = VariableGenerator()
q = gen.array("Binary", 3)
constraint1 = equal_to(q, 1)
constraint2 = equal_to(q, 2)
model = Model(constraint1 + constraint2)

client = FixstarsClient()

result = solve(model, client, dry_run = True)
```

`dry_run` オプションを指定して実行した場合、{py:func}`~amplify.solve` 関数が返す {py:class}`~amplify.Result` オブジェクトには解は入っていません。

```{doctest}
>>> len(result)
0
```

```{note}
`dry_run` オプションを指定して実行した場合、{py:class}`~amplify.Result` の {py:attr}`~amplify.Result.intermediate` プロパティおよび {py:attr}`~amplify.Result.embedding` プロパティは `dry_run` オプションを指定せずに実行した場合と同じ結果になります。これは、モデル変換とグラフ埋め込みがどのように行われるかを知りたい場合に便利です。各プロパティの詳細については[](conversion.md)をご覧ください。
```

```{note}
`dry_run` オプションを指定して実行した場合、実際のリクエストはソルバーには送られませんが、ソルバークライアントの {py:attr}`~amplify.FixstarsClient.write_request_data` が設定されていればリクエストデータのファイル書き込みが行われます。{py:attr}`~amplify.FixstarsClient.write_request_data` の詳細については [](#client-write-data)をご覧ください。
```