式

式とは

整数または実数変数に対する二項演算または単行演算を考えてみましょう。例えば\(x+y\)や\(x^2\)です。jijmodelingで定義された変数に対しても対応する演算が可能であり、その結果は「式」と呼ばれます。

import jijmodeling as jm

x = jm.BinaryVar("x")
y = jm.BinaryVar("y")
z = x + y
w = x ** 2

xとyはBinaryVarオブジェクトであり、zとwは「式」です。これらは「従属変数」であり、私たちが「決定変数」と呼んでいるものとは異なることに注意してください。

組み込み演算

Pythonの組み込み演算子（例：+）は、決定変数（例：BinaryVar）およびPlaceholderの両方に対して利用することができます。

x = jm.BinaryVar("x")
y = jm.BinaryVar("y")
z = x + y
repr(z)

"BinaryVar(name='x', shape=[]) + BinaryVar(name='y', shape=[])"

上記のような演算は代数的な処理（つまり、式木を構成する処理）になります。Pythonの組み込み関数reprを使用して式木の内容を確認することができます。また、Jupyter環境の場合はLaTeXを使用してより美しい表示を得ることができます。

式の次数

組み込み演算は線形演算に限定されないため、式が線形であるかどうかを判別するための関数is_linearが提供されています。

x = jm.BinaryVar("x")
jm.is_linear(x)  # True

w = x ** 2
jm.is_linear(w)  # False

式の次数を確認する関数としてis_quadraticやis_higher_orderも提供されています。

比較演算

等価演算子==および他の比較演算子（例：<=）についても、等式制約および不等式制約を構築するために利用することができます。2つの式木が同じかどうかを確認したい場合は、等価演算子==ではなくis_same関数を使用するように注意してください。

x = jm.BinaryVar("x")
y = jm.BinaryVar("y")
repr(x == y)

"BinaryVar(name='x', shape=[]) == BinaryVar(name='y', shape=[])"

jm.is_same(x, y)

False

インデックスと総和

Pythonの組み込みlistやnumpy.ndarrayと同様に、jijmodelingは多次元の決定変数やパラメータの要素にインデックスアクセスする機能をサポートしています。

x = jm.BinaryVar("x", shape=(3, 4))
x[0, 2]

\[\displaystyle x_{0, 2}\]

Note

x[0][2]とx[0, 2]は同じものを指しています。

x[0, 2]も式です。これは単項演算子**2が適用されたxの式木の場合と似ています。x[0]は、xに適用された「0番目の要素を取る」単項演算子[0]の式木です。また、決定変数を含まない式であれば添字として指定することができます。

x = jm.BinaryVar("x", shape=(3, 4))
n = jm.Placeholder("n")
x[2*n, 3*n]

\[\displaystyle x_{2 \cdot n, 3 \cdot n}\]

インデックス付けのためのクラスとしてElementがあります。これは総和の中の変数\(n\)を表すために利用できます。

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

jijmodelingでは総和を表現するために3つのステップを経る必要があります。

N = jm.Placeholder("N")
x = jm.BinaryVar("x", shape=(N,))

# Step1. [0, N-1]を取りうる範囲とする総和の中の変数$n$を導入
n = jm.Element('n', belong_to=(0, N))

# Step2. インデックスアクセスを用いて式$x_n$を作成
xn = x[n]

# Step3. 変数$n$に沿って$x_n$の総和を取る
jm.sum(n, xn)

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

\[ \mathrm{jm.sum(\overbrace{n}^{subscript}, \underbrace{x[n]}_{operand})} \]

Tip

上記のような単純な総和は省略形で書くことができます。

N = jm.Placeholder('N')
x = jm.BinaryVar(name='x', shape=(N,))
sum_x = x[:].sum()

Elementオブジェクト自体が式として扱えるため、\(\sum_n n x_n\)を次のように書くこともできます。

jm.sum(n, n * x[n])

\[\displaystyle \sum_{n = 0}^{N - 1} n \cdot x_{n}\]

