モデルの定式化

モデルの定式化#

モデルとは何か? なぜ直接ソルバーを使わないのか?#

Why not use solvers directly?

jijmodelingは、人間が読みやすい数理モデルをコンピュータが読み取れるデータ形式に変換する「モデラー」ライブラリです。最適化問題にはいくつかの種類があり、それに対応する問題固有のソルバーはソルバー固有のデータ形式しか受け付けません。そのため、数理モデルをソルバー固有のデータ形式に変換する必要があります。jijmodelingを使用すると数理モデルを単一の数学的な方法で記述することができ、その後、ソルバーやインスタンス固有の詳細に適合させることもできます。

数理モデルの例#

ここでは\(N\)個の実数係数\(d_n\)を持つ単純なバイナリ線形最小化問題を考えます。

\[\begin{split} \min \sum_{n=0}^{N−1}d_n x_n, \\ \text{s.t.} \space \sum_{n=0}^{N-1} x_n = 1, \\ \text{where} \space x_n \in \{0,1\} \space \forall n \in [0, N-1] \end{split}\]

この問題はjijmodelingの基本的な使用方法を学べる良い例です。具体的には、

  • 決定変数\(x_n\)とプレースホルダー\(N\)および\(d_n\)を定義する

  • \(\sum_{n=0}^{N-1} d_n x_n\)の最小化を目的関数として設定する

  • 等式制約\(\sum_{n=0}^{N-1} x_n = 1\)を設定する

という内容を学ぶことができます。より実践的で包括的な例は、JijZeptのドキュメントサイトのLearnを確認してください。

Problemオブジェクトを作る#

実際にjijmodelingを使っていきましょう。まずはインポートする必要があります。

import jijmodeling as jm
jm.__version__   # 1.8.0

'1.10.0'

Caution

以下のコードを実行する前に、あなたの環境のjijmodelingのバージョンがこのドキュメントと一致していることを確認することを強く推奨します。

では、jijmodelingを用いて数理モデルを構築してみましょう。

# 「パラメータ」を定義
d = jm.Placeholder("d", ndim=1)
N = d.len_at(0, latex="N")

# 「決定変数」を定義
x = jm.BinaryVar("x", shape=(N,))

# 総和をするためのインデックスを準備
n = jm.Element('n', belong_to=(0, N))

# 数理モデルを管理するオブジェクトを生成
problem = jm.Problem('my_first_problem')
# 目的関数を設定
problem += jm.sum(n, d[n] * x[n])
# 制約条件を設定
problem += jm.Constraint("onehot", jm.sum(n, x[n]) == 1)

# 数理モデルを表示
problem
\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{my\_first\_problem} & & \\& & \min \quad \displaystyle \sum_{n = 0}^{N - 1} d_{n} \cdot x_{n} & \\\text{{s.t.}} & & & \\ & \text{onehot} & \displaystyle \sum_{n = 0}^{N - 1} x_{n} = 1 & \\\text{{where}} & & & \\& x & 1\text{-dim binary variable}\\\end{array}\end{split}\]

コードのどの部分が上記の数理モデルに対応するか分かりましたか？　このページではコードの各部分の内容と操作についてもう少し深く説明していきます。

Jupyter環境

Jupyter Notebook等の環境では、以下の画像のようにProblemオブジェクトの内容を表示できます。これにより、モデルを対話的にデバッグすることができます。

Jupyter example

決定変数とパラメータ#

上記の数理モデルには「決定変数」と「パラメータ」という2種類の「変数」があります。jijmodelingでは、「変数」を宣言する際に使用するクラスによってこれを識別します。

Decision variables and Parameters

  • \(x_n\)の値は問題を解くことで決まるもののため、これを「決定変数」と呼びます。

    • 今回の問題では、バイナリ変数\(x_n \in \{0, 1\}\)をBinaryVarで宣言しています。決定変数を定義できるクラスとして他にもIntegerVarやContinuousVarがあります。

    • さらに詳しい説明は決定変数の種類を参照してください。

  • \(N\)と\(d\)の値はユーザーによって指定される「パラメータ」です。

    • この問題は\(N\)と\(d\)によってパラメータ化されていると言います。

    • 「パラメータ」の実際の値はProblemオブジェクト内では指定しません。

    • 「パラメータ」は問題の「インスタンスデータ」の入れ物と見なすことができます。特定のインスタンスは異なる値を持ちますが、jijmodelingは特定の値に依存しない方法で数理モデルを記述することができます。

    • ほとんどの「パラメータ」は、上記のコードのdのように明示的に定義されたPlaceholderオブジェクトで表されます。

    • \(N\)は\(d\)の要素数として定義されており、\(N\)は「暗黙的なパラメータ」として扱われます。これにより、数理モデル内の\(N\)の意味がコード上で明確になり、インスタンスを生成するためには\(d\)を指定するだけで良くなります。

