User-provided variables: placeholders and category labels

User-provided variables: placeholders and category labels#

In this chapter, we describe how to declare and inspect placeholders, the variables whose data is provided by users, and category labels, a related variant of placeholders.

Declaring single placeholders#

This section covers placeholder types and how to declare a single placeholder.

Placeholders require a type at declaration time. Because placeholders represent values provided by users at compile time, JijModeling provides several types for representing input data appropriately. Representative placeholder types are:

Type	Mathematical Notation	Description	Alias
`Binary()`	\(\{0, 1\}\)	A binary placeholder taking value \(0\) or \(1\).	-
`Natural()`	\(\mathbb{N}\) or \(\{0, \ldots, N-1\}\)	Natural numbers including zero. Used for array sizes and indices. Specify another natural-valued expression `N` with the `less_than` keyword argument to restrict the range to \(\{0, \ldots, N-1\}\).	`Dim()`, `Length()`
`Integer()`	\(\mathbb{Z}\)	An integer value, including negatives.	-
`Float()`	\(\mathbb{R}\)	A general real-valued floating-point placeholder.	-
Tuples of the above	\(\mathbb{Z} \times \mathbb{R}\)	Fixed-length tuples with per-component types, often used with lists.	-

To declare a placeholder, call the method with the same name as one of the types above on a Problem.

Choosing placeholder types

For simple models, it is usually enough to remember just Natural and Float. Keep the following guidelines in mind:

Use natural numbers for array sizes and item counts, declaring them as Natural or aliases like Dim and Length.
Use Float, or a more specific type when needed, for other numeric values.

As an example, declare the single placeholders needed for a knapsack problem. With the Plain API, this can be written as:

import jijmodeling as jm

knapsack_placeholders = jm.Problem("Knapsack (Placeholders only)", sense=jm.ProblemSense.MAXIMIZE)
W = knapsack_placeholders.Float("W", description="Knapsack capacity")
N = knapsack_placeholders.Length("N", description="Number of items")

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{Number of items}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{Knapsack capacity}\\\end{alignedat}\end{array} \]

Here we define a mathematical model with one real-valued placeholder W for the capacity and one natural-number placeholder N for the number of items. Placeholders declared this way are represented as instances of Placeholder, which stores their metadata.

\[W\in \mathbb{R},\text{Knapsack capacity}\]

\[N\in \mathbb{N},\text{Number of items}\]

When a placeholder appears in an expression, it is automatically treated as an expression that refers to the placeholder value. For example, add \(1\) to W:

W + 1

\[W+1\]

With the Decorator API, when the placeholder name matches the Python variable name, you can omit the name at declaration time.

@jm.Problem.define("Another Problem with Placeholder")
def knapsack_placeholders(problem: jm.DecoratedProblem):
    W = problem.Float(description="Knapsack capacity")
    N = problem.Length(description="Number of items")


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{Number of items}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{Knapsack capacity}\\\end{alignedat}\end{array} \]

When you can omit variable names

In the Decorator API, you can omit a variable name only when the declaration has the form x = problem.Float(...), i.e. one variable on the left and one constructor call on the right. If you declare multiple variables at once, such as x, y = (problem.Float(), problem.Natural()), it will raise an error.

The Placeholder() constructor

The constructors listed above, such as problem.Float and problem.Natural, are special cases of the more general Placeholder() constructor. For example, problem.Natural is implemented as shorthand for problem.Placeholder(dtype=jm.DataType.NATURAL). You can specify the following for dtype:

jm.DataType variants
Python built-in type specifiers such as float and int
NumPy type specifiers such as numpy.uint* and numpy.int* (the bit width after * is simply ignored)
Natural-valued expressions, for specifying the type \(\{0, \ldots, N-1\}\) of natural numbers less than a given natural number N
Category labels
Tuples of the above

For placeholders with more complex types, such as tuples, use the Placeholder constructor to specify the details. Like the specialized constructors, Placeholder also supports name omission in the Decorator API.

Declaring category labels#

As discussed in Variables in JijModeling, a category label is “a set of labels that can be used as dictionary keys, where the concrete candidates are provided at compile time”. Declaring a category label is similar to declaring a placeholder: call CategoryLabel() on the mathematical model to register it. With the Plain API, category labels are declared as follows:

import jijmodeling as jm

problem_catlab_plain = jm.Problem("Category Label Only")
L_plain = problem_catlab_plain.CategoryLabel("L", description="Some category label")

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{Some category label}\end{array} \end{array} \]

