JijModeling 2.5.1 Release Notes

JijModeling 2.5.1 Release Notes#

This Note includes the contents of 2.5.0

As JijModeling 2.5.0 has been yanked, this note contains also contains the changes in 2.5.0.

Feature Enhancements#

Comprehension syntax for `jm.min`, `jm.max`, and `jm.set` in the Decorator API#

Previously, when using the Decorator API, only jm.sum and jm.prod accepted a comprehension (Python generator) expression as their single argument.

Starting with this version, unary calls to jm.min, jm.max, and jm.set also accept comprehension expressions in the same way.

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} \]

Math output: More readable constraint indices#

Constraints created by directly comparing dictionaries or arrays are now rendered in \(\LaTeX\) output using \(\forall\), improving readability.

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} \]

Bounded naturals and category labels are now allowed as a `Placeholder` `dtype`#

The dtype argument of Problem.Placeholder (and its shorthands such as Graph, PartialDict, and TotalDict) used to be limited to a jm.DataType, a NumPy scalar type, or a tuple built out of those. Starting with this version, dtype additionally accepts:

a natural-number expression n, declaring that the values are natural numbers strictly less than n (i.e. drawn from \(\{0, 1, \dots, n - 1\}\)); the bound n may also be a Python integer literal or another placeholder/named expression of natural-number type.
a CategoryLabel L, declaring that the values are labels drawn from L.
a tuple (T, T, ...) whose components are any of the above (or any other accepted dtype).

Along with the additions on dtype as described above, the shorthand constructors Problem.Natural (and its aliases: Problem.Length and Problem.Dim) now also accept a less_than=natexpr keyword argument. This declares the same bounded-natural type placeholder variable as Placeholder(dtype=natexpr), while more clearly communicating the intent of it being a scalar natural placeholder:

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} \]

The same keyword argument is available in the 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} \]

For a more complex example, consider the following optimization problem involving an undirected graph \(G = (V, E)\). Previously, edge endpoints had to be declared as plain naturals; with this release you can express the intent that they must lie in \([0, V)\):

import jijmodeling as jm

problem = jm.Problem("max cut", sense=jm.ProblemSense.MAXIMIZE)
V = problem.Natural("V")
# We can now say that each entry of `E` is a pair of vertices in [0, V)
# (previously we had to write dtype=(jm.DataType.Natural, jm.DataType.Natural)).
# Alternatively, we may write this as 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} \]

When the vertices of a graph are named rather than indexed, a CategoryLabel can now be used directly as the dtype. Here is the same problem, written with Problem.Graph(), but on a graph whose vertices are identified by labels rather than integer indices:

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)

When a value supplied through the instance data is not consistent with the declared dtype (for example a vertex index \(\geq V\), or a label not in L), the compiler will report an out-of-range error instead of silently accepting the value.

Objective functions can now be replaced by assignment#

In this version, you can now replace the objective function directly by assigning to Problem.objective. The same problem.objective = ... syntax is also available for DecoratedProblem.

For example, you can replace an already-defined objective with another expression, or explicitly reset it with 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} \]

Generating dictionaries with generator functions#

Starting with this version, the gendict() function can be used to generate dictionaries by specifying a set of keys and a generator function. This is similar to the array version genarray(), and to NumPy’s 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} \]

Like genarray, using comprehensions is supported when using the Decorator API, but only one for .. in ... clause is allowed in a comprehension.

@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} \]

Bug Fixes#

Fix bug where operations between subscript elements and numeric types failed#

Fixed an issue where numeric operations on Constraint subscript elements, as shown below, were incorrectly treated as type errors.

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} \]

Improved math rendering for expressions involving `product` and `filter`#

Previously, expressions involving product and filter could be rendered as overly complex formulas in some cases. They are now displayed in a more readable form using comprehension-style notation.

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\}\]

Fix bug where `problem.eval()` failed when using a comprehension over a singleton list in a constraint family definition#

In previous versions, a problem definition like the following passed JijModeling’s type checks, as it should, but calling Problem.eval raised the error 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]]
    )

This version fixes the issue so that Problem.eval works correctly for definitions like the one above.