2.5. Tuple and record types

In MiniZinc models we often deal with multiple points of data and multiple decisions that all concern the same thing, an “object”. There are multiple ways to modelling this. It is common practice in MiniZinc to have different arrays for different types of data points or decisions. These arrays will then share a common index mapping to which object each data point belongs.

In this section we present an alternative, “object-oriented”, approach in MiniZinc in the form of tuple and record types. Using these types, different types of data points and decisions can be combined into collections for the modeller’s convenience.

2.5.1. Declaring and using tuples and records

Tuple types and literals

A tuple type variable is declared as:

<var-par> tuple(<ti-expr>, ...): <var-name>

where one or more type instantiations, <ti-expr>, are placed between the parentheses to declare the types contained in the tuple variable.

For convenience the var keyword can be used to varify all the member types of the tuple (i.e., var tuple(int, bool) is the same type as tuple(var int, var bool)).

A tuple literal is created using the following syntax:

(<expr>, [ <expr>, ... ])

For example, (1, true) is a tuple literal of type tuple(int, bool). Note that when a tuple contains multiple members, then adding a trailing comma is optional, but when it contains a single member it is required to distinguish the literal from a normal parenthesized expression.

Tuples provide a very simple way to create a collection that contains values of different types. In a tuple variable, the values contained in the tuple can be accessed using a number representing the place in the tuple. For example, in the tuple any: x = (1, true, 2.0) the first member, 1, can be retrieved using x.1, and the final member, 2.0, can be retrieved using x.3. Note that the MiniZinc compiler will raise a Type Error, when an integer is used that is lower than one or higher than the number of members in the tuple.

Although tuple types can be useful, it can often be confusing which member represents what. Record types improve on this by associating a name with each member of the type.

Record types and literals

A record type variable is declared as:

<var-par> record(<ti-expr-and-id>, ...): <var-name>

where one or more type instantiations with a corresponding identifier, <ti-expr-and-id>, are placed between the parentheses to declare the types contained in the record variable.

For convenience the var keyword can be used to varify all the member types of the record (i.e., var record(int: i, bool: b) is the same type as record(var int: i, var bool: b)).

A record literal is created using the following syntax:

(<ident>: <expr>[, ... ])

For example, (i: 1, b: true) is a record literal of type record(int: i, bool: b). Different from tuples, record literals with only a single member do not require a trailing comma.

The syntax for accessing a member of a record is very similar to accessing a member of a tuple. The difference is that instead of a number, we use the name given to the member. For example, given the record any: x = (i: 1, b: true), the integer value 1 that is named by identifier i is retrieved using x.i. Using identifiers that do not name a member (or any number) will once more result in a Type Error.

2.5.2. Using type-inst synonyms

When using records and tuples, writing the types in many places can quickly become tedious and confusing. Additionally, it might often make sense to give a name to such a type-inst to describe its meaning. For this purpose, you can use type-inst synonyms in MiniZinc.

Type-inst synonyms

A type-inst synonym is declared as:

type <ident> <annotations> = <ti-expr>;

where the identifier <ident> can be used instead of the type-inst <ti-expr> where required.

For example, in the following MiniZinc fragment we declare two synonyms, Coord and Number

type Coord = var record(int: x, int: y, int: z);
type Number = int;

In a model that contains these definitions, we can now declare a variable array[1..10] of Coord: placement; or a function function Number: add(Number: x, Number: y) = x + y;

Similar to record and tuple types, the var keyword can be used before the identifier of a type-inst synonym to varify the type-inst. For instance, given the synonym type OnOff = bool; and the variable declaration var OnOff: choice;, the type-inst of choice would be var bool. Different from records and tuple, the reverse is also possible using the par keyword. For instance, the given the synonym type Choice = var bool; and the variable declaration par Choice: check = fix(choice); the type-inst of check would be bool.

2.5.3. Types with both var and par members

Tuples and records can be used to collect both data and decisions about an object, and it can be natural to mix data and decisions that concern the same object. However, when data and decisions are contained within the same tuple or record type, initialization of these types can be complex. To avoid the usage of anonymous variables or let-expressions and allow the assignment from data files, it is recommended to split data and decisions into separate types.