As with placeholders, it takes a required name and an optional description keyword argument for a human-readable explanation. With the Decorator API, you can omit the category-label name in the same way as placeholders, although specifying it explicitly is also allowed:

import jijmodeling as jm

@jm.Problem.define("Category Label Only")
def problem_catlab_deco(problem: jm.DecoratedProblem):
    L = problem.CategoryLabel(description="Some category label")

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{Some category label}\end{array} \end{array} \]

The list of category labels registered on a Problem object can be obtained from the category_labels property. You can also obtain an expression for the number of values belonging to an individual category label with jm.count() or the jm.CategoryLabel.count() method. In mathematical notation this is rendered as \(\#L\).

Retrieving placeholder and category-label information#

The list of placeholders registered in a mathematical model can be obtained from the Problem object’s placeholders property. This property returns a dictionary keyed by placeholder name, with the corresponding metadata as values. It also includes information for indexed variables discussed below. Similarly, category labels can be obtained from the Problem object’s category_labels property as a dictionary keyed by category-label name.

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="Some category label")
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': CategoryLabel(name="L")}

The metadata obtained this way is represented by Placeholder objects for placeholders and CategoryLabel objects for category labels, the same objects returned at declaration time. Therefore, objects contained in these dictionaries can also be used as variable expressions. This is especially useful when you update a Problem incrementally with multiple @problem.update or @jm.Problem.define() decorators and need to refer to variables defined in earlier decorator blocks.

Tip

In the future, @problem.update is planned to accept already-defined variables as arguments. Stay tuned.

Declaring indexed placeholders#

This section explains how to declare indexed placeholders. As discussed in Variables in JijModeling, indexed variables can be arrays or dictionaries, so we cover each in turn.

There are no indexed category labels

A category label is a concept for adding a new type that can appear as dictionary keys, and is one abstraction level above a placeholder that specifies a value of a particular type. For this reason, unlike placeholders, there is no such thing as an “indexed category label”.

Arrays of placeholders#

There are two ways to declare arrays of placeholders.

Declaring placeholder arrays with `shape`#

The recommended way to declare a placeholder array is to use the shape keyword argument. The shape keyword argument can take an expression representing a fixed-length tuple of natural numbers. When the dimension is \(1\), it can also be given directly as a natural-valued expression. Here we partially define a knapsack problem that has not only single placeholders such as \(N\) and \(W\), but also one-dimensional arrays v for item values and w for item weights:

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="Knapsack capacity")
    N = problem.Length(description="Number of items")

    # Declare one-dimensional arrays of length N with the shape keyword argument.
    # Because they are one-dimensional, shape=N and shape=(N,) mean the same thing.
    v = problem.Float(description="Value of each item", shape=(N,))
    w = problem.Float(description="Weight of each item", 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{Number of items}\\&&&\\v&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\&&&\text{Value of each item}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{Knapsack capacity}\\&&&\\w&\in \mathop{\mathrm{Array}}\left[N;\mathbb{R}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{R}\\&&&\text{Weight of each item}\\\end{alignedat}\end{array} \]

You may also specify None as a component of the shape of a placeholder array. In that case, the dimension marked with None is still required to have a fixed length, but that length is inferred from the instance data provided at compile time. This is useful when you want to define an array whose shape is only partially constrained, as in the following example:

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

Declaring arrays by dimension only#

Another, less recommended, method uses the ndim keyword argument. By passing a natural-number constant literal as the ndim keyword argument of a placeholder constructor, you can declare a placeholder array whose dimension is specified, while the concrete length of each axis is determined when instance data is provided at compile time.

Specifying shape and ndim together

You can specify ndim and shape together, but in that case the number of components in shape must exactly match the value of ndim.

For example, the knapsack_placeholders defined above can be written using ndim as follows:

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="Knapsack capacity")
    v = problem.Float(ndim=1, description="Value of each item")
    N = v.len_at(0)
    w = problem.Float(shape=N, description="Weight of each item")


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{Value of each item}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{Knapsack capacity}\\&&&\\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{Weight of each item}\\\end{alignedat}\end{array} \]

The len_at() method returns the length of the \(i\)-th axis of the given array. Since \(w\), \(v\), and \(x\) all have the same length in the full knapsack model, we declare \(v\) as a one-dimensional array first and use its length to specify the shape of the remaining arrays.

