ユーザーが入力する変数：プレースホルダーとカテゴリーラベル

ユーザーが入力する変数：プレースホルダーとカテゴリーラベル#

本章では、JijModeling において現れる二種類の変数のうち、ユーザーが入力するデータであるプレースホルダーとその変種カテゴリーラベルについて、その宣言方法や情報の取得方法について述べていきます。

単独のプレースホルダーの宣言#

この節では、プレースホルダーの種類と、単独のプレースホルダーの宣言方法について学びます。

プレースホルダーは宣言時に種類を指定する必要があります。 プレースホルダーはコンパイル時にユーザーが入力する値であり、入力データに関する情報を適切に表現するためにいくつかの種類があります。 代表的なプレースホルダーの型は以下の通りです：

種類

数式

説明

別名

Binary()

\(\{0, 1\}\)

\(0\) または \(1\) の値をとる二値プレースホルダー。

-

Natural()

\(\mathbb{N}\) または \(\{0, \ldots, N-1\}\)

ゼロも含む自然数。配列のサイズや添え字などを表すのに使われる。less_than キーワード引数に別の自然数式 N を指定することで、\(\{0, \ldots, N-1\}\) の範囲に制限できる。

Dim(), Length()

Integer()

\(\mathbb{Z}\)

負の数も含む整数値。

-

Float()

\(\mathbb{R}\)

一般の実数値（浮動小数点数値）プレースホルダー。

-

これらのタプル

\(\mathbb{Z} \times \mathbb{R}\)

成分ごとに型の決まった、固定長のタプル。一般にリストと組み合わせて使う。

-

プレースホルダーを宣言するには、上記の種類と同じ名前の Problem のメソッドを呼ぶ必要があります。

プレースホルダーの使い分け

プレースホルダーの種類については、Natural と Float だけ覚えておけば簡単なモデルの記述には十分でしょう。 特に、以下の基準を念頭に置いておくと使い分けがわかりやすいでしょう：

  1. 配列のサイズやアイテムの個数などを表すものは自然数として宣言し、Natural やよりわかりやすい Dim, Length といった別名で宣言する。

  2. それ以外の数値は Float や、場合によってより細分された型の宣言を使えばよい。

例を見るため、ここではナップサック問題に必要な単独のプレースホルダーを宣言してみましょう。 Plain API では次のようにして宣言できます：

import jijmodeling as jm

knapsack_placeholders = jm.Problem("Knapsack (Placeholders only)", sense=jm.ProblemSense.MAXIMIZE)
W = knapsack_placeholders.Float("W", description="ナップサックの耐荷重")
N = knapsack_placeholders.Length("N", description="アイテム数")

knapsack_placeholders
\[\begin{array}{rl} \text{Problem}\colon &\text{Knapsack (Placeholders only)}\\\displaystyle \max &\displaystyle 0\\&\\\text{where}&\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\&&&\text{アイテム数}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{ナップサックの耐荷重}\\\end{alignedat}\end{array} \]

ここでは、耐荷重を表す実数値のプレースホルダー W と、アイテム数を表す自然数のプレースホルダー N を一つずつ持つ数理モデルを定義しています。 このようにして宣言されたプレースホルダーは、Placeholder クラスのインスタンスとして表され、プレースホルダーのメタデータを保持しています。

W
\[W\in \mathbb{R},\text{ナップサックの耐荷重}\]
N
\[N\in \mathbb{N},\text{アイテム数}\]

また、プレースホルダーが式中に現れた場合、自動的にその値を参照する式として扱われます。 試しに、A に \(1\) を足してみましょう。

W + 1
\[W+1\]

また、Decorator API を使えば、Python 変数と同じ名前の場合、宣言時にプレースホルダーの名前を省略できます。

@jm.Problem.define("Another Problem with Placeholder")
def knapsack_placeholders(problem: jm.DecoratedProblem):
    W = problem.Float(description="ナップサックの耐荷重")
    N = problem.Length(description="アイテム数")


knapsack_placeholders
\[\begin{array}{rl} \text{Problem}\colon &\text{Another Problem with Placeholder}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\&&&\text{アイテム数}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{ナップサックの耐荷重}\\\end{alignedat}\end{array} \]

