総和演算 Sum

JijModelingで総和を表すSumの使い方を紹介します。

基本的な総和演算

まずシンプルな総和 $`\sum_{i=0}^{n-1}d_i x_i`$の記述方法を紹介します。ここでdはデータが入るPlaceholderで、xが決定変数となるバイナリ変数です。

この式はJijModelingでは以下のように実装されます。

import jijmodeling as jm

d = jm.Placeholder('d', dim=1)
n = d.shape[0]
x = jm.Binary('x', shape=(n, ))

i = jm.Element('i', (0, n))
term = jm.Sum(i, d[i]*x[i])

ここで総和の範囲を(0, n)のようなタプルで表していますが、これは0からn-1までを表していることに注意してください。Pythonのrangeと同じような振るような振る舞いです。

また添え字が0から始まる場合は0を省略することもできます。

# jm.Element("i", (0, n)) と同じ
i = jm.Element("i", n)

集合に対する総和

上記のような範囲を指定する総和以外にもある集合の要素に対して総和を取りたいことも多いです。そのような場合も似たような記述を行うことができます。

例えば

$$\sum_{v \in V} v x_v$$

という項を作りたいと思います。ここでVは整数を要素に持つ集合です。JijModelingでは以下のように実装します。

import jijmodeling as jm
V = jm.Placeholder('V', dim=1)
n = V.shape[0]
x = jm.Binary('x', shape=n)

v = jm.Element('v', V)

term = jm.Sum(v, v * x[v])

このようにElementの第二引数にVを入れるだけです。この第二引数にスカラー値が来ると範囲に対する総和として解釈され、次元(dim)が1以上のPlaceholderが来ると集合に対しての総和として解釈されます。

!!! info "Jupyter notebook で確認" Jupyter notebookを使っている場合は上記のサンプルコードのtermをcellで表示すると数式として描画されるので、今どのような総和の実装になっているのかを分かりやすく確認することができます。

添字(Element)を辞書で表す

先ほどまではSum関数の前に総和を取るための添え字としてElementクラスのオブジェクトを生成していました。しかし、同じ添え字を用いつつ総和の範囲を変えたい場合は辞書型を使うことができます。

例えば最初に紹介した

$$\sum_{i=0}^{n-1}d_i x_i$$

のもう一つの実装の方法としては、

import jijmodeling as jm

d = jm.Placeholder('d', dim=1)
e = jm.Placeholder('e', dim=1)
n = d.shape[0]
m = e.shape[0]
x = jm.Binary('x', shape=(n, ))

i = jm.Element('i', (0, n))
term = jm.Sum({i: (0, m)}, d[i]*x[i])

という実装方法ができます。この場合、定義した総和は

$$\sum_{i=0}^{m-1}d_i x_i$$

と等価になります。

添え字に対して条件を設ける

総和に対して以下のように条件を設けたい場合があります。

\sum_{j = 0}^{n-1}
\sum_{\substack{i=0 \\ i != j}}^{n-1} d_{i, j} x_i x_j

このような場合の記述はSum関数の第一引数をタプルを用いて(添字, 条件)という書き方で表現します。

import jijmodeling as jm

d = jm.Placeholder('d', dim=1)
n = d.shape[0]
x = jm.Binary('x', shape=(n, ))

i = jm.Element('i', (0, n))
j = jm.Element('i', (0, n))

term = jm.Sum(j, jm.Sum((i, i!=j), d[i, j]*x[i]*x[j]))

!!! info "条件の演算について" 条件同士の演算でandやorがPythonだと用いる事ができますが、これらはJijModelingでは使用することができません。代わりに&演算子と|演算子を用いてください。

!!! info "等号演算子について" 上記のような条件を表すために==演算子を使用しているのでJijModelingの数式同士を==で比較した場合はbool値が返って来ないので数式が等価であるかという比較を==演算子ではできないことに注意してください。

!!! note "Sum関数の第三引数に条件を書く記法について" 現在、Sum関数はタプルではなく第三引数に条件を書くこともできますが、そちらは非推奨で今後のバージョンアップで廃止予定です。

複数のSumを省略して書く

先ほどのように多重の総和が出てくる場合、Sumをたくさん書く必要があります。そうするとコードが長くなって見づらくなってしまいます。
そこでJijiModelingではSum関数の第一引数をリストで指定することで複数のSumを表現することができます。

import jijmodeling as jm

d = jm.Placeholder('d', dim=2)
n = d.shape[0]
x = jm.Binary('x', shape=(n, ))

i = jm.Element('i', (0, n))
j = jm.Element('j', (0, n))

term = jm.Sum([j, (i, i!=j)], d[i, j]*x[i]*x[j])

上記の条件付き総和の例を一つSumを省略して記述しました。

このリストにおいて、リストの中は Element | Tuple[Element, Condition] |Dict[str, Expression]のいずれかの型を混ぜて記述することができます。