Tips

目的関数への項の追加

Problemの目的関数は上書きする仕様になっています。そのため、新しい目的関数を加えると既に設定されている目的関数を上書きしてしまうことに注意してください。

import jijmodeling as jm

c = jm.Placeholder("c", ndim=1)
N = c.len_at(0)
x = jm.BinaryVar("x", shape=(N,))
i = jm.Element("i", (0, N))
problem = jm.Problem("my problem")
problem += jm.sum(i, c[i] * x[i]) # 目的関数を設定

# 後から別の変数や式を追加したくなった場合は、
# 新しい目的関数として式を作るところから始める必要があります
d = jm.Placeholder("d", ndim=1)
M = d.len_at(0)
y = jm.BinaryVar("y", shape=(M,))
j = jm.Element("j", (0, M))
problem += jm.sum(i, c[i] * x[i]) + jm.sum(j, d[j] * y[j])

より複雑な目的関数を構築したい場合は、最終的な式を書き出す前に、簡単な項や式を組み立てから足し合わせることをおすすめします。例えば、以下のようにすると良いでしょう。

sum_of_xs = jm.sum(i, c[i] * x[i])
sum_of_ys = jm.sum(j, d[j] * y[j])
problem += sum_of_xs + sum_of_ys

Caution

現在のjijmodelingでは複数の目的関数を持つ数理モデルをサポートしていません。

集合に沿ったElementを定義したい場合

一部のユーザーはPythonの集合Setを使用してインデックス\(i \in \{0, 1, 2\}\)を以下のように作成したいと思うかもしれません。

import jijmodeling as jm
i = jm.Element("i", {0,1,2}) # このコードはエラーが出る

しかし、jijmodelingでは上記の書き方はサポートされていません。今回の例でいえば以下のように区間で表現する必要があります。（Elementの区間は半開区間であるため、\(\{0, 1, 2\}\)を表現するためには(0, 3)と書く必要があります）

i = jm.Element("i", (0, 3))

より複雑なユースケースの場合（インデックスが単なる整数の連続値でない場合など）には、次の2つの方法のいずれかで表現できるかを検討してみてください。

1つ目の選択肢は集合を表す一次元のPlaceholderを作成することです。この選択肢は\(E = \{2, 4, 10, 35, 36\}\)のような不連続な整数を含む集合を表現するときに役に立ちます。これにより、 Elementは集合を使ったかのように機能します。この方法を用いれば、\(e \in E\)を表現するElementが以下のように定義できます。

E = jm.Placeholder("E", ndim=1)
e = jm.Element("e", E)

ただし、数理モデルの中に具体的な集合内の値は現れないということに注意してください。その後、数理モデルをインスタンスに変換するときにEの実際の値を指定する必要があります。

もう1つの選択肢は範囲内の有効な値を制限する条件を使用することです。この選択肢はルールに従う整数の集合を用いる場合に役に立ちます。条件の付け方についてはこちらを参照してください。

条件付きのElementを扱いたい場合

しばしば、数理モデル中にある総和のインデックスが条件付けされていることがあります。例えば、\(i \neq j\)のような条件です。これらの条件は、インデックスを作成するときではなく、総和や制約を定義するときに指定されます。jijmodelingでは、sumの第1引数にタプル(<element>, <condition>)の形で条件付きのインデックスを定義することができます。この場合、<element>がインデックスとして使用され、<condition>が条件として設定され、<condition>が真であるときだけ足し合わされます。

例えば、偶数の\(i\)に対する\(x_i\)の総和を考えてみましょう。jijmodelingでは以下のように定義できます。

import jijmodeling as jm
i = jm.Element("i", (0, 100))
x = jm.BinaryVar("x", shape=(100,))

sum_over_even_is = jm.sum((i, i % 2 == 0), x[i])

同じ総和で使用される他のElementと比較を行うことも可能です。また、sumの第1引数には[[(index 1, condition of index 1), (index 2, condition of index 2), ...]]の形で入力が可能です。 この入力を利用する際の注意点としてcondition of index 1の中ではindex 2は使えない仕様のため、インデックスと条件の順序関係には気を付けるようにしてください。具体例として、以下ではjijmodelingで\(i \neq j\)である2つのインデックス\(i, j\)に対する総和を示します。

import jijmodeling as jm

i = jm.Element("i", (0, 100))
j = jm.Element("j", (0, 100))
x = jm.BinaryVar("x", shape=(100, 100))

jm.sum([i, (j, j!= i)], x[i, j])

\[\begin{split}\displaystyle \sum_{i = 0}^{99} \sum_{\substack{j = 0\\j \neq i}}^{99} x_{i, j}\end{split}\]

また、同様のタプル表記はConstraintの引数forallでも利用できます。

jm.Constraint("c1", x[i, j] - x[j, i] >= 0, forall=[i, (j, j != i)])

