JijModeling 2.11.0 Release Notes

JijModeling 2.11.0 Release Notes#

Feature Enhancements#

Improved handling of functions with argument-dependent return types#

JijModeling has supported functions whose return types depend on their arguments. This release makes their handling more systematic and displays their types accurately, for example as (n : natural) -> Array[n; natural].

Several related bugs have also been fixed. In the Bugfixes section of these release notes, fixes associated with this change are marked with (Π).

Improved argument types for functions passed to `jm.map`#

As part of this change, argument types for functions passed to operations such as jm.map and jm.filter are now handled more precisely. In the following example, the function passed as the first argument to jm.map was previously inferred to take an arbitrary natural number (natural). Starting with this release, its argument is correctly typed as a natural number less than N.

import jijmodeling as jm

problem = jm.Problem("map argument types")
N = problem.Natural("N")
x = problem.BinaryVar("x", shape=(N,))
problem += jm.map(lambda i: x[i], N).sum()

print(problem.objective)

Expression(sum(N.map(lambda (i: N): x[i])))

As a result, programs that previous versions incorrectly accepted (even though they should have produced errors) are now correctly rejected. One example is the following stream of arrays whose types depend on their position \(n < N\) within the stream. JijModeling currently has no mechanism for safely handling streams or arrays whose element types depend on their positions, so this program should produce an error.

import jijmodeling as jm

try:

    @jm.Problem.define("problem")
    def problem(problem: jm.DecoratedProblem):
        N = problem.Natural()
        x = problem.NamedExpr(jm.map(lambda n: jm.genarray(lambda j: 42, n), N))

except Exception as e:
    print(e)

Traceback (most recent last):
    while inferring the type of expression `N.map(lambda n: genarray(lambda j: 42, (n)))`,
        defined at File "/var/folders/mg/mg6st30d18s7pxjjrk6pkxym0000gn/T/ipykernel_79079/1446842279.py", line 8, col 31-80
    while inferring the type of expression `N.map(lambda n: genarray(lambda j: 42, (n)))`,
        defined at File "/var/folders/mg/mg6st30d18s7pxjjrk6pkxym0000gn/T/ipykernel_79079/1446842279.py", line 8, col 31-80
    while inferring a common result type for `lambda n: genarray(lambda j: 42, (n))` over arguments of type `N`,
        defined at File "/var/folders/mg/mg6st30d18s7pxjjrk6pkxym0000gn/T/ipykernel_79079/1446842279.py", line 8, col 31-80

File "/var/folders/mg/mg6st30d18s7pxjjrk6pkxym0000gn/T/ipykernel_79079/1446842279.py", line 8, col 31-80:

    8  |          x = problem.NamedExpr(jm.map(lambda n: jm.genarray(lambda j: 42, n), N))
                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E-TE0026] A function of type `(n : N) -> Array[n; natural]` produces output elements whose type depends on its argument, and JijModeling cannot give them one common type.

Operations that build a collection from a function, such as `map`, `flat_map`, `genarray`, and `gendict`, need one type for all output elements (for `flat_map`, the elements of the returned collections). Where part of that type depends on the argument, JijModeling replaces it with a broader type that does not. For example, the type of numbers below the argument, or below a value computed from it, becomes the type of all natural numbers. JijModeling does not do this for array lengths or function parameter types.

Possible fix: make the array lengths and function parameter types in each output element's type independent of the argument. For an array whose length depends on the argument, build a stream instead, for example `jm.map(f, n)` instead of `jm.genarray(f, n)`, because the type of a stream has no length.

Hint: You can read the description and possible fix at https://jij-inc-jijmodeling.readthedocs-hosted.com/en/stable/error_codes/error/E-TE0026.html

Previously, this program was incorrectly inferred to have a type such as Stream[Array[n_1234, natural]], containing an undefined variable n_1234. Starting with this release, it is correctly reported as an error.

Bugfixes#

Bugfix (Π): Fix constraint detection errors when destructuring dictionary keys#

Constraints containing comprehensions that unpack dictionary (PartialDict / TotalDict) keys into their individual components (such as for i, j in c.keys() in the example below) previously caused an E-TE0014 error during constraint detection. Starting with this release, these cases run successfully:

import jijmodeling as jm


@jm.Problem.define("problem")
def problem(problem: jm.DecoratedProblem):
    N = problem.Length()
    c = problem.PartialDict(dtype=float, dict_keys=(N, N))
    x = problem.BinaryVar(dict_keys=c.keys())
    problem += problem.Constraint("onehot", jm.sum(x[i, j] for i, j in c.keys()) == 1)


problem.eval({"N": 2, "c": {(0, 0): 1.0, (1, 1): 1.0}})

Instance(raw=<builtins.Instance object at 0x754c23cf00>, annotations={})

