List and set variables¶

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 Hexaly Modeler, and with the method getCollectionValue() in Hexaly Optimizer APIs. It returns an object of type HxCollection, that can be read and modified through the methods: count, get, clear, add.

Modifying this HxCollection 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¶

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

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));

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

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

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

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 fails 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.