ソルバーが決定する変数：決定変数

以下では、数理モデルの重要な構成要素の一つである決定変数について、JijModeling での宣言方法を見ていきます。 まずはいつも通りのモジュールのインポートから始めましょう。

単独の決定変数とその上下界の宣言

決定変数は各種ソルバーが制約条件と目的関数に基づいて値を決定する変数です。JijModeling は汎用モデラーであるため、代表的な以下の種類をサポートしています：

種類	数式	説明
BinaryVar()	\(\{0, 1\}\)	\(0\) または \(1\) の値を取るバイナリ変数。上下界の設定は不要。
IntegerVar()	\(\mathbb{Z}\)	整数変数。上下界の設定が必要。
ContinuousVar()	\(\mathbb{R}\)	実数値を取る連続変数。上下界の設定が必要。
SemiIntegerVar()	-	上下界内の整数値またはゼロの値をとる変数。上下界の設定が必要。
SemiContinuousVar()	-	上下界内の連続値またはゼロの値をとる変数。上下界の設定が必要。

概ねプレースホルダーの構築子と似ていますが、*Var で終わるものが決定変数、そうでないものがプレースホルダーの構築子です。 また、連続値の決定変数は FloatVar ではなく ContinuousVar となっている点に注意してください。

特定の種類の決定変数を宣言するには、その変数を登録する Problem オブジェクトに対して対応する「種類」と同じ名前のメソッドを呼び出してやれば大丈夫です。 それでは、バイナリ変数 \(x\) と、\(-5\) 以上 \(10.5\) 以下の範囲に値を取る連続変数 \(C' \in[-5, 10.5]\) を持つ数理モデルを定義してみましょう。 Plain API では次のように定義できます：

import jijmodeling as jm


problem = jm.Problem("Model with Variables")
x = problem.BinaryVar("x", description="適当な二値変数")
C = problem.ContinuousVar(
    "C'",
    lower_bound=-5,
    upper_bound=10.5,
    description="これまた適当な連続変数",
)

problem

\[\begin{array}{rl} \text{Problem}\colon &\text{Model with Variables}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}C'&\in \mathbb{R}\;\left(-5\leq C'\leq 10.5\right)&\quad &0\text{-dim continuous variable}\\&&&\text{これまた適当な連続変数}\\&&&\\x&\in \left\{0, 1\right\}&\quad &0\text{-dim binary variable}\\&&&\text{適当な二値変数}\\\end{alignedat}\end{array} \]

第 1 引数は変数の名前を表す必須引数です。また、upper_boundおよびlower_boundは変数の上下界を表すキーワード引数であり、バイナリ変数以外は必ず指定しなければいけません。 descriptionは Problem のものと同様、人間がわかりやすい説明を書くための省略可能なキーワード引数です。

単独の決定変数の上下界

upper_boundおよびlower_boundには、決定変数を含まない任意の JijModeling の式を書くことができます。 どのような式が書けるのかは「式の構築」を参考にしてください。

更に、Decorator API を使うと名前の指定を省略でき、この場合 Python 変数と同じ変数名が自動的に使われます。 次は Decorator API で同様のモデルを定義している例です。

import jijmodeling as jm


@jm.Problem.define("Model with Variables")
def deco_problem(deco_problem: jm.DecoratedProblem):
    # Decorator API の内側なので、 x の名前を省略している
    x = deco_problem.BinaryVar(description="適当な二値変数")
    # Decorator API 内であっても、名前を明示することもできる
    C = deco_problem.ContinuousVar(
        "C'",
        lower_bound=-5,
        upper_bound=10.5,
        description="これまた適当な連続変数",
    )


deco_problem

\[\begin{array}{rl} \text{Problem}\colon &\text{Model with Variables}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}C'&\in \mathbb{R}\;\left(-5\leq C'\leq 10.5\right)&\quad &0\text{-dim continuous variable}\\&&&\text{これまた適当な連続変数}\\&&&\\x&\in \left\{0, 1\right\}&\quad &0\text{-dim binary variable}\\&&&\text{適当な二値変数}\\\end{alignedat}\end{array} \]

