Lambda Expressions

Hexaly Optimizer 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 lambda 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]);

# with x a list or a set
total = model.sum(x, model.lambda_function(lambda i: quantity[i]))

// with x a list or a set
HxExpression total = model.sum(x,
        model.createLambdaFunction([&](HxExpression i) { return quantity[i]; }));

// with x a list or a set
HxExpression total = model.Sum(x, model.LambdaFunction(i => quantity[i]));

// with x a list or a set
HxExpression total = model.sum(x,
        model.lambdaFunction(i -> model.at(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 lambda function that should be applied to each element in the range.

In addition to lists and sets, it is possible to use an interval decision variable or 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), i => quantity[x[i]]);

total = model.sum(
        model.range(0, model.count(x)),
        model.lambda_function(lambda i: quantity[x[i]]))

HxExpression total = model.sum(
        model.range(0, model.count(x)),
        model.createLambdaFunction([&](HxExpression i) { return quantity[x[i]]; }));

HxExpression total = model.Sum(
        model.Range(0, model.Count(x)),
        model.LambdaFunction(i => quantity[x[i]]));

HxExpression total = model.sum(
        model.range(0, model.count(x)),
        model.lambdaFunction(i -> model.at(quantity, model.at(x, i))));

We will describe the properties of a range and how a lambda 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 code templates illustrate this feature (including the classical CVRP).

Ranges

A range is a collection of consecutive integers.

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 than a:

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

objective = model.max(model.range(a, b), model.lambda_function(lambda i: v[i + 1] * z))
model.minimize(objective)

HxExpression objective = model.max(model.range(a, b),
        model.createLambdaFunction([&](HxExpression i) { return v[i + 1] * z; }));
model.minimize(objective);

HxExpression objective = model.Max(model.Range(a, b),
        model.LambdaFunction(i => v[i + 1] * z));
model.Minimize(objective);

HxExpression objective = model.max(model.range(a, b),
        model.lambdaFunction(i -> model.prod(model.at(v, model.sum(i, 1)), z)));
model.minimize(objective);

Lambda functions

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

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

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

Applying a lambda function to an iterable

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

  • op is some n-ary operator among: sum, prod, min, max, and, or, xor, array, intersection, hull, or some binary operator among distinct and sort.
  • iterable is an iterable with integer values such as a range, a collection or an interval.
  • function is a lambda function with exactly one argument, except for the array operator which accepts one or two operands (see below).

The value of such a op(iterable, function) expression can be computed as follows. For each integer i within iterable, 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 [a,b).

A typical usage of this feature can be found in our Traveling Salesman Problem (TSP) code template, where the sum of distances along the circuit is computed as follows:

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

distance_lambda = model.lambda_function(
        lambda i: distance[cities[i]][cities[i + 1]])
obj = model.sum(
        model.range(0, nb_cities - 1),
        distance_lambda) + distance[cities[nb_cities - 1]][cities[0]]

HxExpression distanceLambda = model.createLambdaFunction([&](HxExpression i) {
    return distance[cities[i]][cities[i + 1]];
});
HxExpression obj = model.sum(
        model.range(0, nbCities - 1),
        distanceLambda) + distance[cities[nbCities - 1]][cities[0]];

HxExpression distanceLambda = model.LambdaFunction(
        i => model.At(distance, cities[i], cities[i + 1]));
HxExpression obj = model.Sum(
        model.Range(0, nbCities - 1),
        distanceLambda) + model.At(distance, cities[nbCities - 1], cities[0]);

HxExpression distanceLambda = model.lambdaFunction(i ->
        model.at(distance, model.at(cities, i), model.at(cities, model.sum(i, 1))));
HxExpression obj = model.sum(
        model.sum(model.range(0, nbCities - 1), distanceLambda),
        model.at(distance, model.at(cities, nbCities - 1), model.at(cities, 0)));

In the Bin Packing Problem (BPP) code template, a similar syntax allows to sum the weights of items in a bin, which is defined as a set:

bin <- set(nbItems);
binWeight <- sum(bin, i => itemWeights[i]);

bin = model.set(nb_items)
bin_weight = model.sum(bin, model.lambda_function(lambda i: item_weights[i]))

HxExpression bin = model.setVar(nbItems);
HxExpression binWeight = model.sum(bin,
        model.createLambdaFunction([&](HxExpression i) { return itemWeights[i]; }));

HxExpression bin = model.Set(nbItems);
HxExpression binWeight = model.Sum(bin, model.LambdaFunction(i => itemWeights[i]));

HxExpression bin = model.setVar(nbItems);
HxExpression binWeight = model.sum(bin,
        model.lambdaFunction(i -> model.at(itemWeights, i)));

Finally, one can also iterate over an interval, resulting in the enumeration of the successive integers between its start (inclusive) and its end (exclusive). The Job Shop Problem with Intensity uses this feature to compute the number of active time steps over the duration of a task:

task <- interval(0, timeHorizon);
constraint sum(task, t => intensity[t]) >= processingTime;

task = model.interval(0, time_horizon)
model.constraint(
        model.sum(task, model.lambda_function(lambda t: intensity[t])) >= processing_time)

HxExpression task = model.intervalVar(0, timeHorizon);
model.constraint(model.sum(task,
        model.createLambdaFunction([&](HxExpression t) { return intensity[t]; }))
        >= processingTime);

HxExpression task = model.Interval(0, timeHorizon);
model.Constraint(model.Sum(task, model.LambdaFunction(t => intensity[t]))
        >= processingTime);

HxExpression task = model.intervalVar(0, timeHorizon);
model.constraint(model.geq(
        model.sum(task, model.lambdaFunction(t -> model.at(intensity, t))),
        processingTime));

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), c), we will have v[i] = f(i,v[i-1]) for all i in interval [a,b), with v[a-1] equal to c.

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 of early arrival. More precisely, 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]];
}

