Operations on Arrays and Dictionaries

User-provided variables: placeholders and category labels and Solver-determined variables: decision variables explained how to define arrays and dictionaries of different variable types. JijModeling can also work with arrays and dictionaries containing general elements, not only variables. We refer to these collectively as collections. For a detailed conceptual explanation of arrays and dictionaries and guidance on choosing between them, see Arrays and dictionaries of variables in Variables in JijModeling.

This chapter first reviews the different kinds of collections, then explains the functions used to generate them and how to access their elements. The next chapter, Folding and Streams, also explains how to treat arrays and dictionaries as streams and take their sums and products.

import jijmodeling as jm

Generating Collections: genarray() and gendict()

As described in User-provided variables: placeholders and category labels and Solver-determined variables: decision variables, arrays and dictionaries can be introduced when declaring variables. They can also be generated from other expressions. Use genarray() to generate an array and gendict() to generate a dictionary.

Array Generation with genarray()

genarray() is similar to NumPy’s fromfunction()[1]. It generates a new array from a shape and a function (the generator function) that maps indices to elements. The following example uses genarray to generate an array of shape \((N, M)\) whose elements are the sums of their respective indices:

problem = jm.Problem("Array and Dict Example")
N = problem.Length("N")
M = problem.Length("M")

jm.genarray(lambda i, j: i + j, (N, M))

\[{\left( i+j\right) }_{\begin{subarray}{l} i\in \left\{0,\ldots ,N-1\right\}\\j\in \left\{0,\ldots ,M-1\right\}\end{subarray} }\]

Within the Decorator API, you can write the same expression concisely with a comprehension:

@problem.update
def _(problem: jm.DecoratedProblem):
    display(jm.genarray(i + j for (i, j) in (N, M)))

\[{\left( i+j\right) }_{\begin{subarray}{l} i\in \left\{0,\ldots ,N-1\right\}\\j\in \left\{0,\ldots ,M-1\right\}\end{subarray} }\]

Here, the tuple (N, M) on the right-hand side of in is shorthand for the Cartesian product of N and M. This notation is explained further in Folding and Streams.

Comprehensions passed to genarray() support exactly one for clause and do not support if clauses. For example, using multiple for clauses as follows results in an error:

try:

    @jm.Problem.define("genarray example")
    def problem(problem):
        N = problem.Natural()
        M = problem.Natural()
        a = problem.Float(shape=(N, M))
        x = problem.BinaryVar(shape=N)
        Sums = problem.NamedExpr(jm.genarray(a[i, j] * x[i] for i in N for j in M))

except SyntaxError as e:
    print(str(e))

error[E-SE0002] A `genarray` comprehension must have exactly one for-clause.

Possible fix: use a single `for` that iterates over the whole shape or key set at once.

File "/tmp/ipykernel_769/1800573765.py", line 9, col 46-82:

    9  |          Sums = problem.NamedExpr(jm.genarray(a[i, j] * x[i] for i in N for j in M))
                                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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

Dictionary Generation with gendict()

The dictionary generator gendict() creates a new dictionary from an expression representing a key set and a generator function that maps keys to values. Because the generator function always returns a value, a dictionary generated by gendict() is always a TotalDict.

The following example generates a dictionary keyed by a category label \(L\) and a natural number \(N\):

problem = jm.Problem("Array and Dict Example")
N = problem.Natural("N")
L = problem.CategoryLabel("L")
x = problem.BinaryVar("x", dict_keys=L)
jm.gendict(lambda l, n: x[l] + n, (L, N))

\[{\left\{ {x}_{l}+n\right\} }_{\begin{subarray}{l} l\in L\\n\in N\end{subarray} }\]

In the Decorator API, gendict() also supports comprehensions containing exactly one for clause and any number of if clauses.

@problem.update
def _(problem: jm.DecoratedProblem):
    display(jm.gendict(x[l] + n for (l, n) in (L, N) if n % 2 == 0))