jm.sumの結果も式になります。そのため、次のような同じ式を含むモデルも簡単に記述することができます。

n = jm.Element('n', belong_to=(0, N))
sum_x = jm.sum(n, x[n])
sum_x * (1 - sum_x)

\[\displaystyle \sum_{n = 0}^{N - 1} x_{n} \cdot \left(- \sum_{n = 0}^{N - 1} x_{n} + 1\right)\]

集合に沿った総和

数理モデルでは、しばしば集合\(V\)に沿った総和を取ります。例えば、以下のような総和です。

\[ \sum_{v \in V} x_v . \]

この総和では集合\(V\)に沿って非連続なインデックス（例: \([1, 4, 5, 9]\)や\([2, 6]\)など）が使用されます。

Tip

集合に沿った総和は、与えられた集合\(V\)に対するone-hot制約などでよく利用されます。

\[ \sum_{v \in V} x_v = 1 \]

このページで説明されているすべての式はConstraintオブジェクトの第2引数の値としても使えます。

N = jm.Placeholder('N')
x = jm.BinaryVar('x', shape=(N,))

# 集合$V$をPlaceholderオブジェクトとして定義
V = jm.Placeholder('V', ndim=1)

# $V$に沿って動く変数$v$を定義
v = jm.Element('v', belong_to=V)

# $V$に沿って総和を取る
sum_v = jm.sum(v, x[v])

また、集合\(V\)の実際のデータは以下のように指定する必要があります。

import jijmodeling_transpiler as jmt

problem = jm.Problem('Iterating over a Set')
problem += sum_v

instance_data = { "N": 10, "V": [1, 4, 5, 9]}
compiled_model = jmt.core.compile_model(problem, instance_data)

Jagged配列

時々、\(C_\alpha\)のような集合のまとまりを考慮する必要があります。例えば、K-hot制約を設定するような場合です。

\[ \sum_{i \in C_\alpha} x_i = K_\alpha. \]

これらの集合\(C_\alpha\)は異なる要素数を持つことがあります。例えば、以下のような場合です。

\[\begin{split} \begin{align*} C_1 &= [1, 4, 5, 9], \\ C_2 &= [2, 6], \\ C_3 &= [3, 7, 8] \end{align*} \end{split}\]

Placeholderオブジェクトを利用すれば、このような”いびつな”配列を表現することができます。

N = jm.Placeholder('N')
x = jm.BinaryVar('x', shape=(N,))

# 2次元のPlaceholderオブジェクトを定義
C = jm.Placeholder('C', ndim=2)

# K-hot制約の本数を定義
# 0次元方向の長さは”いびつな”配列であるために取得できないことに注意
M = C.len_at(0, latex="M")

K = jm.Placeholder('K', ndim=1)

# $/alpha$のインデックスを定義
a = jm.Element(name='a', belong_to=(0, M), latex=r"\alpha")
# $C_/alpha$毎の要素に沿った変数を定義
i = jm.Element(name='i', belong_to=C[a]) 

# K-hot制約の定義
k_hot = jm.Constraint('k-hot_constraint', jm.sum(i, x[i]) == K[a], forall=a)

また、\(C\)に対する実際のデータは以下のように渡す必要があります。

problem = jm.Problem('K-hot')
problem += k_hot

instance_data = {
    "N": 4,
    "C": [[1, 4, 5, 9],
          [2, 6],
          [3, 7, 8]],
    "K": [1, 1, 2],
}
compiled_model = jmt.core.compile_model(problem, instance_data)

複数のインデックスに対する総和

次のような複数の総和が含まれるケースを考えてみましょう。

\[ \sum_{i, j} Q_{ij} x_{ij} \]

上記のようなケースはjijmodelingで次のように実装できます。

# 変数の定義
Q = jm.Placeholder('Q', ndim=2)
I = Q.shape[0]
J = Q.shape[1]
x = jm.BinaryVar('x', shape=(I, J))
i = jm.Element(name='i', belong_to=(0, I))
j = jm.Element(name='j', belong_to=(0, J))
# $i$と$j$に沿った総和を取る
sum_ij = jm.sum([i, j], Q[i, j]*x[i, j])