変数名省略の条件

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

Placeholder() 構築子

上の表に掲げた problem.Float, problem.Natural などの構築子は、実はより一般的な Placeholder() 構築子の特別な場合になっており、たとえばproblem.Natural は problem.Placeholder(dtype=jm.DataType.NATURAL) の省略記法として実装されています。dtypeには、

  • jm.DataType列挙体のバリアント

  • Python 組み込みの型指定子 float, int

  • NumPy の型指定子 numpy.uint*, numpy.int*（* 以下のビット数の情報は単純に無視されます）

  • （指定された自然数 N 未満の自然数の型 \(\{0, \ldots, N-1\}\) という指定をするための）自然数式

  • カテゴリーラベル

  • これらのタプル

などが指定できます。

タプルなどより複雑な型を持つようなものについては、Placeholder 構築子を使ってより詳細な仕様を指定することができるようになっています。また、Placeholder も他の特化型の構築子同様、Decorator API による変数名の省略もサポートしています。

カテゴリーラベルの宣言#

「JijModeling における変数」でも触れた通り、カテゴリーラベルは「辞書のキーとして使うことができ、具体的な値の候補はコンパイル時に与えられるラベルの集合」なのでした。 カテゴリーラベルの宣言方法はプレースホルダーとほぼ同様であり、数理モデルに対して CategoryLabel() 関数を呼び出して登録することで宣言します。 Plain API でのカテゴリーラベルの宣言方法は以下のようになります：

import jijmodeling as jm


problem_catlab_plain = jm.Problem("Category Label Only")
L_plain = problem_catlab_plain.CategoryLabel("L", description="適当なカテゴリーラベル")

problem_catlab_plain
\[\begin{array}{rl} \text{Problem}\colon &\text{Category Label Only}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\\&\text{Category Labels:}\\&\qquad \begin{array}{rl} L&\text{適当なカテゴリーラベル}\end{array} \end{array} \]

プレースホルダーと同様、名前を表す必須引数と、必要に応じて人間向けの説明を書く省略可能な description キーワード引数を取ります。 また、Decorator API を使うとプレースホルダーの場合と同様にカテゴリーラベル名を省略できます（もちろん明示することもできます）：

import jijmodeling as jm


@jm.Problem.define("Category Label Only")
def problem_catlab_deco(problem: jm.DecoratedProblem):
    L = problem.CategoryLabel(description="適当なカテゴリーラベル")


problem_catlab_deco
\[\begin{array}{rl} \text{Problem}\colon &\text{Category Label Only}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\\&\text{Category Labels:}\\&\qquad \begin{array}{rl} L&\text{適当なカテゴリーラベル}\end{array} \end{array} \]