\[{\left\{ {x}_{l}+n\right\} }_{\begin{subarray}{l} l\in L\\n\in \left\{0,\ldots ,N-1\right\}\\n\bmod 2=0\end{subarray} }\]

Obtaining the Domains of Arrays and Dictionaries

For Placeholder and DecisionVar objects, the tuple representing an array’s shape is available through the shape attribute. For general expressions, use the Expression.shape() method. The expression representing a dictionary’s key set is available through Expression.keys(). Array expressions also provide Expression.len_at(n) for obtaining the size of the \(n\)-th dimension. These operations are useful when formulating mathematical models, for example when defining sums or constraints that iterate over a domain.

Element Access and Slicing with Indices

As with Python’s built-in lists and dictionaries or numpy.ndarray, elements of JijModeling collections can be accessed with multidimensional indices such as x[i, j]. Specifically, JijModeling supports indexing expressions of the following types:

1. Multidimensional arrays

   • Allowed indices: natural-number expressions that contain no decision variables

2. Dictionaries

   • Allowed indices: expressions that contain no decision variables and match the dictionary’s key type; these can be integers, strings, category labels, or tuples composed of them

3. Tuples

   • Allowed indices: natural-number expressions that contain no decision variables and are within the tuple’s length

In every case, an index cannot contain a decision variable. The following example accesses elements of an array and a dictionary by index:

import jijmodeling as jm


@jm.Problem.define("Array and Dict Example")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    L = problem.CategoryLabel()

    w = problem.Float(shape=N)  # N-element array
    x = problem.BinaryVar(dict_keys=(N, L))  # Dictionary

    problem += jm.sum(w[i] * x[i, l] for i in N for l in L)


problem

\[\begin{array}{rl} \text{Problem}\colon &\text{Array and Dict Example}\\\displaystyle \min &\displaystyle \sum _{i=0}^{N-1}{\sum _{l\in L}{{w}_{i}\cdot {x}_{i,l}}}\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}{x}_{i,j}&\in \left\{0,1\right\}&\qquad &\text{a dictionary of }\text{binary}\text{ decision variables}\\&\forall i\in \left\{0,\ldots ,N-1\right\},\;\forall j\in \mathrm{L}&&\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}N&\in \mathbb{N}&\qquad &\text{a scalar placeholder in }\mathbb{N}\\&&&\\{w}_{i}&\in \mathbb{R}&\qquad &\text{a }1\text{-dim array of placeholders with elements in }\mathbb{R}\\&\forall i\in \left\{0,\ldots ,N-1\right\}&&\\\end{alignedat}\\&\\&\text{Category Labels:}\\&\qquad \begin{array}{rl} L&\text{Category Label}\end{array} \end{array} \]

Multiple components can be specified at once, as in x[i,j,k]. However, using more indices than the number of tuple components, array dimensions, or dictionary key components results in a type error, as shown below.

import jijmodeling as jm


@jm.Problem.define("Array and Dict Example, oversubscripted")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    M = problem.Natural()

    w = problem.Float(shape=(N, M))  # N × M array

    try:
        problem += jm.sum(w[i, j, i] for i in N for j in M)  # ERROR: too many indices
    except Exception as e:
        print(e)