\[\begin{split}\begin{array}{cccc} & \text{c1} & \displaystyle x_{i, j} - x_{j, i} \geq 0 & \forall i \in \left\{0,\ldots,99\right\} \forall j \in \left\{j \in \left\{0,\ldots,99\right\} \mid j \neq i \right\} \\ \end{array}\end{split}\]

加えて、インデックスに対して比較演算だけでなく論理演算を適用することも可能です。ここでいう論理演算とは、論理積&、論理和|、排他的論理和^のことを指しています。

jm.sum((i, (i % 2 == 0) | (i % 5 == 0)), x[i, 0])

\[\begin{split}\displaystyle \sum_{\substack{i = 0\\\left(i \bmod 2\right) = 0 \lor \left(i \bmod 5\right) = 0}}^{99} x_{i, 0}\end{split}\]

両側を不等式で囲んだ制約を扱いたい場合

数理最適化では\(l \leq x + y \leq u\)のような両側を不等式で囲んだ制約を扱いたいケースも存在します。このような制約はjijmodelingでは直接サポートされておらず、そのまま実装しようとすると、Converting <class> to boolean is unsupportedという例外が発生します。

そのため、jijmodelingではこのような制約を2つに分けて、それぞれ1つの不等式で記述する必要があります。

import jijmodeling as jm

l, u = jm.Placeholder("l"), jm.Placeholder("u")
x = jm.IntegerVar("x", lower_bound=0, upper_bound=10)
y = jm.IntegerVar("y", lower_bound=5, upper_bound=20)

problem = jm.Problem("problem")
problem += jm.Constraint("greater than l", l <= x + y)
problem += jm.Constraint("less than u", x + y <= u)
problem

\[\begin{split}\begin{array}{cccc}\text{Problem:} & \text{problem} & & \\& & \min \quad \displaystyle 0 & \\\text{{s.t.}} & & & \\ & \text{greater than l} & \displaystyle l \leq x + y & \\ & \text{less than u} & \displaystyle x + y \leq u & \\\text{{where}} & & & \\& x & 0\text{-dim integer variable}\\ & & \text{lower bound: }0 & \\ & & \text{upper bound: }10 & \\& y & 0\text{-dim integer variable}\\ & & \text{lower bound: }5 & \\ & & \text{upper bound: }20 & \\\end{array}\end{split}\]

従属変数を使いたい場合

次のような制約をjijmodelingで書きたいとしましょう。

\[\begin{split} \begin{array}{cccc} & \text{constraint:} & \displaystyle y_{i} \leq c & \forall i \in \left\{0,\ldots,N - 1\right\} \\ \end{array}\quad \text{where}\quad y_{i} = a_{i} x_{i} + b \end{split}\]

この制約の中で\(y_i\)は従属変数となっています。jijmodelingでは、このような従属変数を書くことも難しくありません。また、必要に応じてset_latexで\(y_i\)としてLaTeX表示することも可能です。

import jijmodeling as jm

a = jm.Placeholder("a", ndim=1)
b = jm.Placeholder("b")
N = a.len_at(0, latex="N")
x = jm.BinaryVar("x", shape=(N,))
i = jm.Element("i", belong_to=N)
c = jm.Placeholder("c")

y = a[i] * x[i] + b
y.set_latex("y_i")
jm.Constraint("constraint", y <= c, forall=i)

\[\begin{split}\begin{array}{cccc} & \text{constraint} & \displaystyle y_i \leq c & \forall i \in \left\{0,\ldots,N - 1\right\} \\ \end{array}\end{split}\]

しかし、上記のコードは柔軟性に欠けている部分があります。なぜなら、\(y\)はインデックス\(i\)を明示的に使用して定義されており、同様の形の式が数理モデルの他の部分で使われていた場合に再利用することができないからです。この柔軟性を確保するには、Pythonの関数やlambda式を使うと良いでしょう。

y = lambda e: a[e] * x[e] + b
jm.Constraint("constraint", y(i) <= c, forall=i)

def y(e: jm.Element):
  y = a[e] * x[e] + b
  y.set_latex("y_{e.name}")
  return y
jm.Constraint("constraint", y(i) <= c, forall=i)

\[\begin{split}\begin{array}{cccc} & \text{constraint} & \displaystyle y_{e.name} \leq c & \forall i \in \left\{0,\ldots,N - 1\right\} \\ \end{array}\end{split}\]

異なる下限・上限を持つ多次元変数を扱いたい場合

多次元の決定変数を定義する際には、通常、lower_boundとupper_boundをスカラー値として指定します。この場合、すべての決定変数は同じ下限・上限が設定されます。

N = jm.Placeholder("N")
M = jm.Placeholder("M")
x = jm.IntegerVar("x", shape=(N, M), lower_bound=0, upper_bound=5)

上記のコードでは、N * M個の整数変数xが下限を0、上限を5として定義されています。では、異なる下限・上限を持つように定義したい場合はどうすれば良いのでしょうか？