複数の総和がある場合、jm.sumを複数回使用するのではなく、第1引数をリスト[subscript1, subscript2, ...]にすることもできます。 もちろん、これは\(\sum_{i, j} = \sum_{i} \sum_{j}\)であるため、jm.sumを複数回使用するのと同じ数理モデルになります。

sum_ij = jm.sum(i, jm.sum(j, Q[i, j]*x[i, j]))

条件付き総和

次のようにインデックスが特定の条件を満たす部分の総和を取るケースを考えてみましょう。

\[ \sum_{i<U} x_i \]

上記のようなケースはjijmodelingを使用して次のように実装できます。

# 変数を定義
I = jm.Placeholder('I')
x = jm.BinaryVar('x', shape=(I,))
i = jm.Element(name='i', belong_to=(0, I))
U = jm.Placeholder('U')
# $i<U$を満たすインデックスについて総和を取る
sum_i = jm.sum((i, i<U), x[i])

インデックスが特定の条件を満たす部分の総和を取るには、jm.sumの第1引数にタプル(index, condition)を指定する必要があります。

\[ \mathrm{jm.sum((\underbrace{i}_{index}, \overbrace{i<U}^{condition}), \underbrace{x[i]}_{operand})} \]

比較演算子<、<=、>=、>、==、!=および論理演算子&、|およびそれらの組み合わせを条件式として使用できます。例えば、

\[\begin{split} \sum_{\substack{i < U \\ i!=N}} d_i x_i \end{split}\]

は次のように実装できます。

# 変数の定義
d = jm.Placeholder('d', ndim=1)
I = d.shape[0]
x = jm.BinaryVar('x', shape=(I,))
U = jm.Placeholder('U')
N = jm.Placeholder('N')
i = jm.Element(name='i', belong_to=(0, I))
# 条件$i<U$と条件$i≠N$を満たす部分について総和を取る
sum_i = jm.sum((i, (i<U)&(i!=N)), d[i]*x[i])

\[ \mathrm{jm.sum((\underbrace{i}_{subscript}, \overbrace{(i<U)}^{condition 1} \underbrace{\&}_{logical operator} \overbrace{(i!=N)}^{condition 2}), \underbrace{d[i]*x[i ]}_{operand})} \]

複数条件付きの総和

複数の添字に対する総和演算に条件がある場合、例えば

\[\begin{split} \sum_{\substack{i>L \\ i!=N}} \sum_{j<i} R_{ij} x_{ij} \end{split}\]

のようなケースを考えてみましょう。これはjijmodelingで次のように実装することができます。

# 変数を定義
R = jm.Placeholder('R', ndim=2)
I = R.shape[0]
J = R.shape[1]
x = jm.BinaryVar('x', shape=(I, J))
i = jm.Element(name='i', belong_to=(0, I))
j = jm.Element(name='j', belong_to=(0, J))
N = jm.Placeholder('N')
L = jm.Placeholder('L')
# $i>L$かつ$i≠N$かつ$j<i$を満たす部分について総和を取る
sum_ij = jm.sum([(i, (i>L)&(i!=N)), (j, j<i)], R[i, j]*x[i, j])

jm.sumの第1引数には、[[(index 1, condition of index 1), (index 2, condition of index 2), ...]]のように指定する必要があります。[(index1, condition of index1), (index2, condition of index2), ...]のように指定することで、各インデックスに条件を付けた複数の総和演算を記述できます。

Caution

[(j, j<i), (i, (i>L)&(i!=N))]はエラーが発生します。なぜなら、\(i\)はまだ\(j<i\)の時点で定義されていないからです。 これは\(\sum_{\substack{i>L \\ i!=N}} \left( \sum_{j<i} \cdots \right)\)のように式で書くことができますが、\(\sum_{j<i} \left( \sum_{\substack{i>L \\ i!=N}} \cdots \right)\)は書くことができないことに対応します。複数の総和において添字に条件を課す順序に注意してください。