Traceback (most recent last):
    while checking if expression `sum(stream(N.flat_map(lambda i: M.map(lambda j: (i, j)))).map(lambda (i, j): w[i, j, i]))` has type `float!`,
        defined at File "/tmp/ipykernel_769/3614808236.py", line 12, col 20-60
    while inferring the type of expression `sum(stream(N.flat_map(lambda i: M.map(lambda j: (i, j)))).map(lambda (i, j): w[i, j, i]))`,
        defined at File "/tmp/ipykernel_769/3614808236.py", line 12, col 20-60
    while inferring the type of expression `sum(stream(N.flat_map(lambda i: M.map(lambda j: (i, j)))).map(lambda (i, j): w[i, j, i]))`,
        defined at File "/tmp/ipykernel_769/3614808236.py", line 12, col 20-60
    while inferring the type of expression `stream(N.flat_map(lambda i: M.map(lambda j: (i, j)))).map(lambda (i, j): w[i, j, i])`,
        defined at File "/tmp/ipykernel_769/3614808236.py", line 12, col 27-59
    while inferring the type of expression `stream(N.flat_map(lambda i: M.map(lambda j: (i, j)))).map(lambda (i, j): w[i, j, i])`,
        defined at File "/tmp/ipykernel_769/3614808236.py", line 12, col 27-59
    while checking if the type of expression `lambda (i, j): w[i, j, i]` is a function with domain `Tuple[natural, natural]`,
        defined at File "/tmp/ipykernel_769/3614808236.py", line 12, col 27-59
    while inferring the type of expression `lambda (i, j): w[i, j, i]` under application with argument types `Tuple[natural, natural]`,
        defined at File "/tmp/ipykernel_769/3614808236.py", line 12, col 27-59
    while inferring the type of expression `w[i_860755560, j_2137274828, i_860755560]`,
        defined at File "/tmp/ipykernel_769/3614808236.py", line 12, col 27-37
    while checking if type `Array[N, M; float]` can be subscripted with (i_860755560, j_2137274828, i_860755560): (natural, natural, natural),
        defined at File "/tmp/ipykernel_769/3614808236.py", line 12, col 27-37

File "/tmp/ipykernel_769/3614808236.py", line 12, col 27-37:

    12  |          problem += jm.sum(w[i, j, i] for i in N for j in M)  # ERROR: too many indices
                                     ^^^^^^^^^^

error[E-TE0018] Too many subscripts: the array has 2 dimension(s) (shape `[N, M]`), but 3 subscript(s) were given (types: `natural, natural, natural`).

Possible fix: give the array at most one subscript per dimension.

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

Array indices also support slice notation such as x[:, 1].

import jijmodeling as jm


@jm.Problem.define("Slicing example")
def problem(problem: jm.DecoratedProblem):
    N = problem.Natural()
    M = problem.Natural()

    w = problem.Integer(shape=N)  # N-element array
    x = problem.BinaryVar(shape=(N, M))  # N × M array

    problem += problem.Constraint("sum-per-n", [x[i, :].sum() == w[i] for i in N])


problem

\[\begin{array}{rl} \text{Problem}\colon &\text{Slicing example}\\\displaystyle \min &\displaystyle 0\\&\\\text{s.t.}&\\&\begin{aligned} \text{sum-per-n}&\quad \displaystyle \sum _{{i}_{1}=0}^{M-1}{{x}_{i,\left(\colon \right),{i}_{1}}}={w}_{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}_{i,j}&\in \left\{0,1\right\}&\qquad &\text{a }2\text{-dim array of }\text{binary}\text{ decision variables}\\&\forall i\in \left\{0,\ldots ,N-1\right\},\;\forall j\in \left\{0,\ldots ,M-1\right\}&&\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}M&\in \mathbb{N}&\qquad &\text{a scalar placeholder in }\mathbb{N}\\&&&\\N&\in \mathbb{N}&\qquad &\text{a scalar placeholder in }\mathbb{N}\\&&&\\{w}_{i}&\in \mathbb{Z}&\qquad &\text{a }1\text{-dim array of placeholders with elements in }\mathbb{Z}\\&\forall i\in \left\{0,\ldots ,N-1\right\}&&\\\end{alignedat}\end{array} \]

Slices that specify a step or stop index, such as x[1, 1:N:2], are also supported. For details on slice syntax, see the Python docs on “Slicings”.

---

[1]

Depending on the form of its generator function, NumPy’s fromfunction() may generate an array with a shape different from the one supplied, or even a scalar. JijModeling’s genarray() is guaranteed to return an array with the supplied shape regardless of the generator function’s form.