def departure_time(route, i, prev):
    arrival_time = model.iif(
            i == 0,
            opening_hour[route[i]],
            model.max(opening_hour[route[i]], prev + distance_matrix[route[i - 1]][route[i]]))
    return arrival_time + service_time[route[i]]

HxExpression departureTime(
    HxModel& model, HxExpression route, HxExpression i, HxExpression prev,
    HxExpression openingHour, HxExpression serviceTime, HxExpression distanceMatrix) {
    HxExpression arrivalTime = model.iif(
            i == 0,
            openingHour[route[i]],
            model.max(openingHour[route[i]], prev + distanceMatrix[route[i - 1]][route[i]]));
    return arrivalTime + serviceTime[route[i]];
}

HxExpression DepartureTime(
    HxModel model, HxExpression route, HxExpression i, HxExpression prev,
    HxExpression openingHour, HxExpression serviceTime, HxExpression distanceMatrix)
{
    HxExpression arrivalTime = model.If(
            i == 0,
            openingHour[route[i]],
            model.Max(
                    openingHour[route[i]],
                    prev + model.At(distanceMatrix, route[i - 1], route[i])));
    return arrivalTime + serviceTime[route[i]];
}

HxExpression departureTime(
    HxModel model, HxExpression route, HxExpression i, HxExpression prev,
    HxExpression openingHour, HxExpression serviceTime, HxExpression distanceMatrix) {
    HxExpression currentLocation = model.at(route, i);
    HxExpression previousLocation = model.at(route, model.sub(i, 1));
    HxExpression arrivalTime = model.iif(
            model.eq(i, 0),
            model.at(openingHour, currentLocation),
            model.max(
                    model.at(openingHour, currentLocation),
                    model.sum(prev, model.at(distanceMatrix, previousLocation, currentLocation))));
    return model.sum(arrivalTime, model.at(serviceTime, currentLocation));
}

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

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

times = model.array(
        model.range(0, model.count(route)),
        model.lambda_function(lambda i, prev: departure_time(route, i, prev)),
        0)

HxExpression times = model.array(
    model.range(0, model.count(route)),
    model.createLambdaFunction(
        [&](HxExpression i, HxExpression prev) {
            return departureTime(
                model, route, i, prev, openingHour, serviceTime, distanceMatrix);
        }),
    0);

HxExpression times = model.Array(
    model.Range(0, model.Count(route)),
    model.LambdaFunction((i, prev) => DepartureTime(
            model, route, i, prev, openingHour, serviceTime, distanceMatrix)),
    0);

HxExpression times = model.array(
    model.range(0, model.count(route)),
    model.lambdaFunction((i, prev) -> departureTime(
        model, route, i, prev, openingHour, serviceTime, distanceMatrix)),
    0);

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

Then, if we also consider closing hours at each location (the truck must have left location L before closingHour[L]), we can add the corresponding constraint by applying the and operator to the same range:

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

model.constraint(model.and_(
        model.range(0, model.count(route)),
        model.lambda_function(lambda i: times[i] <= closing_hour[route[i]])))

model.constraint(model.and_(
        model.range(0, model.count(route)),
        model.createLambdaFunction(
                [&](HxExpression i) { return times[i] <= closingHour[route[i]]; })));

model.Constraint(model.And(
        model.Range(0, model.Count(route)),
        model.LambdaFunction(i => times[i] <= closingHour[route[i]])));

model.constraint(model.and(
        model.range(0, model.count(route)),
        model.lambdaFunction(i ->
                model.leq(model.at(times, i), model.at(closingHour, model.at(route, i))))));