この例では、\(x\) の変数名を省略して宣言していますが、ちゃんと期待通りの \(x\) として出力されています。 Decorator API 内での変数名の省略は義務ではなく、上のセルでの \(C'\) のように名前を明示することもできます。

変数名省略の条件

Decorator API で変数名を省略できるのは、x = problem.*Var(...) のように「変数一つ = Var の宣言一つ」のような形をしているときのみです。 x, y = (problem.BinaryVar(), problem.BinaryVar()) のように複数同時に宣言した場合などはエラーとなりますので注意してください。

決定変数の情報の取得

プレースホルダーの場合と同様、決定変数の一覧もProblem オブジェクトの decision_vars プロパティにより取得でき、以下で扱う添え字つき変数の情報も含まれています。

import jijmodeling as jm


@jm.Problem.define("Model with Variables")
def deco_problem(deco_problem: jm.DecoratedProblem):
    x = deco_problem.BinaryVar(description="適当な二値変数")
    C = deco_problem.ContinuousVar(
        "C'",
        lower_bound=-5,
        upper_bound=10.5,
        description="これまた適当な連続変数",
    )


deco_problem.decision_vars

{"C'": DecisionVariable(name="C'", kind=CONTINUOUS, shape=, lower_bound=-5, upper_bound=10.5, description="これまた適当な連続変数", ),
 'x': DecisionVariable(name="x", kind=BINARY, shape=, lower_bound=0, upper_bound=1, description="適当な二値変数", )}

このようにして得られる決定変数のメタデータは DecisionVar オブジェクトであり、宣言時に返ってくるオブジェクトと同じものです。 従って、decision_vars に含まれる DecisionVar オブジェクトも変数式として使うことができます。 特に、複数の @problem.update や @jm.Problem.define() デコレータで逐次的に Problem を更新していく場合、それ以前のデコレータブロック内で定義された変数を参照するために使うことができます。

Tip

将来的には @problem.update が定義済の変数たちを引数として取れるようにする変更が予定されています。期待してお待ちください！

添え字つき決定変数の宣言

それでは、添え字つきの決定変数の宣言方法を見ていきましょう。

決定変数の配列

決定変数の配列は、プレースホルダーの場合と同様、BinaryVar などの構築子に shape= キーワード引数として自然数から成る固定長のタプルを表す式を指定することで宣言でき、\(1\)次元の場合は単に自然数を表す式で与えることもできます。

決定変数の配列のシェイプの指定

決定変数の数はプレースホルダーの値のみから確定する必要があるため、プレースホルダーの場合と異なり shape 引数の成分に None を指定することはできず、また ndim= キーワード引数を使うこともできません。

それでは、\(N\)個の決定変数から成るようなバイナリ変数の配列\(x\)を持つモデルを定義してみましょう：

import jijmodeling as jm


@jm.Problem.define("Example Problem", sense=jm.ProblemSense.MAXIMIZE)
def problem(problem: jm.DecoratedProblem):
    # 個数を確定させるため、プレースホルダー $N$ を宣言する必要がある
    N = problem.Length()

    # $x$ の宣言
    x = problem.BinaryVar(shape=N)


problem

\[\begin{array}{rl} \text{Problem}\colon &\text{Example Problem}\\\displaystyle \max &\displaystyle 0\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \]

Tip

ここでは Decorator API を使って定義していますが、shapeの指定方法は（変数名が省略できない点を除けば）Plain API でも同様です。

次は shape にタプルを渡して二次元配列を定義している例です：

import jijmodeling as jm


multidim_arrays = jm.Problem("multidimensional arrays", sense=jm.ProblemSense.MINIMIZE)
N = multidim_arrays.Length("N")  # Plain API なので変数名を指定している
M = multidim_arrays.Length("M")
x = multidim_arrays.BinaryVar(
    "x",
    shape=(N, M),  # N x M 配列
)

multidim_arrays

\[\begin{array}{rl} \text{Problem}\colon &\text{multidimensional arrays}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[N\times M;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}M&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \]

決定変数配列の上下界の指定

決定変数の配列に対しては、次に該当するような式を upper_bound / lower_bound に指定することができます：

1. スカラー

2. スカラーを要素に持ち、同じシェイプの配列の式

3. 添え字から上下界を表すスカラーへの関数式

ただし、いずれも決定変数を含まない式である必要があります。

これらの指定方法は、上下界でそれぞれ別のものを使うことができます。次は (1) と (2) を使って上下界が与えられている例です。

import jijmodeling as jm


problem = jm.Problem("Bounds for variable arrays")
N = problem.Length("N")
lb = problem.Integer("lb")
ubs = problem.Integer("ub", shape=N)
a = problem.IntegerVar("a", shape=N, lower_bound=lb + 1, upper_bound=ubs)

problem

\[\begin{array}{rl} \text{Problem}\colon &\text{Bounds for variable arrays}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}a&\in \mathop{\mathrm{Array}}\left[N;\mathbb{Z}\right]\;\left(lb+1\leq {a}_{i}\leq {ub}_{i}\right)&\quad &1\text{-dim integer variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}lb&\in \mathbb{Z}&\quad &\text{A scalar placeholder in }\mathbb{Z}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\ub&\in \mathop{\mathrm{Array}}\left[N;\mathbb{Z}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{Z}\\\end{alignedat}\end{array} \]

lb はゼロ次元のスカラー、 ub は長さ \(N\) の一次元配列として宣言されたプレースホルダーです。 これらを基に、長さ \(N\) の一次元決定変数配列 \(a\) は次のような上下界が設定されています：

• 下界：添え字によらず \(a_i \geq \mathit{lb} + 1\)（上記の (1) に相当）

• 上界：添え字 \(i = 0, \ldots, N - 1\) ごとに \(a_i \leq \mathit{ub}_i\)（上記の (2) に相当）

(3) の添え字からの関数式として与える例としては、やや人工的ですが次のような例が考えられます：

import jijmodeling as jm


problem = jm.Problem("Another bound examples with lambda")

N = problem.Length("N")
M = problem.Length("M")
s = problem.ContinuousVar(
    "s",
    shape=(N,M),
    lower_bound=0,
    upper_bound=lambda i, j: i + j,
)

problem

\[\begin{array}{rl} \text{Problem}\colon &\text{Another bound examples with lambda}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}s&\in \mathop{\mathrm{Array}}\left[N\times M;\mathbb{R}\right]\;\left(0\leq {s}_{i,j}\leq i+j\right)&\quad &2\text{-dim continuous variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}M&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \]

