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 domain
[0, n-1] where n is the unique
operand of this operator. Mathematically a list is a permutation of a subset
[0, n-1]: it does not necessarily contains all the values in
and all values in a 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 domain size 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.
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¶
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);
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 * x[count(x)-1];
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-1][j in 0..n-1](c[i][j] * (indexOf(x,i) > indexOf(x,j)));
disjoint operator applies to N lists sharing the same domain. 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 be 3:
x <- list(10); y <- list(10); z <- list(10); constraint disjoint(x, y, z); maximize min(count(x), count(y), count(z));
partition operator applies to N lists sharing the same domain. 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, list variables can be used to model a
variety of problems. A pure Traveling Salesman Problem (TSP) is modeled with a
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), whereas for a Prize-Collecting VRP only
their disjointness will be required (operator
Distances can be either given as a matrix and accessed with the
or explicitly computed (with operators
srqt for Euclidian
distances for instance).
Detailed routing examples are available in our example tour.