These two approaches define semantically similar models, but they differ in how instance data is provided. In the first knapsack_placeholders example (definition and update), \(N\) is also declared as a Length placeholder, so when generating an instance, you must provide N as instance data in addition to W, v, and w. In knapsack_placeholders_ndim, where \(N\) is constructed as an expression using len_at instead of as a placeholder, the value of \(N\) is inferred from input v, so at compile time you only need to provide values for W, v, and w.

So when should you introduce a length placeholder, and when should you use ndim + len_at? A good rule of thumb is: if there are dependencies between the lengths of multiple axes in a single array, then you should define a length placeholder.

As an example, consider defining a distance matrix \(d\) of shape \(N \times N\):

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

Here both axes of the two-dimensional array \(d\) must have length \(N\). This constraint cannot be expressed with ndim=2, so you need to define \(N\) and use it in shape.

In the older JijModeling 1 series, placeholders supported only ndim declarations for a long time, so knapsack_placeholders_ndim-style definitions were common:

v = problem.Float(ndim=1, description="Value of each item")
w = problem.Float(ndim=1, description="Weight of each item")

However, this does not express the shape relationship between \(v\) and \(w\). Therefore, in JijModeling 2 and later, such definitions that cannot enforce length consistency are strongly discouraged, and it is strongly recommended to specify shape somewhere whenever there is a non-trivial relationship between shapes.

Graphs as arrays of tuples

For example, when V is a natural-valued expression representing the number of vertices, G = problem.Graph(dtype=V) declares a placeholder corresponding to the edge set of a graph with vertex set \(\{0, \ldots, V-1\}\). This constructor is actually equivalent to a one-dimensional array of tuples, as described in “Single placeholders”, and can be written as:

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

Therefore, you can obtain the number of edges, counting multiplicities, via N = G.len_at(0), and you can use array operations to work with graphs. Dictionaries, described below, can also represent graphs with edge labels. In this way, JijModeling lets you represent complex structures by combining tuples and arrays.

Since 2.0.0: Jagged Array is strongly discouraged

In JijModeling 1, a Jagged Array collection was available for non-uniform shapes. However, due to that non-uniformity, Jagged Arrays are difficult to validate with type systems and similar checks. In JijModeling 2, Jagged Array is strongly discouraged and planned to be removed in a future release. You can express graph structures, non-zero-based indices, and sparse structures using combinations of arrays, tuples, and dictionaries, so we strongly recommend migrating away from Jagged Array.

Dictionaries of placeholders#

Placeholder dictionaries are declared by passing the dict_keys keyword argument, instead of shape, to constructors such as Float and Length. To align with decision-variable behavior, if only dict_keys is specified, the placeholder dictionary is declared as a TotalDict. If you also pass partial_dict=True, it is declared as a PartialDict.

When declared as a TotalDict, meaning partial_dict is omitted or False, dict_keys can be:

A natural-valued expression \(n\) without decision variables
A Python list of strings
A category label defined by problem.CategoryLabel
A tuple composed of (1) to (3)

When declared as a PartialDict, the following can be specified:

jm.DataType.INTEGER, the Python type identifier int, or numpy.int*, meaning an integer type
jm.DataType.NATURAL or numpy.uint*
A natural-valued expression \(n\) without decision variables, identified with the set \(\mathbb{N}_{<n} = \{0, \ldots, n - 1\}\)
The Python type identifier str
A Python list of strings
A category label defined by problem.CategoryLabel
A tuple composed of (1) to (6)

You can also declare placeholder dictionaries by calling the TotalDict() constructor or PartialDict() constructor on the Problem object.

Why there is no ndim-like option for placeholder dictionaries

There is no argument corresponding to ndim for placeholder arrays. If only the number of components were provided while omitting the key type, the concrete key type could not be determined without accessing instance data.

The following example declares each item in the knapsack problem as a category label rather than a natural number, and declares the item values and weights as dictionaries over that label:

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="Knapsack capacity")
    L = problem.CategoryLabel(description="Item category label")
    v = problem.Float(description="Value of each item", dict_keys=L)
    w = problem.Float(description="Weight of each item", 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{Value of each item}\\&&&\\W&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\&&&\text{Knapsack capacity}\\&&&\\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{Weight of each item}\\\end{alignedat}\\&\\&\text{Category Labels:}\\&\qquad \begin{array}{rl} L&\text{Item category label}\end{array} \end{array} \]