この例では、シェイプ \(N \times M\) の二次元配列 \(s\) に対し、以下のように上下界が設定されることになります：

• 下界：添え字 \(i\) によらず、\(s_{i,j} \geq 0\)（上記の (1) に相当）

• 上界：添え字 \(i = 0, \ldots, N - 1\) および \(j = 0, \ldots, M - 1\) ごとに、\(s_{i,j} \leq i + j\)（上記の (3) に相当）

このように、同一シェイプの配列を用意したり、複雑な式には添え字からの関数を使うことによって、決定変数の配列に対しても柔軟に上下界を指定することができます。

決定変数の辞書

決定変数の辞書に関しては、『決定変数の「個数」』で触れたようにコンパイル後に個数が確定している必要があるため、TotalDict のみしか宣言できないようになっています。 決定変数の辞書を宣言するには、BinaryVar, IntegerVar, ... などの構築子に対して、dict_keys キーワード引数を渡すことで宣言できます。 これは、決定変数の配列の宣言に shape を渡す必要があったのと同じです。

決定変数の辞書を宣言する際に、dict_keys に渡すことができるのは次の式です：

1. 決定変数を含まない自然数式 \(n\)（\(n\) 未満の自然数の集合 \(\mathbb{N}_{<n} = \{0, \ldots, n - 1\}\) と同一視）

2. Python 上の文字列のリスト

3. problem.CategoryLabel によって定義されたカテゴリーラベル

4. (1)-(3) を要素に持つタプル

注意

決定変数構築子に ndim または shapeの少なくとも一方と、dict_keys を同時に指定すると、コンテナの種類が確定できないためエラーとなります。

以下は、カテゴリーラベルと自然数の集合のタプルをキーに持つ決定変数の辞書を定義している例です：

import jijmodeling as jm


problem_for_dict = jm.Problem("Dec Var Keys demonstration")
N = problem_for_dict.Length("N")
L = problem_for_dict.CategoryLabel("L")
x = problem_for_dict.BinaryVar("x", dict_keys=(L, N))

problem_for_dict

\[\begin{array}{rl} \text{Problem}\colon &\text{Dec Var Keys demonstration}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{TotalDict}}\left[\left\{\left\langle i,j\right\rangle \mid i\in L,j\in \left\{0,\ldots ,N-1\right\}\right\};\left\{0, 1\right\}\right]&\quad &\text{a dictionary of }\text{binary}\text{ variables with key }\left\{\left\langle i,j\right\rangle \mid i\in L,j\in \left\{0,\ldots ,N-1\right\}\right\}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\\&\\&\text{Category Labels:}\\&\qquad \begin{array}{rl} L&\text{Category Label}\end{array} \end{array} \]

決定変数の辞書の上下界の指定

決定変数の辞書の lower_bound および upper_bound の設定についても、「決定変数配列の上下界」の節で紹介したのと同様に、以下の値を指定することができます：

1. スカラー

2. スカラーを要素に持ち、同じキー集合を持つ TotalDict

3. 添え字から上下界を表すスカラーへの関数式

辞書とカテゴリーラベルを使った問題定義の例

以下はナップサック問題をカテゴリーラベルを使って定式化しなおしたものです：