この疑問を解消する方法として、lower_boundとupper_boundをPlaceholderで指定するという方法があります。0次元のPlaceholderの場合、これは通常の数値リテラルを与えたときと同じように機能します。一方で、決定変数と同じ次元を持つPlaceholderを使用することもでき、そのPlaceholderによって各変数の下限・上限を指定することができます。

以下は、変数\(x_{i,j}\)の上限を\(ub_{i,j}\)を個別に設定する例です。

import jijmodeling as jm

ub = jm.Placeholder("ub", ndim=2)
N = ub.len_at(0, latex="N")
M = ub.len_at(1, latex="M")
# 下限0、上限ubとする整数変数xを定義
x = jm.IntegerVar("x", shape=(N,M), lower_bound=0, upper_bound=ub)

決定変数とPlaceholderの次元および形状が一致している必要があることに注意してください。また、すべての決定変数に有効な下限・上限が設定されていることにも注意してください。上記のコードではubに基づいてNおよびMを定義しているため、その形状が一致していることが保証できています。

また、何らかの理由でPlaceholderの転置や他の軸を指定して上限・下限として利用したい場合は、Elementを使った特別な構文を利用することができます。例えば、変数\(x_{i,j}\)の上限をインデックスを反転させて\(ub_{j,i}\)の値にしたい場合です。これを行うには、軸に一致するElementを定義し、上限をub[j, i]として次のように指定します。

ub = jm.Placeholder("ub", ndim=2)
N = ub.len_at(0, latex="N")
M = ub.len_at(1, latex="M")
i = jm.Element("i", N)
j = jm.Element("j", M)
x = jm.IntegerVar("x", shape=(N, M), lower_bound=0, upper_bound=ub[j, i])

前述同様、すべての変数に有効な下限・上限が設定されていることに注意してください。加えて、上記のコードではNとMが等しい場合にのみ意味があることにも注意してください。また、この構文は総和と制約の中では使えないことにも注意してください。

異なるサイズのインデックスに対する総和を扱いたい場合

このTipでは少しニッチに思えるユースケースとして多次元のElementやインデックス付けに関する手法を説明していきます。

2次元の決定変数\(x\)があり、次のような制約を書きたいとしましょう。

\[ \sum_{a \in A_{n}} x_{n, a} = 0,\quad \forall n \in \{0,..., N-1\} \]

ここで\(A\)は\(N\)行の2次元の”いびつな配列”です。そのため、\(A\)を「リストのリスト」と解釈すると、リスト毎にインデックスとして利用することができます。

このような制約が何を意味するかを明確にするために、A = [[1, 2, 3], [0, 1, 4, 5], [2, 3, 5]]を例に考えてみましょう。具体的に制約を書き下すと以下のようになります。

\[ \sum_{a \in \{ 1, 2, 3 \}} x_{0, a} = 0 \ \land \ \sum_{a \in \{ 0, 1, 4, 5 \}} x_{1, a} = 0 \ \land \ \sum_{a \in \{ 2, 3, 5 \}} x_{2, a} = 0 \]

jijmodelingでは、この制約を次のように書くことができます。

import jijmodeling as jm

A = jm.Placeholder("A", ndim=2)
N = A.len_at(0, latex="N")
n = jm.Element("n", N) # "いびつな"配列の行数
a = jm.Element("a", A[n]) # 行毎のインデックス
x = jm.BinaryVar("x", shape=(3,6))

jm.Constraint("constraint", jm.sum(a, x[n, a]) == 0, forall=n)

\[\begin{split}\begin{array}{cccc} & \text{constraint} & \displaystyle \sum_{a \in A_{n}} x_{n, a} = 0 & \forall n \in \left\{0,\ldots,N - 1\right\} \\ \end{array}\end{split}\]

上記の例ではxの形状を具体的な数値で定義しました。実際の数理モデルでは形状もPlaceholderにするかインデックスエラーを避けるために他のパラメータに関連して定義することをお勧めします。このような制約を正しく定義するためには十分な決定変数xを定義するのが良いでしょう。具体的には、上記のコードの(3, 6)を(Aの行数, Aの列数の最大値)に置き換えれば良いでしょう。しかし、Aの行数はNですが、Aの列数の最大値は数理モデルの構築段階ではわからないという問題があります。そのため、追加でPlaceholderを定義し、インスタンスデータとして指定できるようにしておくと良いでしょう。

# `Aの列数の最大値`を意味するPlaceholderを定義
max_A = jm.Placeholder("max_A") 
x = jm.BinaryVar("x", shape=(N, max_A + 1))

problem = jm.Problem("problem")
problem += jm.Constraint("constraint", jm.sum(a, x[n, a]) == 0, forall=n)

jijmodeling_transpilerやJijZeptで使用するインスタンスデータは以下のように構築すると良いでしょう。

# "いびつな"配列を作成
data_A = [
    [1, 2, 3],
    [0, 1, 4, 5],
    [2, 3, 5],
    # ...
]
# "いびつな"配列の列数の最大値を取得
data_max_A = max(max(An) for An in data_A)

instance_data = {
    "A": data_A,
    "max_An": data_max_A,
}