オブジェクトとは何か？

Pythonではすべての値には型があります。例えば、1はint型であり、1.0はfloat型です。組み込み関数typeを使用して、type(1.0)のように型を取得できます。ある型Aに対して、型Aの値を「Aオブジェクト」と呼びます。

多次元変数#

配列や行列のようなインデックスを使用できる変数を定義することができます。 上記の数理モデルでは、\(N\)個の係数\(d_n\)と\(N\)個の決定変数\(x_n\)を定義したいので、1次元のPlaceholderオブジェクトdと1次元のBinaryVarオブジェクトxを定義しましょう。Placeholderの場合は値がいくつかあるかを指定せずに、ただ1次元であることを指定すれば十分です。一方、決定変数の場合は次元数とともにその長さを指定しなければなりません。ですが、jijmodelingではその長さも「パラメータ」として定義することができるので、数値を使わずに以下のように書くことができます。

# 係数dの定義
d = jm.Placeholder("d", ndim=1)
# $d$の長さとして$N$を定義
N = d.len_at(0, latex="N")
# $N$を用いて決定変数$x$を定義
x = jm.BinaryVar("x", shape=(N,))

NはArrayLength型であり、Placeholderオブジェクトdの要素数を表しています。len_atの第1引数に与えられた0は0次元方向の要素数をカウントすることを意味しており、これはPlaceholderが任意の次元数を持つことができるために指定が必要になっています。

Note

インデックスと総和については、次のページでさらに詳しく説明します。

目的関数#

次に、最小化する目的関数として\(\sum_{n=0}^{N-1} d_n x_n\)をProblemオブジェクトに設定しましょう。しかし、\(N\)はProblemオブジェクトの構築段階では固定されていないため、Pythonのforループを書くことはできません。では、どのように総和を行えば良いでしょうか？

この疑問を解決するためにjijmodeling専用のsumが存在します。

n = jm.Element('n', belong_to=(0, N))
sum_dx = jm.sum(n, d[n] * x[n])

Elementは、ある範囲内のインデックスに対応する新しいタイプの変数です。以下のようなケースを考えてみましょう。

与えられた\(n \in [0, N-1]\)に対し、\(d \in \mathbb{R}^N\)の\(n\)番目の要素\(d_n\)を取る

jijmodelingでは、\(n \in [0, N-1]\)に対応するElementオブジェクトnと\(d\)に対応するPlaceholderオブジェクトdを用いて、\(d_n\)をd[n]で表現します。Elementオブジェクトに有効な範囲が指定されていることに注意してください。 そして、総和\(\sum_{n} d_n x_n\)を表現するためにjijmodeling専用のsumを利用します。第1引数として和を取る範囲を表すElementオブジェクトnを指定し、第2引数として和を取る式d[n] * x[n]を指定します。これにより、\(\sum_{n} d_n x_n\)を表現する式sum_dxが定義できます。

Note

「式」については次のページで詳しく説明します。

そして、以下のようにProblemインスタンスを作成して、sum_dxを加えることで\(\sum_n d_n x_n\)を目的関数として設定できます。

problem = jm.Problem('my_first_problem')
problem += sum_dx

Problemオブジェクトはデフォルトでは最小化問題になります。目的関数を最大化したい場合はProblemを構築する際にsense引数を以下のように指定してください。

problem = jm.Problem('my_first_problem', sense=jm.ProblemSense.MAXIMIZE)

等式制約#

最後に、等式制約に対応するConstraintオブジェクトを作成しましょう。

\[ \sum_{n=0}^{N-1} x_n = 1 \]

上記で説明したsumを使用して、この制約を次のように記述できます。

jm.sum(n, x[n]) == 1
\[\displaystyle \sum_{n = 0}^{N - 1} x_{n} = 1\]

jijmodelingの式における==は、通常のPythonとは異なり、新しいjijmodelingの式を返すことに注意してください。また、Constraintオブジェクトは第1引数に制約の名前を指定し、第2引数に比較式を指定する必要があります。（jijmodelingでは比較式として==、<=、>=を利用できます） このようにして構築したConstraintオブジェクトをProblemオブジェクトに追加することで数理モデルに制約を加えることができます。

problem += jm.Constraint("onehot", jm.sum(n, x[n]) == 1)

Note

「制約条件とペナルティ」については次のページでさらに詳しく説明します。