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>, ... ])
(1, true) is a tuple literal of type
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
any: x = (1, true, 2.0) the first member,
1, can be
x.1, and the final member,
2.0, can be retrieved
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
record(var int: i, var bool: b)).
A record literal is created using the following syntax:
(<ident>: <expr>[, ... ])
(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
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.
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,
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
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
type OnOff = bool; and the variable declaration
var OnOff: choice;, the type-inst of
choice would be
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
check would be
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 decisions 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
++ 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.
% 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]) );