JijModeling 2.5.1 リリースノート

JijModeling 2.5.1 リリースノート#

このノートには 2.5.0 の内容も含まれています

JijModeling 2.5.0 のリリースは取り下げられたため、このノートには 2.5.0 の変更内容も含まれています。

機能強化#

Decorator API における jm.min、jm.max、jm.set の内包表記サポート#

旧来は、Decorator API を利用する際に内包表記（Python のジェネレータ式）を引数として受け取れるのは jm.sum と jm.prod のみでした。

本バージョンから、jm.min、jm.max、jm.set の一引数呼び出しでも、同様に内包表記を受け取れるようになりました。

import jijmodeling as jm


@jm.Problem.define("min/max/set comprehension example")
def problem(problem: jm.DecoratedProblem):
    N = problem.Length()
    x = problem.BinaryVar(shape=N)

    nonzero = jm.set(i for i in N if i != 0)
    problem += jm.min(x[i] for i in N) + jm.max(x[i] for i in nonzero)


problem
\[\begin{array}{rl} \text{Problem}\colon &\text{min/max/set comprehension example}\\\displaystyle \min &\displaystyle \min _{i=0}^{N-1}{{x}_{i}}+\max _{\substack{i=0\\i\neq 0}}^{N-1}{{x}_{i}}\\&\\\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} \]

数式出力：制約の添え字が読みやすく#

辞書や配列同士の直接比較による制約条件が、\(\LaTeX\) 出力では \(\forall\) を使って出力されるようになり、可読性が向上しました。

import jijmodeling as jm


@jm.Problem.define("container-vs-scalar-comp")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    L = problem.CategoryLabel()
    x = problem.BinaryVar(shape=N)
    y = problem.BinaryVar(dict_keys=(L, N - 1))
    z = problem.BinaryVar(dict_keys=(L, N - 1))

    problem += problem.Constraint("scalar-vs-tensor", 1 <= x)
    problem += problem.Constraint("tensor-vs-tensor", x <= x)
    problem += problem.Constraint("dict-vs-scalar", y <= 5)
    problem += problem.Constraint("dict-vs-dict", y <= z)


problem
\[\begin{array}{rl} \text{Problem}\colon &\text{container-vs-scalar-comp}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{dict-vs-dict}&\quad \displaystyle {y}_{i,j}\leq {z}_{i,j}\quad \forall \left(i,j\right)\;\text{s.t.}\;i\in L,j\in \left\{0,\ldots ,N-1-1\right\}\\\text{dict-vs-scalar}&\quad \displaystyle {y}_{i,j}\leq 5\quad \forall \left(i,j\right)\;\text{s.t.}\;i\in L,j\in \left\{0,\ldots ,N-1-1\right\}\\\text{scalar-vs-tensor}&\quad \displaystyle {x}_{i}\geq 1\quad \forall i\;\text{s.t.}\;i\in \left\{0,\ldots ,N-1\right\}\\\text{tensor-vs-tensor}&\quad \displaystyle {x}_{i}\leq {x}_{i}\quad \forall i\;\text{s.t.}\;i\in \left\{0,\ldots ,N-1\right\}\end{aligned} \\&\\\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}\\y&\in \mathop{\mathrm{TotalDict}}\left[\left\{\left\langle i,j\right\rangle \mid i\in L,j\in N-1\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 N-1\right\}\\z&\in \mathop{\mathrm{TotalDict}}\left[\left\{\left\langle i,j\right\rangle \mid i\in L,j\in N-1\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 N-1\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} \]

Placeholder の dtype に上限付き自然数とカテゴリーラベルを指定できるように#

Problem.Placeholder（および Graph、PartialDict、TotalDict などの型付き構築子）の dtype 引数は、これまで jm.DataType、NumPy のスカラー型、あるいはそれらから構成されるタプルに限られていました。 本バージョンから、dtype には次のものも追加で指定できるようになりました：

  • 自然数式 n：値が n より真に小さい自然数（すなわち \(\{0, 1, \dots, n - 1\}\) のいずれか）であることを表します。n には Python の整数リテラルのほか、自然数型の他のプレースホルダーや NamedExpr などの式も渡せます。

  • CategoryLabel L：値が L のラベルのうちのいずれかであることを表します。

  • 上記（あるいは他の指定可能な dtype）を要素とするタプル (T, T, ...)。

上記の dtype に関する追加に合わせて、型付き構築子である Problem.Natural（およびそのエイリアスである Problem.Length と Problem.Dim）でも less_than=natexpr キーワード引数を指定できるようになりました。これは Placeholder(dtype=natexpr) と同じく上限付き自然数型のプレースホルダーを宣言するもので、自然数値のプレースホルダーであるという意図をより明瞭に表現する書き方です。

import jijmodeling as jm

problem = jm.Problem("bounded natural shorthand")
N = problem.Natural("N")
i = problem.Natural("i", less_than=N)
x = problem.BinaryVar("x", shape=(N,))
problem += x[i]

problem
\[\begin{array}{rl} \text{Problem}\colon &\text{bounded natural shorthand}\\\displaystyle \min &\displaystyle {x}_{i}\\&\\\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}i&\in N&\quad &\text{A scalar placeholder in }N\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \]

