List variables¶

In addition to boolean, integers and floats, LocalSolver offers a higher level decision variable: lists.

The list operator¶

The list operator allows defining a decision variable whose value is a collection of integers within a range [0, n-1] where n is the unique operand of this operator. Mathematically a list is a permutation of a subset of [0,n-1]. All values in the list will be pairwise different, non negative and strictly smaller that n. Note that the unique operand of this operator must be a constant strictly positive integer.

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

x <- list(10);

The value of this list is obtained with the syntax x.value in the LSP language, and with the method getCollectionValue() in LocalSolver’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 variable. The code below illustrates the use of these methods:

println(x.value.count()); // Current size of the list
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¶

Unary and binary operators¶

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

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

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 is 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-1][j in 0..n-1](c[i][j] * (indexOf(x,i) > indexOf(x,j));

N-ary operators¶

The disjoint operator applies to N lists sharing the same range. It takes value 1 when all lists are pairwise disjoint (that is to say that no value appears in more than one list), 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 the 3:

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

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

These operators are particularly useful when tasks have to be dispatched to different machines, or locations have to be dispatched to different trucks for instance.

Application to routing problems¶

In the context of routing problems, lists 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).

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 examples are available in our example tour.