Problem オブジェクトに登録されているカテゴリーラベルの一覧は、category_labels プロパティにより取得できます。 また、個別のカテゴリーラベルに属する値の個数を表す式は jm.count() 関数や jm.CategoryLabel.count() メソッドにより取得できます（数式上は \(\#L\)と表記されます）。

プレースホルダーおよびカテゴリーラベルの情報の取得#

数理モデルに登録されたプレースホルダーの一覧は、Problem オブジェクトの placeholders プロパティにより取得できます。 このプロパティはプレースホルダー名をキーとし、それぞれのメタデータを値とする辞書を返します。 この一覧には、以下で扱う添え字つき変数の情報も含まれています。 また、カテゴリーラベルについては、Problem オブジェクトの category_labels プロパティにより、同様にカテゴリーラベル名をキーとする辞書が得られます。

import jijmodeling as jm

ph_catlab_problem = jm.Problem("Placeholder and Category Label Info")
N = ph_catlab_problem.Length("N")
L = ph_catlab_problem.CategoryLabel("L", description="適当なカテゴリーラベル")
A = ph_catlab_problem.Float("A", dict_keys=(N, L))

print(f"Placeholders: {ph_catlab_problem.placeholders}")
print(f"Category Labels: {ph_catlab_problem.category_labels}")

Placeholders: {'A': Placeholder(name="A", dict, dict_keys=set((N, L)): (natural, CategoryLabel(L)), dtype=Scalar(Float), jagged=false, ), 'N': Placeholder(name="N", ndim=0, dtype=Scalar(Natural), jagged=false, )}
Category Labels: {'L': <jijmodeling.CategoryLabel object at 0x77d21ce08530>}

このようにして得られるメタデータは、プレースホルダーについては Placeholder オブジェクト、カテゴリーラベルについては CategoryLabel オブジェクトであり、宣言時に返ってくるオブジェクトと同じものです。 従って、これらの辞書に要素として含まれるオブジェクトも変数式として使うことができます。 特に、複数の @problem.update や @jm.Problem.define() デコレータで逐次的に Problem を更新していく場合、それ以前のデコレータブロック内で定義された変数を参照するために使うことができます。

Tip

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

添え字つきプレースホルダーの宣言#

以下では、添え字つきプレースホルダーの宣言方法について見ていきます。「JijModeling における変数」で触れた通り、添え字つきの変数には配列によるものと辞書によるものの二種類がありますので、順に見ていきましょう。

添え字つきのカテゴリーラベルはない

カテゴリーラベルは、辞書のキーとして出現できる型を新たに追加するための概念であり、特定の型の値を指定するプレースホルダーよりも一段上の抽象的な概念です。 このため、プレースホルダーと異なり、「添え字つきのカテゴリーラベル」のような概念はありません。

プレースホルダーの配列#

プレースホルダーの配列を宣言する方法は二つあります。それぞれについて見ていきましょう。

シェイプを指定したプレースホルダー配列の宣言#

プレースホルダー配列の宣言で最も推奨されるものは、 shape キーワード引数を使うことです。 shapeキーワード引数には、自然数から成る固定長のタプルを表す式を指定することができます。 また、次元が\(1\)の場合は単に自然数を表す式で与えることもできます。 ここでは、\(N\)や\(W\)などの単独のプレースホルダーだけではなく、各アイテムの価値を表す一次元配列 v と、重さを表す一次元配列 w を持つようなナップサック問題を部分的に定義してみましょう。：

import jijmodeling as jm

@jm.Problem.define("Knapsack (Placeholders only, with arrays)", sense=jm.ProblemSense.MAXIMIZE)
def knapsack_placeholders(problem: jm.DecoratedProblem):
    W = problem.Float(description="ナップサックの耐荷重")
    N = problem.Length(description="アイテム数")

    # shape キーワード引数を使い長さ N の一次元配列を宣言
    # 一次元なので、shape=N としても shape=(N,) としても同じ意味
    v = problem.Float(description="各アイテムの価値", shape=(N,))
    w = problem.Float(description="各アイテムの重さ", shape=N)


knapsack_placeholders
\[\begin{array}{rl} \text{Problem}\colon &\text{Knapsack (Placeholders only, with arrays)}\\\displaystyle \max &\displaystyle 0\\&\\\text{where}&\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\&&&\text{アイテム数}\\&&&\\v&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\&&&\text{各アイテムの価値}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{ナップサックの耐荷重}\\&&&\\w&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\&&&\text{各アイテムの重さ}\\\end{alignedat}\end{array} \]

また、プレースホルダーの配列の shape の成分には None を指定することができます。 この場合、None に指定された次元も一定の長さであることが要求されますが、その長さはコンパイル時に与えられたインスタンスデータの値から推論されます。 この機能は、以下のように部分的に長さに制約がある配列を定義したい場合に便利です：

import jijmodeling as jm


@jm.Problem.define("Partially determined shape")
def partial_shape(problem: jm.DecoratedProblem):
    a = problem.Float(ndim=1)
    N = a.len_at(0)
    c = problem.Float(shape=(N, None))
    M = c.len_at(1)
    x = problem.BinaryVar(shape=(N, M))
    problem += jm.sum(a[i] * c[i, j] * x[i, j] for i in N for j in M)

partial_shape
\[\begin{array}{rl} \text{Problem}\colon &\text{Partially determined shape}\\\displaystyle \min &\displaystyle \sum _{i=0}^{\mathop{\mathtt{len\_{}at}}\left(a,0\right)-1}{\sum _{j=0}^{\mathop{\mathtt{len\_{}at}}\left(c,1\right)-1}{{a}_{i}\cdot {c}_{i,j}\cdot {x}_{i,j}}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[\mathop{\mathtt{len\_{}at}}\left(a,0\right)\times \mathop{\mathtt{len\_{}at}}\left(c,1\right);\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}a&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\c&\in \mathop{\mathrm{Array}}\left[\mathop{\mathtt{len\_{}at}}\left(a,0\right)\times (-);\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\end{array} \]

次元のみを指定した配列の宣言#

もう一つの（あまり推奨されない）方法は、ndim キーワード引数を用いるものです。 プレースホルダーの構築子の ndim キーワード引数として自然数の定数リテラルを渡すことで、次元のみ指定し、各次元の具体的な長さはコンパイル時にインスタンスデータを与えた時に確定するようなプレースホルダー配列が宣言できます。

shape と ndim の同時指定について

ndim と shape キーワード引数を同時に指定することもできますが、この場合 shapeの成分数と ndim の値が正確に一致している必要があります。

たとえば、上で定義した knapsack_placeholders は ndim を使って次のように定義することができます：

import jijmodeling as jm


@jm.Problem.define("Knapsack (vars only, with ndim)", sense=jm.ProblemSense.MAXIMIZE)
def knapsack_placeholders_ndim(problem: jm.DecoratedProblem):
    W = problem.Float(description="ナップサックの耐荷重")
    v = problem.Float(ndim=1, description="各アイテムの価値")
    N = v.len_at(0)
    w = problem.Float(shape=N, description="各アイテムの重さ")


knapsack_placeholders_ndim
\[\begin{array}{rl} \text{Problem}\colon &\text{Knapsack (vars only, with ndim)}\\\displaystyle \max &\displaystyle 0\\&\\\text{where}&\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}v&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\&&&\text{各アイテムの価値}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{ナップサックの耐荷重}\\&&&\\w&\in \mathop{\mathrm{Array}}\left[\mathop{\mathtt{len\_{}at}}\left(v,0\right);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\&&&\text{各アイテムの重さ}\\\end{alignedat}\end{array} \]

ここで、len_at() メソッドは与えられた配列 array の \(i\) 番目の軸の長さを返すメソッドです。 \(w, v, x\) の長さはいずれも同じ長さですので、\(v\)を 1 次元配列として宣言しておき、残る \(w\), \(x\) はその長さを使って shape を指定する形にしているのです。 このように、最初に \(N\) を独立して定義する方法と、配列の長さから復元する方法とでは、定義される数理モデルは意味的には同じですが、インスタンスデータの与え方が異なります。 たとえば、最初の knapsack_placeholders の例（定義およびその更新）では、\(N\) も Length プレースホルダーとして宣言しているため、インスタンスの生成時に W, v, w だけではなく N の値もインスタンスデータとして与える必要があります。 一方で、\(N\) をプレースホルダーではなく len_at を使って別の式として構築している knapsack_placeholders_ndim では、\(N\)の値は入力値 v から推論されるため、コンパイル時には W, v, w の値のみを指定するだけで済みます。

どういう時に長さに相当するプレースホルダーを導入し、どういう時に ndim + len_at を使うべきでしょうか？ 一つの目安は、単一の配列内の複数軸の長さの間に依存関係がある場合、長さに相当するプレースホルダーを定義するべき、というものです。

例として、距離行列を表すシェイプ \(N \times N\) の多次元配列 \(d\) を定義することを考えます：

import jijmodeling as jm


@jm.Problem.define("Distance matrix")
def dist_matrix(problem: jm.DecoratedProblem):
    N = problem.Length()
    d = problem.Float(shape=(N, N))


dist_matrix
\[\begin{array}{rl} \text{Problem}\colon &\text{Distance matrix}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}d&\in \mathop{\mathrm{Array}}\left[N\times N;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \]

この例では、二次元配列\(d\)の二つの軸はどちらも長さ\(N\)を持つ必要があり、この制約は ndim=2 という指定では表現できず、まず\(N\)を定義し shape に指定する必要があるのです。

また、旧来の JijModeling 1 系統では、Placeholder には永らく ndim 宣言しか存在しなかったため、たとえば上の knapsack_placeholders_ndim は次のように定義されることが多くありました：

v = problem.Float(ndim=1, description="各アイテムの価値")
w = problem.Float(ndim=1, description="各アイテムの重量")

しかし、これでは \(v, w\) の間のシェイプの関係が表現できないため、JijModeling 2 以降ではこのような長さの一致性が強制できない定義は強く非推奨としており、シェイプの間に非自明な関係がある場合は必ずどこかで shape を指定することを強く推奨します。

タプルの配列としてのグラフ

たとえば、V が超点数を表す自然数式のとき、G = problem.Graph(dtype=V) とすると、\(G\) は \(\{0, \ldots, V-1\}\) を頂点集合として持つグラフの辺集合にあたるプレースホルダーとして宣言されます。 実は、この構築子は一次元配列と「単独のプレースホルダー」で触れたタプルの組み合わせで表現されており、次のように書いたのと同値です：

G = problem.Placeholder(dtype=(V, V), ndim=1)

ですので、N = G.len_at(0) とすることで \(G\) の（重複を込みで数えた）辺の総数を取得することができますし、配列に関する種々の演算を使ってグラフを操作することができるようになります。

また、後述する辞書を使えば、辺にラベルがついたようなグラフも表現できるようになります。 このように、JijModeling ではタプルと配列を組み合わせて、複雑な構造を表現できるようになっているのです。

2.0.0 以降は Jagged Array は強く非推奨

JijModeling 1 系統には、シェイプが均一ではない Jagged Array というコレクションも用意されていました。 しかし、Jagged Array はその不均一性から型システムなどによる検証を受けづらいため、JijModeling 2 ではJagged Array は強く非推奨となっており、将来のリリースで取り除くことが計画されています。 こうした配列とタプルの組み合わせや後述する辞書を使うと、グラフ構造や \(0\) 起点でなかったり疎な構造を表すことができますので、移行の際にはこうした新たな構成要素を用いて Jagged Array を用いない記述へと置き換えることを強く推奨します。

プレースホルダーの辞書#

プレースホルダーの辞書は、同様に Float や Length などの構築子に shape のかわりに dict_keys キーワード引数を渡すことで宣言できます。 決定変数の挙動と合わせるため、dict_keysのみが指定された場合そのプレースホルダー辞書は TotalDict として宣言されますが、同時に partial_dict=True 引数を渡すと PartialDict として宣言されるようになります。

TotalDict として宣言されている場合（つまり、partial_dict が指定されていないか False に設定されている場合）、dict_keys に指定できるものは以下の通りです：

  1. 決定変数を含まない自然数式 \(n\)

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

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

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

一方で、PartialDict として宣言されている場合、以下が指定できるようになります：

  1. jm.DataType.INTEGER、Python の型識別子 int、または numpy.int*（整数を表す識別子）

  2. jm.DataType.NATURAL または numpy.uint*

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

  4. Python の型識別子 str

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

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

  7. (1)-(6) を要素に持つタプル

また、TotalDict() 構築子や PartialDict() を Problem オブジェクトに対して呼び出すことでもプレースホルダーの辞書を宣言できます。

プレースホルダー辞書に ndim 相当がない理由

プレースホルダー配列における ndim 相当の引数は存在しません。これは、キーの型を省略して成分数だけ与えた場合、インスタンスデータへのアクセスなしに具体的なキーの型を確定することができないためです。

以下は、ナップサック問題の各アイテムを、自然数ではなくカテゴリーラベルとして宣言し、各アイテムの価値と重さをその辞書として宣言する例です：

import jijmodeling as jm


@jm.Problem.define("Knapsack with dict placeholders", sense=jm.ProblemSense.MAXIMIZE)
def knapsack_dict(problem: jm.DecoratedProblem):
    W = problem.Float(description="ナップサックの耐荷重")
    L = problem.CategoryLabel(description="アイテムのカテゴリーラベル")
    v = problem.Float(description="各アイテムの価値", dict_keys=L)
    w = problem.Float(description="各アイテムの重さ", dict_keys=L)


knapsack_dict
\[\begin{array}{rl} \text{Problem}\colon &\text{Knapsack with dict placeholders}\\\displaystyle \max &\displaystyle 0\\&\\\text{where}&\\&\\&\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 \mathbb{R}&\quad &\text{A scalar placeholder 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{アイテムのカテゴリーラベル}\end{array} \end{array} \]