Decorator API でも同じキーワード引数を利用できます。

@jm.Problem.define("bounded natural shorthand in Decorator API")
def problem(problem: jm.DecoratedProblem):
    N = problem.Length()
    i = problem.Dim(less_than=N)
    x = problem.BinaryVar(shape=(N,))
    problem += x[i]


problem
\[\begin{array}{rl} \text{Problem}\colon &\text{bounded natural shorthand in Decorator API}\\\displaystyle \min &\displaystyle {x}_{i}\\&\\\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}i&\in N&\quad &\text{A scalar placeholder in }N\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \]

より複雑な例として、以下の、無向グラフ \(G = (V, E)\) についての最適化問題を考えます。以前のバージョンでは辺の端点の型は単なる自然数として宣言する必要がありましたが、本リリースから、端点が \([0, V)\) の範囲に収まることを dtype を通じて表現できるようになりました：

import jijmodeling as jm

problem = jm.Problem("max cut", sense=jm.ProblemSense.MAXIMIZE)
V = problem.Natural("V")
# `E` の各要素が `[0, V)` のペアであることを直接宣言できるようになりました
# （従来は dtype=(jm.DataType.Natural, jm.DataType.Natural) と書く必要がありました）。
# この宣言は、 `problem.graph("E", dtype=V)` と書くこともできます。
E = problem.Placeholder("E", dtype=(V, V), ndim=1)
x = problem.BinaryVar("x", shape=(V,))
problem += jm.map(lambda u, v: (x[u] - x[v]) ** 2, E).sum()

problem
\[\begin{array}{rl} \text{Problem}\colon &\text{max cut}\\\displaystyle \max &\displaystyle \sum _{\left\langle u,v\right\rangle \in E}{{\left({x}_{u}-{x}_{v}\right)}^{2}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[V;\left\{0, 1\right\}\right]&\quad &1\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}E&\in \mathop{\mathrm{Array}}\left[(-);V\times V\right]&\quad &1\text{-dimensional array of placeholders with elements in }V\times V\\V&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\\end{alignedat}\end{array} \]

また、グラフの頂点にラベルを用いる場合を想定して、CategoryLabel をそのまま dtype として指定することもできるようになりました。 以下の例は、ラベルが頂点として使われるグラフの上で（Problem.Graph() を用いて）同じ問題を定義するものです。

problem = jm.Problem("max cut on a labeled graph", sense=jm.ProblemSense.MAXIMIZE)
L = problem.CategoryLabel("L")
edges = problem.Graph("edges", dtype=L)
x = problem.BinaryVar("x", dict_keys=L)
problem += jm.map(lambda u, v: (x[u] - x[v]) ** 2, edges).sum()

compiler = jm.Compiler.from_problem(
    problem,
    {
        "L": ["A", "B", "C"],
        "edges": [("A", "B"), ("B", "C"), ("C", "A")],
    },
)
instance = compiler.eval_problem(problem)

インスタンスデータとして与えられた値が宣言された dtype と整合しない場合（たとえば、頂点インデックスが V 以上であったり、L に含まれないラベルが渡されたりした場合）、コンパイラは範囲外エラーを報告します。

目的関数を代入で再設定できるように#

本バージョンから Problem.objective に直接代入して置き換えられるようになりました。 DecoratedProblem でも同じように problem.objective = ... と書けます。

たとえば、一度設定した目的関数を別の式に置き換えたり、problem.objective = 0 として目的関数を明示的にリセットしたりできます。

import jijmodeling as jm

problem = jm.Problem("set objective example")
x = problem.BinaryVar("x")
y = problem.BinaryVar("y")

problem.objective = x
problem.objective = y
problem.objective = 0


@problem.update
def _(problem: jm.DecoratedProblem):
    z = problem.BinaryVar()
    problem.objective = z


