List and set variables¶
In addition to boolean, integers and floats, LocalSolver offers two higher level decision variable: lists and sets.
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
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
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 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 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¶
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);
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-1](weight[i] * contains(knapsack, i)) <= capacity; maximize sum[i in 0..n-1](value[i] * contains(knapsack, i));
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));
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)-1](contains(xcolls[i], j))) >= 1 for j in [0, n-1].
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)-1](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¶
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)));
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
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
disjoint). For a Split Delivery
VRP the lists form a cover (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 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
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
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
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.