Lambda expressions¶

LocalSolver offers the possibility to apply n-ary operators (like sum, min, max and so on) to a range of dynamic size. For instance it allows defining a sum whose number of terms will depend on other expressions. In such an expression, the iterated term is introduced as a function. A typical usage is for defining a sum over items of a collection:

// with x a list or a set
total <- sum(x, i => quantity[i]);

In the above example, sum has two operands:

The first operand is the collection.
The second operand is a lambda expression defining the function that should be applied to each element in the range.

In addition to lists and sets, it is possible to use a range of integers defined by its extremities. For example, if x is a list, the above construct is equivalent to:

total <- sum(0..count(x)-1, i => quantity[x[i]]);

We will describe the properties of a range and how a function can be introduced. Then we will detail which operators can benefit from this feature, including the special case of the array operator.

Several examples of our our example tour illustrate this feature (including the classical CVRP).

Ranges¶

A range is a collection of consecutive integers.

Note

In the LSP modeling language, the .. operator defines a closed range. That is to say that both extremities are included in the interval: a..b refers to the sequence of integers from a to b. On the contrary, when calling LocalSolver from its APIs, range(a,b) refers to the sequence of integers from a to b-1.

Both extremities of the range can be non-constant expressions. Note that some n-ary operators (like min and max) will be considered as undefined when the range is empty, that is to say that the solution will remain infeasible while the range is empty. For instance, the following expression implicitly constrains b to be larger or equal to a:

minimize max(a..b, i => v[i+1] * z);

Functions¶

A function is a particular LocalSolver expression composed of two parts, arguments => body:

The arguments of the function, which are also LS expressions, automatically and implicitely created when you use the arguments => body construct.
The body of the function. The body is an LS expression that will be used to evaluate the result of the function. The body can be any LS expression composed of any operands and operators supported by LocalSolver.

Note that these functions are explicitly defined with a combination of LocalSolver operators and should not be confused with Native functions.

Applying a function to a range¶

Applying a function to a range or a collection is achieved with the syntax op(range,function) where:

op is some n-ary operator among: sum, prod, min, max, and, or, xor, array.
range is a range of integers
function is a function with exactly one argument, except for the array operator which accepts one or two operands (see below).

The value of such a op(range,function) expression can be computed as follows. For each integer i within range, function(i) is evaluated; and all these numbers are agregated with the operator op. If we define v <- sum(a..b, i => f(i)), then v will be equal to the sum of all f(i) for i in interval [a,b].

A typical usage of this feature can be found in our TSP example, where the sum of distances along the circuit is computed as follows:

obj <- sum(0..nbCities-2, i => distanceWeight[cities[i]][cities[i+1]])
       + distanceWeight[cities[nbCities-1]][cities[0]];

Special case¶

When the array operator is used in this context, it creates an array whose size will vary with the size of the associated range. We allow a recursive definition of elements of this array by using a second argument in the function, containing the evaluation of the function on the previous element of the range.

Formally, if we define v <- array(a..b, (i,prev) => f(i,prev)), we will have v[i] = f(i,v[i-1]) for all i in interval [a,b], with v[-1] equal to 0 by convention.

The use of this feature can be illustrated on a routing problem with time-windows. Having opening hours on each location visited by a truck, we have to take into account the possible waiting time of the truck in case or early arrival. In fact the resulting time will be the maximum between the earliest arrival time (based on the driving time from the previous location) and the opening hour. Taking into account a service time on each location we have:

function departureTime(route, i, prev) {
   arrivalTime <- (i==0) ?
       openingHour[route[i]] :
       max(openingHour[route[i]], prev + distance(route[i-1],route[i]));
   return arrivalTime + serviceTime[route[i]];
}

And the array of all departure times can be defined recursively as:

times <- array(0..count(route)-1, (i, prev) => departureTime(route, i, prev));

Althoug we have used a function of the modeling language to obtain a more readable model it is important to note that departureTime merely returns an expression made of LocalSolver operators.

Now what if we also have closing hours at each location that is to say that the truck must have left location L before closingHour[L]? Such a constraint can be added applying operator and to the same range:

constraint and(0..count(route)-1, i => times[i] <= closingHour[route[i]]);