Bugfix (Π): Fix constraint detection errors when using variables bound by earlier `for` clauses inside `genarray`#

Fixed an issue where using a variable bound by an earlier for clause as the length of a subsequent jm.genarray caused an E-TE0005 (unbound variable) error when constraint detection was enabled. For example, the following code previously raised an error such as error[E-TE0005] Unbound variable `d_...` , but now compiles successfully.

import jijmodeling as jm


@jm.Problem.define("problem")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    ub = problem.Natural(less_than=N)
    x = problem.BinaryVar(shape=(N,))
    problem += problem.Constraint(
        "onehot",
        jm.sum(
            x[t]
            for n in ub
            for j in n
            for s, d in [(n, j)]
            for t in jm.genarray(s + i for i in d)
        )
        == 1,
    )


problem.eval({"N": 3, "ub": 1})

Instance(raw=<builtins.Instance object at 0x754e3b6a00>, annotations={})

Bugfix (Π): Fix unexpected `__dangling_*` variable names in string representations#

When displaying problems with nested for clauses as strings, for example with print, unexpected variable names such as __dangling_* could appear. Starting with this release, the correct variable names are displayed:

import jijmodeling as jm


@jm.Problem.define("problem")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    a = problem.Placeholder(
        shape=(N,), dtype=(jm.DataType.NATURAL, jm.DataType.NATURAL)
    )
    x = problem.BinaryVar(shape=(N,))
    problem += jm.sum(x[s] for n in N for s, d in [a[n]])


print(problem)

Problem(name="problem", sense=MINIMIZE, objective=sum(stream(N.flat_map(lambda (n: natural): [a[n]].map(lambda ((s, d): Tuple[natural, natural]): (n, s, d)))).map(lambda ((n, s, d): Tuple[natural, natural, natural]): x[s])), constraints=[])

In previous releases, [a[n]] in the output above was displayed as [a[__dangling_0]].

Bugfix: Fix panics when accessing keys of dictionaries created with `gendict`#

Accessing the keys of a dictionary created with gendict could cause an unrecoverable panic, as in the following example:

import jijmodeling as jm


@jm.Problem.define("problem")
def problem(problem: jm.DecoratedProblem):
    keys = problem.Natural("keys", ndim=1)
    a = problem.Natural("a", ndim=1)
    d = problem.NamedExpr("d", jm.gendict(k for k in keys))
    problem += jm.sum(a[i] for n in d.keys() for i in n)


problem

\[\begin{array}{rl} \text{Problem}\colon &\text{problem}\\\displaystyle \min &\displaystyle \sum _{n\in \mathop{\mathtt{keys}}\left(d\right)}{\sum _{i\in n}{{a}_{i}}}\\&\\\text{where}&\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}{a}_{i}&\in \mathbb{N}&\qquad &\text{a }1\text{-dim array of placeholders with elements in }\mathbb{N}\\&\forall i\in \left\{0,\ldots ,\mathop{\mathtt{len\_{}at}}\left(a,0\right)-1\right\}&&\\&&&\\{keys}_{i}&\in \mathbb{N}&\qquad &\text{a }1\text{-dim array of placeholders with elements in }\mathbb{N}\\&\forall i\in \left\{0,\ldots ,\mathop{\mathtt{len\_{}at}}\left(keys,0\right)-1\right\}&&\\\end{alignedat}\\&\\&\text{Named Expressions:}\\&\qquad \begin{alignedat}{2}d&={\left\{ k\right\} }_{k\in keys}&\quad &\in \mathop{\mathrm{TotalDict}}\left[keys;\mathbb{N}\right]\\\end{alignedat}\end{array} \]

Previously, the code above caused the following unrecoverable error:

PanicException: internal error: entered unreachable code: ElementOf[stream(keys)] must wrap a set type, but got: Array[:; natural]

Starting with this release, this code works as expected.

Bugfix: Correct result types for sums and products of bounded natural numbers#

Fixed an issue where sum and prod over natural numbers less than N were incorrectly given a result type with the same bound N. Even when each element is less than N, their sum or product can be N or greater. Starting with this release, the result type is natural, without an upper bound. The result types of min and max remain N, since the minimum and maximum cannot exceed the elements’ bound.

import jijmodeling as jm

problem = jm.Problem("sum and prod types")
N = problem.Natural("N")
a = problem.Natural("a", shape=(3,), less_than=N)

print("a:", problem.infer(a))
print("sum:", problem.infer(a.sum()))
print("prod:", problem.infer(a.prod()))
print("min:", problem.infer(a.min()))
print("max:", problem.infer(a.max()))

a: Array[3; N]
sum: natural
prod: natural
min: N
max: N

Other Changes#

Fixed: Corrected inaccuracies in the API documentation and agent skill descriptions.