For example, in a rostering problem it would be natural to combine information about the employees, both data and decisions. It might thus be natural to define the following synonyms and variable declarations.

enum EmpId;
type Employee = record(
  string: name,
  array[Timespan] of bool: available,
  set of Capability: capacities,
  array[Timespan] of var Shift: shifts,
  var 0..infinity: hours,
);

array[EmpId] of Employee: employee;

However, it is not possible to assign employees from a data file. Instead, the data and the data could be split as follows.

enum EmpId;
type EmployeeData = record(
  string: name,
  array[Timespan] of bool: available,
  set of Capability: capacities,
);
type EmployeeVar = record(
  array[Timespan] of var Shift: shifts,
  var 0..infinity: hours,
);

array[EmpId] of EmployeeData: employee_data;
array[EmpId] of EmployeeVar: employee_var;

Now it is possible to initialize employee_data from a data file. Depending on the model, it might be easiest to use these synonyms and variable declarations separately, but it might be useful to combine them again. For instance, when your model contains functions that should operate on the complete record. The ++ operator can be used to easily combine these synonyms and values, as shown in the following fragment.

type Employee = EmployeeData ++ EmployeeVar;

array[EmpId] of Employee: employee = [employee_data[id] ++ employee_var[id] | id in EmpId];

++ operator for tuples and records

The ++ operator can be used to combine expressions and type-inst expressions that both have tuple types or both have record types.

<expr> ++ <expr>
<ti-expr> ++ <ti-expr>

When both (type-inst) expressions have a tuple type, this operation is very similar to array concatenation. The result of evaluating the expression will be a new tuple that contains all members of left-hand side followed by all the members of the right-hand side.

When both (type-inst) expressions have a record type, then the result of evaluating the expression is a record that merges the fields in both records. Note that if both records contain a field with the same name, then the compiler will reject this as a Type Error.

2.5.4. Example: rectangle packing using records

Consider a packing problem where a collection of rectangular objects have to be packed into a rectangular space. Importantly, none of the rectangles being packed can overlap. To keep the model simple, we don’t allow the rectangles to be turned. When we create a model to decide whether the packing is possible, we can use records to help us make the model easier to read.

The data for the model comes in two parts: the total area of the space and the sizes of the rectangles being packed. We can represent both using a “dimensions” record that includes the width and the height of a rectangle. We therefore define the following type-inst synonym.

type Dimensions = record(int: width, int: height);

To decide whether the problem is satisfiable or not, we will have to find a placement for the rectangles being packed. We can thus use the coordinates of their left bottom corner as our decision variables, for which a type-inst synonym can be defined as follows.

type Coordinates = record(var 0..infinity: x, var 0..infinity: y);

To enforce that no rectangles overlap, it can be easy to start by writing a predicate that ensures that two rectangles do not overlap. This predicate will require both the information about the dimensions of the rectangle and the coordinate decision variable. As such, it can be valuable to first combine these records into a new record type. The following fragment shows the additional type-inst synonym, and a definition for the described predicate.

type Rectangle = Dimensions ++ Coordinates;

% No overlap predicate
predicate no_overlap(Rectangle: rectA, Rectangle: rectB) = 
  rectA.x + rectA.width <= rectB.x
  \/ rectB.x + rectB.width <= rectA.x
  \/ rectA.y + rectA.height <= rectB.y
  \/ rectB.y + rectB.height <= rectA.y;

Using these definitions the remainder of the model is now easy to define as shown below.

Listing 2.5.1 Partial rectangle packing model using record types (full model: rect_packing.mzn example data: rect_packing.json).
% Instance data
array[_] of Dimensions: rectDim;
Dimensions: area;

% Decision variables
array[index_set(rectDim)] of Coordinates: rectCoord ::no_output;

array[_] of Rectangle: rectangles ::output = [ rectDim[i] ++ rectCoord[i] | i in index_set(rectDim)];

% Constraint: rectangles must be placed within the area
constraint forall(rect in rectangles) (
  rect.x + rect.width <= area.width
  /\ rect.y + rect.height <= area.height
);

% Constraint: no rectangles can overlap
constraint forall(i, j in index_set(rectangles) where i < j) (
  no_overlap(rectangles[i], rectangles[j])
);