This page is for an old version of Hexaly Optimizer. We recommend that you update your version and read the documentation for the latest stable release.

List and set variables

In addition to boolean, integers and floats, Hexaly Optimizer offers two higher level decision variable: lists and sets.

Creation operator

The list and the set operator allows defining a decision variable whose value is a collection of integers within a domain [0, n-1] where n is the unique operand of the operator. They do not necessarily contain all the values in [0, n-1] and all the values in a list or set will be pairwise different, non negative and strictly smaller that n. Note that the operand must be a constant, strictly positive integer.

For instance the following line creates a list decision variable of domain size 10:

x <- list(10);

The difference between a list and a set is that the list maintains an order on its elements. Mathematically, a list is a permutation of a subset of [0, n-1], and a set is a subset of [0, n-1].

Setting and retrieving values

As mentioned above, the value of a list or a set is a collection of integers. This value is obtained with the syntax x.value in the LSP language, and with the method getCollectionValue() in Hexaly Optimizer’s APIs. It returns an object of type LSCollection, that can be read and modified through the methods: count, get, clear, add.

Modifying this LSCollection object modifies the value of the corresponding list or set variable. The code below illustrates the use of these methods:

println(x.value.count()); // Current size of the collection
x.value.clear(); // empty the list
x.value.add(3); // add a value, throw an error if this value in not in interval [0,9], if x was defined as list(10)
x.value.add(5); // add a value, throw an error if this value is already included in the list
for[e in x.value] println(e); // print the content of the list
println(x.value); // print the content of the list, ``[3, 5]`` in this case

Operators on lists and sets

Unary and binary operators

The count operator returns the number of elements in a collection. For example, the following model merely expresses the search for a set of maximum size:

x <- set(5);
maximize count(x);

The contains operator expresses that an element is present in a collection. For example, the following model defines a knapsack problem using a set:

knapsack <- set(n);
constraint sum[i in 0...n](weight[i] * contains(knapsack, i)) <= capacity;
maximize sum[i in 0...n](value[i] * contains(knapsack, i));

The distinct operator takes as input a collection and a lambda function, and returns the unordered set of distinct values among all the values returned by the function. For example, the following constraint forces a machine to produce at most two distinct types of product:

machine <- list(10);
productTypes = { 0, 1, 2, 1, 2, 0, 0, 1, 2, 1 };
constraint count(distinct(machine, i => productTypes[i])) <= 2;

The ìntersection operator takes two operands which can both be collection or array. It returns the unordered set of the values present in both operands. For example the following constraint prevents the set from having the value 0, 1 or 2:

forbiddenValues <- array(0, 1, 2);
numbers <- set(10);
constraint count(intersection(numbers, forbiddenValues)) == 0;

N-ary operators

The disjoint operator applies to N lists or N sets sharing the same domain. It takes value 1 when all collections are pairwise disjoint (that is to say that no value appears in more than one collection), and value 0 otherwise. It takes at least one operand. In the following example we try to maximize the minimum size among three lists. Since they are constrained to be disjoint this maximum will be 3:

x <- list(10);
y <- list(10);
z <- list(10);
constraint disjoint(x, y, z);
maximize min(count(x), count(y), count(z));

The cover operator applies to N lists or N sets sharing the same domain. It takes value 1 when the given collections form a cover of the set [0, n-1], and value 0 otherwise. It takes at least one operand. cover(xcolls) is equivalent to sum[i in 0...count(xcolls)](contains(xcolls[i], j))) >= 1 for j in [0, n-1].

The partition operator applies to N lists or N sets sharing the same domain. It takes value 1 when the given collections form a partition of the set [0, n-1], and value 0 otherwise. It takes at least one operand. In other words, partition(xcolls) is equivalent to disjoint(xcolls) && sum[i in 0...count(xcolls)](count(xcolls[i])) == n.

These operators are particularly useful when items are to be assigned to one of several groups or containers. Each group will be represented by its own collection. For instance, the items may be tasks to be dispatched to one of several machines, or delivery locations to be serviced by one of several trucks.

Operators specific to lists

The at operator allows accessing the value at a given position in the list. It takes two operands: a list and an integer expression (not necessarily constant). It returns -1 when the given index is negative or larger or equal to count(x).

For example, the objective function in the following model is to maximize the product of the first and last items in the list:

x <- list(5);
constraint count(x) > 0;
maximize x[0] * x[count(x)-1];

The indexOf operator returns the position of a given integer in the list or -1 if this integer is not included in the list. It takes two operands: a list and an integer expression (not necessarily constant). For example, given a matrix c of size n, the linear ordering problem consists in finding a permutation of [0, n-1] of minimum cost, where a cost c[i][j] is paid when j is before i in the ordering. Here is the corresponding model:

x <- list(n);
constraint count(x) == n;
minimize sum[i in 0...n][j in 0...n](c[i][j] * (indexOf(x,i) > indexOf(x,j)));

Modeling with lists

In the context of routing problems, list variables can be used to model a variety of problems. A pure Traveling Salesman Problem (TSP) is modeled with a single list x with a constraint count(x)==n in order to specify that all cities must be visited. This constraint would be omitted for a Prize Collecting TSP, where a penalty is paid for cities not in the tour.

A vehicle routing problem (VRP) will be modeled with k lists if k is the number of trucks. For a classical VRP these lists will be constrained to form a partition (operator partition), whereas for a Prize-Collecting VRP only their disjointness will be required (operator disjoint). For a Split Delivery VRP the lists form a cover (operator cover).

Distances can be either given as a matrix and accessed with the at operator or explicitly computed (with operators pow and srqt for Euclidian distances for instance).

Detailed routing and scheduling examples are available in our example tour.

Modeling with sets

Sets can be used as a compact way to model group membership in a variety of problems. A bin packing problem will be modeled with k sets if k is the number of bins. These sets will be constrained to form a partition (operator partition).

While lists are unique in their capacity to model ordering constraints, set variables may be replaced by an equivalent boolean model. Set variables should be preferred if the problem involves assigning an item to one of several similar groups or containers. This is modeled naturally with the disjoint, partition or cover operator.

On the other hand, there are cases where a boolean model may perform better. This can happen when there is a single set (for example a knapsack problem), or they are all independent i.e. the sets don’t bring any additional structure to the model. Similarly, if many constraints need to be added on the items, for example with the contains operator, there tends to be less benefit in using sets over boolean variables, since the model will not be more compact.

Detailed packing examples using set variables are available in our example tour.