problem
\[\begin{array}{rl} \text{Problem}\colon &\text{set objective example}\\\displaystyle \min &\displaystyle z\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \left\{0, 1\right\}&\quad &0\text{-dim binary variable}\\y&\in \left\{0, 1\right\}&\quad &0\text{-dim binary variable}\\z&\in \left\{0, 1\right\}&\quad &0\text{-dim binary variable}\\\end{alignedat}\end{array} \]

生成関数による辞書の生成#

本バージョンから、gendict() 関数により、キー集合と生成関数を指定して配列を生成できるようになりました。 これは配列の genarray() や numpy の fromfunction() と類似の機能です。

import jijmodeling as jm


problem = jm.Problem("gendict example")
K = problem.CategoryLabel("K")
a = problem.Float("a", dict_keys=K)
x = problem.BinaryVar("x", dict_keys=K)
Sums = problem.NamedExpr("Sums", jm.gendict(lambda k: a[k] * x[k], K))


problem
\[\begin{array}{rl} \text{Problem}\colon &\text{gendict example}\\\displaystyle \min &\displaystyle 0\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{TotalDict}}\left[\mathrm{K};\left\{0, 1\right\}\right]&\quad &\text{a dictionary of }\text{binary}\text{ variables with key }K\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}a&\in \mathop{\mathrm{TotalDict}}\left[\mathrm{K};\mathbb{R}\right]&\quad &\text{A total dictionary of placeholders with keys }\mathrm{K}\text{, values in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Category Labels:}\\&\qquad \begin{array}{rl} K&\text{Category Label}\end{array} \\&\\&\text{Named Expressions:}\\&\qquad \begin{alignedat}{2}Sums&=\mathop{\mathtt{gen\_{}dict}}\left(\lambda \left(k\in \mathrm{K}\right)\ldotp {a}_{k}\cdot {x}_{k},K\right)&\quad &\in \mathop{\mathrm{TotalDict}}\left[K;\mathbb{R}\right]\\\end{alignedat}\end{array} \]

また、jm.genarray と同じように、Decorator API を利用している場合、内包表記を用いることもできます。ただし、for .. in ... は一つしか許容されません。

@jm.Problem.define("gendict example")
def problem(problem):
    problem = jm.Problem("gendict example")
    K = problem.CategoryLabel("K")
    a = problem.Float("a", dict_keys=K)
    x = problem.BinaryVar("x", dict_keys=K)
    Sums = problem.NamedExpr("Sums", jm.gendict(a[k] * x[k] for k in K))


problem
\[\begin{array}{rl} \text{Problem}\colon &\text{gendict example}\\\displaystyle \min &\displaystyle 0\end{array} \]

バグ修正#

添え字の要素と数値型の演算に失敗していたバグの修正#

以下のように Constraint の添え字の要素に対する数値演算が誤って型エラーとして判定されていた問題を修正しました。

import jijmodeling as jm


@jm.Problem.define("Example")
def problem(problem: jm.DecoratedProblem):
    K = problem.Float(ndim=1)
    x = problem.BinaryVar()
    problem += problem.Constraint("c", [k * x <= 0 for k in K])


problem
\[\begin{array}{rl} \text{Problem}\colon &\text{Example}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{c}&\quad \displaystyle k\cdot x\leq 0\quad \forall k\;\text{s.t.}\;k\in K\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \left\{0, 1\right\}&\quad &0\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}K&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\end{array} \]

product や filter の絡む数式出力を改善#

旧来は product や filter などを含む式が場合によって複雑な式として表示されていましたが、内包表記を使った読みやすい出力がされるようになりました。

import jijmodeling as jm

problem = jm.Problem("product and filter example")
N = problem.Natural("N")
M = problem.Natural("M")
x = problem.BinaryVar("x", shape=(N, M))
jm.product(N, M).filter(lambda i, j: i == j)
\[\left\{\left\langle i,j\right\rangle \mid i\in \left\{0,\ldots ,N-1\right\},j\in \left\{0,\ldots ,M-1\right\},i=j\right\}\]

制約族の定義で singleton list に対する comprehension をした時に problem.eval() が失敗するバグの修正#

以前は次のような問題定義が、JijModeling の型検査は（期待通り）通過するものの、 Problem.eval を呼び出すと Could not convert value from function of decision variable to SubscriptItem. というエラーが発生するバグがありました。

@jm.Problem.define("Min fail")
def min_fail(problem: jm.DecoratedProblem):
    x = problem.BinaryVar("x", shape=(1,))
    problem += problem.Constraint(
        "c", [x[j] == 0 for i in jm.range(1) for j in [i + 0]]
    )

本バージョンでは、上記の様な定義に対しても Problem.eval が正常に動作するように修正しました。