import jijmodeling as jm


@jm.Problem.define("Knapsack (vars only, CATEGORY LABEL)")
def knapsack_cat_dict(problem: jm.DecoratedProblem):
    L = problem.CategoryLabel()
    # TotalDict 構築子を使ってみる
    v = problem.TotalDict(dtype=float, dict_keys=L, description="各アイテムの価値")
    # dict_keys を使ってみる
    w = problem.Float(dict_keys=L, description="各アイテムの重量")
    x = problem.BinaryVar(
        dict_keys=L, description="アイテム $i$ を入れるときのみ $x_i = 1$"
    )


knapsack_cat_dict

\[\begin{array}{rl} \text{Problem}\colon &\text{Knapsack (vars only, CATEGORY LABEL)}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{TotalDict}}\left[\mathrm{L};\left\{0, 1\right\}\right]&\quad &\text{a dictionary of }\text{binary}\text{ variables with key }L\\&&&\text{アイテム $i$ を入れるときのみ $x_i = 1$}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}v&\in \mathop{\mathrm{TotalDict}}\left[\mathrm{L};\mathbb{R}\right]&\quad &\text{A total dictionary of placeholders with keys }\mathrm{L}\text{, values in }\mathbb{R}\\&&&\text{各アイテムの価値}\\&&&\\w&\in \mathop{\mathrm{TotalDict}}\left[\mathrm{L};\mathbb{R}\right]&\quad &\text{A total dictionary of placeholders with keys }\mathrm{L}\text{, values in }\mathbb{R}\\&&&\text{各アイテムの重量}\\\end{alignedat}\\&\\&\text{Category Labels:}\\&\qquad \begin{array}{rl} L&\text{Category Label}\end{array} \end{array} \]

これだけだと、\(N\)のかわりに\(L\)を定義しているだけですね。 そこで、更に「一部のアイテムの組 \((i, j)\)に対して、ナップサックに同時に詰めると追加の価値（シナジーボーナス）\(s_{i, j}\)が発生する」という追加条件を考えてみます。 このような場合に、PartialDict は大きな効力を発揮します：

import jijmodeling as jm


@jm.Problem.define("Knapsack (vars only, with synergy)")
def knapsack_synergy(problem: jm.DecoratedProblem):
    L = problem.CategoryLabel()
    v = problem.TotalDict(dtype=float, dict_keys=L, description="各アイテムの価値")
    w = problem.Float(dict_keys=L, description="各アイテムの重量")
    x = problem.BinaryVar(
        dict_keys=L, description="アイテム $i$ を入れるときのみ $x_i = 1$"
    )
    # PartialDict を使ってシナジーボーナスを表現！
    s = problem.PartialDict(
        dtype=float, dict_keys=(L, L), description="一部のアイテム間のシナジーボーナス"
    )


knapsack_synergy

\[\begin{array}{rl} \text{Problem}\colon &\text{Knapsack (vars only, with synergy)}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{TotalDict}}\left[\mathrm{L};\left\{0, 1\right\}\right]&\quad &\text{a dictionary of }\text{binary}\text{ variables with key }L\\&&&\text{アイテム $i$ を入れるときのみ $x_i = 1$}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}s&\in \mathop{\mathrm{PartialDict}}\left[\mathrm{L}\times \mathrm{L};\mathbb{R}\right]&\quad &\text{A partial dictionary of placeholders with keys }\left(\mathrm{L},\mathrm{L}\right)\text{, values in }\mathbb{R}\\&&&\text{一部のアイテム間のシナジーボーナス}\\&&&\\v&\in \mathop{\mathrm{TotalDict}}\left[\mathrm{L};\mathbb{R}\right]&\quad &\text{A total dictionary of placeholders with keys }\mathrm{L}\text{, values in }\mathbb{R}\\&&&\text{各アイテムの価値}\\&&&\\w&\in \mathop{\mathrm{TotalDict}}\left[\mathrm{L};\mathbb{R}\right]&\quad &\text{A total dictionary of placeholders with keys }\mathrm{L}\text{, values in }\mathbb{R}\\&&&\text{各アイテムの重量}\\\end{alignedat}\\&\\&\text{Category Labels:}\\&\qquad \begin{array}{rl} L&\text{Category Label}\end{array} \end{array} \]

\(s\) が "A partial dictionary of placeholders..." と説明されているのが重要です。これにより、「\(s\) は一部の\(L\)の組み合わせについてだけ定義されている」という条件が表現されているのです。 こうした定義はタプルのリストとそれと同じ長さの実数配列の組を使えば表現できなくもありませんが、辞書を使うことでより素直で自然な記述が可能になっています。