Set and List Variables

In addition to Boolean, integers and floats, Hexaly Optimizer offers higher-level decision variables: lists and sets, presented here, and interval variables.

Mathematical principle and creation operator

The set and list operators define a decision variable whose value is a collection of integers within domain [0, n-1], where n is the unique operand of the operator. They do not necessarily contain all the elements in [0, n-1]. The elements in a list or set are pairwise different, non negative and strictly smaller than n. Note that the operand must be a constant, strictly positive integer.

Set decisions

Mathematically, a set decision variable of domain size n represents a subset of {0, ..., n-1}. It is a set in the usual mathematical sense: each element is unique in the set, and the elements inside a set are unordered.

For instance, the following line creates a set decision variable of domain size 5:

x <- set(5);

x = model.set(5)

HxExpression x = model.setVar(5);

HxExpression x = model.Set(5);

HxExpression x = model.setVar(5);

Based on this definition, the following examples represent valid values for a set decision variable of domain size 5:

{}              // Empty set
{2, 3}          // Equivalent to {3, 2}
{4, 2, 0, 1, 3} // Full set, equivalent to {0, 1, 2, 3, 4}

On the contrary, the following examples are invalid values:

{5}             // Out of bounds for a set decision of domain size 5
{1, 2, 3, 1}    // Repetition of element 1, which is impossible since each element is unique

List decisions

Mathematically, a list decision variable of domain size n represents a subpermutation of {0, ..., n-1}. As for sets, each element is unique in a list. The difference between sets and lists is that elements inside a list are ordered.

For instance, the following line creates a list decision variable of domain size 5:

x <- list(5);

x = model.list(5)

HxExpression x = model.listVar(5);

HxExpression x = model.List(5);

HxExpression x = model.listVar(5);

Based on this definition, the following examples represent valid values for a list decision variable of domain size 5:

[]              // Empty list
[2, 3]          // Different from [3, 2], which is also valid
[4, 2, 0, 1, 3] // Full list

On the contrary, the following examples are invalid values:

[5]             // Out of bounds for a list decision of domain size 5
[1, 2, 3, 1]    // Repetition of element 1, which is impossible since each element is unique

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 Hexaly Modeler, with x.get_value() in Python, with getCollectionValue() in C++ and Java, and with GetCollectionValue() in C#. It returns an object of type HxCollection, that can be read and modified through the methods: count, get, clear, add.

Modifying this HxCollection 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,4], if x was defined as list(5)
x.value.add(1);                 // 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, 1]`` in this case)

collection = x.get_value()
print(collection.count())       # Current size of the collection
collection.clear()              # Empty the list
collection.add(3)               # Add a value, throw an error if this value in not in interval [0,4], if x was defined as list(5)
collection.add(1)               # Add a value, throw an error if this value is already included in the list
for e in collection:
    print(e)                    # Print the content of the list
print(collection)               # Print the content of the list (``[3, 1]`` in this case)

HxCollection collection = x.getCollectionValue();
std::cout << collection.count() << std::endl;  // Current size of the collection
collection.clear();                            // Empty the list
collection.add(3);                             // Add a value, throw an error if this value in not in interval [0,4], if x was defined as list(5)
collection.add(1);                             // Add a value, throw an error if this value is already included in the list
for (int i = 0; i < collection.count(); ++i)
    std::cout << collection.get(i) << std::endl; // Print the content of the list

HxCollection collection = x.GetCollectionValue();
Console.WriteLine(collection.Count());     // Current size of the collection
collection.Clear();                        // Empty the list
collection.Add(3);                         // Add a value, throw an error if this value in not in interval [0,4], if x was defined as list(5)
collection.Add(1);                         // Add a value, throw an error if this value is already included in the list
foreach (long e in collection)
    Console.WriteLine(e);                  // Print the content of the list

HxCollection collection = x.getCollectionValue();
System.out.println(collection.count());    // Current size of the collection
collection.clear();                        // Empty the list
collection.add(3);                         // Add a value, throw an error if this value in not in interval [0,4], if x was defined as list(5)
collection.add(1);                         // Add a value, throw an error if this value is already included in the list
for (int i = 0; i < collection.count(); ++i)
    System.out.println(collection.get(i)); // Print the content of the list

Operators on lists and sets

Unary and binary operators

The 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);

x = model.set(5)
model.maximize(model.count(x))

HxExpression x = model.setVar(5);
model.maximize(model.count(x));

HxExpression x = model.Set(5);
model.Maximize(model.Count(x));

HxExpression x = model.setVar(5);
model.maximize(model.count(x));

The 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](weight[i] * contains(knapsack, i)) <= capacity;
maximize sum[i in 0...n](value[i] * contains(knapsack, i));

knapsack = model.set(n)
knapsack_weight = model.sum(
    weight[i] * model.contains(knapsack, i) for i in range(n))
knapsack_value = model.sum(
    value[i] * model.contains(knapsack, i) for i in range(n))
model.constraint(knapsack_weight <= capacity)
model.maximize(knapsack_value)

HxExpression knapsack = model.setVar(n);
HxExpression knapsackWeight = model.sum();
HxExpression knapsackValue = model.sum();
for (int i = 0; i < n; ++i) {
    knapsackWeight.addOperand(weight[i] * model.contains(knapsack, i));
    knapsackValue.addOperand(value[i] * model.contains(knapsack, i));
}
model.constraint(knapsackWeight <= capacity);
model.maximize(knapsackValue);

HxExpression knapsack = model.Set(n);
HxExpression knapsackWeight = model.Sum();
HxExpression knapsackValue = model.Sum();
for (int i = 0; i < n; ++i)
{
    knapsackWeight.AddOperand(weight[i] * model.Contains(knapsack, i));
    knapsackValue.AddOperand(value[i] * model.Contains(knapsack, i));
}
model.Constraint(knapsackWeight <= capacity);
model.Maximize(knapsackValue);

HxExpression knapsack = model.setVar(n);
HxExpression knapsackWeight = model.sum();
HxExpression knapsackValue = model.sum();
for (int i = 0; i < n; ++i) {
    knapsackWeight.addOperand(model.prod(weight[i], model.contains(knapsack, i)));
    knapsackValue.addOperand(model.prod(value[i], model.contains(knapsack, i)));
}
model.constraint(model.leq(knapsackWeight, capacity));
model.maximize(knapsackValue);

The distinct operator takes as input a collection and a lambda function, and returns the unordered set of distinct values among all the values returned by the function. For example, the following constraint forces a machine to produce at most two distinct types of product:

machine <- list(10);
productTypes = { 0, 1, 2, 1, 2, 0, 0, 1, 2, 1 };
constraint count(distinct(machine, i => productTypes[i])) <= 2;

machine = model.list(10)
product_types = model.array([0, 1, 2, 1, 2, 0, 0, 1, 2, 1])
product_type = model.lambda_function(lambda i: product_types[i])
model.constraint(model.count(model.distinct(machine, product_type)) <= 2)

HxExpression machine = model.listVar(10);
std::vector<int> productTypes { 0, 1, 2, 1, 2, 0, 0, 1, 2, 1 };
HxExpression hxProductTypes = model.array(productTypes.begin(), productTypes.end());
HxExpression productType = model.lambdaFunction(
    [&](HxExpression i) { return hxProductTypes[i]; });
model.constraint(model.count(model.distinct(machine, productType)) <= 2);

HxExpression machine = model.List(10);
long[] productTypes = { 0, 1, 2, 1, 2, 0, 0, 1, 2, 1 };
HxExpression hxProductTypes = model.Array(productTypes);
HxExpression productType = model.LambdaFunction(
    (HxExpression i) => model.At(hxProductTypes, i));
model.Constraint(model.Count(model.Distinct(machine, productType)) <= 2);

HxExpression machine = model.listVar(10);
long[] productTypes = { 0, 1, 2, 1, 2, 0, 0, 1, 2, 1 };
HxExpression hxProductTypes = model.array(productTypes);
HxExpression productType = model.lambdaFunction(
    i -> model.at(hxProductTypes, i));
model.constraint(model.leq(model.count(model.distinct(machine, productType)), 2));

The intersection operator takes two operands if operands are collections or arrays. It returns the unordered set of the values present in both operands. For example the following constraint prevents the set from containing values 0, 1 and 2:

forbiddenValues <- array(0, 1, 2);
numbers <- set(10);
constraint count(intersection(numbers, forbiddenValues)) == 0;

forbidden_values = model.array([0, 1, 2])
numbers = model.set(10)
model.constraint(model.count(model.intersection(numbers, forbidden_values)) == 0)

std::vector<int> forbiddenValues { 0, 1, 2 };
HxExpression hxForbiddenValues = model.array(forbiddenValues.begin(), forbiddenValues.end());
HxExpression numbers = model.setVar(10);
model.constraint(model.count(model.intersection(numbers, hxForbiddenValues)) == 0);

HxExpression forbiddenValues = model.Array(new long[] { 0, 1, 2 });
HxExpression numbers = model.Set(10);
model.Constraint(model.Count(model.Intersection(numbers, forbiddenValues)) == 0);

HxExpression forbiddenValues = model.array(new long[] { 0, 1, 2 });
HxExpression numbers = model.setVar(10);
model.constraint(model.eq(model.count(model.intersection(numbers, forbiddenValues)), 0));

The sort operator takes as input a collection and a lambda function, and sorts the input based on the values returned by the function into ascending order. For example, the following lines sort the objects contained in a knapsack into ascending order of values:

knapsack <- set(n);
sortedValues <- sort(knapsack, i => value[i]);

knapsack = model.set(n)
value_array = model.array(value)
sorted_values = model.sort(knapsack, model.lambda_function(lambda i: value_array[i]))

HxExpression knapsack = model.setVar(n);
HxExpression valueArray = model.array(value.begin(), value.end());
HxExpression sortedValues = model.sort(knapsack,
    model.lambdaFunction([&](HxExpression i) { return valueArray[i]; }));

HxExpression knapsack = model.Set(n);
HxExpression valueArray = model.Array(value);
HxExpression sortedValues = model.Sort(knapsack,
    model.LambdaFunction((HxExpression i) => model.At(valueArray, i)));

HxExpression knapsack = model.setVar(n);
HxExpression valueArray = model.array(value);
HxExpression sortedValues = model.sort(knapsack,
    model.lambdaFunction(i -> model.at(valueArray, i)));

Operators specific to lists

The at operator allows accessing the value at a given position in the list. It takes two operands: a list and an integer expression. It fails 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];

x = model.list(5)
model.constraint(model.count(x) > 0)
model.maximize(x[0] * x[model.count(x) - 1])

HxExpression x = model.listVar(5);
model.constraint(model.count(x) > 0);
model.maximize(x[0] * x[model.count(x) - 1]);

HxExpression x = model.List(5);
model.Constraint(model.Count(x) > 0);
model.Maximize(model.At(x, 0) * model.At(x, model.Count(x) - 1));

HxExpression x = model.listVar(5);
model.constraint(model.gt(model.count(x), 0));
model.maximize(model.prod(model.at(x, 0), model.at(x, model.sub(model.count(x), 1))));

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

x = model.list(n)
model.constraint(model.count(x) == n)
ordering_cost = model.sum(
    c[i][j] * (model.index(x, i) > model.index(x, j))
    for i in range(n) for j in range(n))
model.minimize(ordering_cost)

HxExpression x = model.listVar(n);
model.constraint(model.count(x) == n);
HxExpression orderingCost = model.sum();
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j)
        orderingCost.addOperand(c[i][j] * (model.indexOf(x, i) > model.indexOf(x, j)));
}
model.minimize(orderingCost);

HxExpression x = model.List(n);
model.Constraint(model.Count(x) == n);
HxExpression orderingCost = model.Sum();
for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < n; ++j)
        orderingCost.AddOperand(c[i][j] * (model.IndexOf(x, i) > model.IndexOf(x, j)));
}
model.Minimize(orderingCost);

HxExpression x = model.listVar(n);
model.constraint(model.eq(model.count(x), n));
HxExpression orderingCost = model.sum();
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        HxExpression isJBeforeI = model.gt(model.indexOf(x, i), model.indexOf(x, j));
        orderingCost.addOperand(model.prod(c[i][j], isJBeforeI));
    }
}
model.minimize(orderingCost);

The array operator takes as input a list and a lambda function, and returns the array created by applying the function to every element in the list. It can also be used with a two-argument lambda function to create recursive arrays. For example, the following array defines the end times of consecutive tasks on a machine:

x <- list(n);
endTimes <- array(x, (i, prev) => prev + duration[i]);

x = model.list(n)
duration_array = model.array(duration)
end_times = model.array(
    x, model.lambda_function(lambda i, prev: prev + duration_array[i]))

HxExpression x = model.listVar(n);
HxExpression durationArray = model.array(duration.begin(), duration.end());
HxExpression endTimes = model.array(x, model.lambdaFunction(
    [&](HxExpression i, HxExpression prev) { return prev + durationArray[i]; }));

HxExpression x = model.List(n);
HxExpression durationArray = model.Array(duration);
HxExpression endTimes = model.Array(x, model.LambdaFunction(
    (HxExpression i, HxExpression prev) => prev + model.At(durationArray, i)));

HxExpression x = model.listVar(n);
HxExpression durationArray = model.array(duration);
HxExpression endTimes = model.array(x, model.lambdaFunction(
    (i, prev) -> model.sum(prev, model.at(durationArray, i))));

N-ary operators

The 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));

x = model.list(10)
y = model.list(10)
z = model.list(10)
model.constraint(model.disjoint(x, y, z))
model.maximize(model.min(model.count(x), model.count(y), model.count(z)))

HxExpression x = model.listVar(10);
HxExpression y = model.listVar(10);
HxExpression z = model.listVar(10);
model.constraint(model.disjoint(x, y, z));
model.maximize(model.min(model.count(x), model.count(y), model.count(z)));

HxExpression x = model.List(10);
HxExpression y = model.List(10);
HxExpression z = model.List(10);
model.Constraint(model.Disjoint(x, y, z));
model.Maximize(model.Min(model.Count(x), model.Count(y), model.Count(z)));

HxExpression x = model.listVar(10);
HxExpression y = model.listVar(10);
HxExpression z = model.listVar(10);
model.constraint(model.disjoint(x, y, z));
model.maximize(model.min(model.count(x), model.count(y), model.count(z)));

The 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. For example, the following constraint ensures that every customer is served by at least one truck:

trucks[k in 0...nbTrucks] <- list(nbCustomers);
constraint cover[k in 0...nbTrucks](trucks[k]);

trucks = [model.list(nb_customers) for k in range(nb_trucks)]
model.constraint(model.cover(trucks))

std::vector<HxExpression> trucks(nbTrucks);
for (int k = 0; k < nbTrucks; ++k)
    trucks[k] = model.listVar(nbCustomers);
model.constraint(model.cover(trucks.begin(), trucks.end()));

HxExpression[] trucks = new HxExpression[nbTrucks];
for (int k = 0; k < nbTrucks; ++k)
    trucks[k] = model.List(nbCustomers);
model.Constraint(model.Cover(trucks));

HxExpression[] trucks = new HxExpression[nbTrucks];
for (int k = 0; k < nbTrucks; ++k)
    trucks[k] = model.listVar(nbCustomers);
model.constraint(model.cover(trucks));

The 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, it combines the disjoint and cover operators: it returns 1 if every element in [0, n-1] is present in exactly one of the collections. For example, the following constraint ensures that each item is placed in exactly one bin:

bins[k in 0...nbBins] <- set(nbItems);
constraint partition[k in 0...nbBins](bins[k]);

bins = [model.set(nb_items) for k in range(nb_bins)]
model.constraint(model.partition(bins))

std::vector<HxExpression> bins(nbBins);
for (int k = 0; k < nbBins; ++k)
    bins[k] = model.setVar(nbItems);
model.constraint(model.partition(bins.begin(), bins.end()));

HxExpression[] bins = new HxExpression[nbBins];
for (int k = 0; k < nbBins; ++k)
    bins[k] = model.Set(nbItems);
model.Constraint(model.Partition(bins));

HxExpression[] bins = new HxExpression[nbBins];
for (int k = 0; k < nbBins; ++k)
    bins[k] = model.setVar(nbItems);
model.constraint(model.partition(bins));

These three 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.

The union operator applies to N collections and/or arrays, and returns the unordered set of the values present in at least one operand. For example, the following lines returns the unordered set of customers served by at least one truck:

truck[i in 0...nbTrucks] <- list(nbCustomers);
servedCustomers <- union[i in 0...nbTrucks](truck[i]);

truck = [model.list(nb_customers) for i in range(nb_trucks)]
served_customers = model.union(truck)

std::vector<HxExpression> truck(nbTrucks);
for (int i = 0; i < nbTrucks; ++i)
    truck[i] = model.listVar(nbCustomers);
HxExpression servedCustomers = model.union_();
servedCustomers.addOperands(truck.begin(), truck.end());

HxExpression[] truck = new HxExpression[nbTrucks];
for (int i = 0; i < nbTrucks; ++i)
    truck[i] = model.List(nbCustomers);
HxExpression servedCustomers = model.Union();
for (int i = 0; i < nbTrucks; ++i)
    servedCustomers.AddOperand(truck[i]);

HxExpression[] truck = new HxExpression[nbTrucks];
for (int i = 0; i < nbTrucks; ++i)
    truck[i] = model.listVar(nbCustomers);
HxExpression servedCustomers = model.union();
for (int i = 0; i < nbTrucks; ++i)
    servedCustomers.addOperand(truck[i]);

Modeling with sets

Set decision variables are very useful to model optimization problems with assignment relationships. If a problem involves “containers” and “contained” elements, with several elements inside each container, and a requirement that every element belongs to at most, exactly, or at least one container, it can generally be modeled using set decisions linked together by a disjoint, partition, or cover constraint.

For example, the Bin Packing Problem (BPP) illustrates the use of set decisions very well: each bin is modeled using a set decision, and the elements in the set correspond to the indices of the items in the bin. To ensure that each items belong to exactly one bin, the sets are constrained to form a partition thanks to the partition operator.

Note

While an equivalent model can often be written by replacing each set variable with n Booleans (x[i] equals 1 if element i is in the set, 0 if not), set decisions are generally preferred. Indeed, Hexaly Optimizer’s large collection of dedicated set-based operators make the modeling more straightforward. Furthermore, set decisions are higher-level decision variables, and they provide more structural information for the solver, leading to overall better performance.

Detailed packing examples using set variables are available in our code templates.

Modeling with lists

List decision variables are very useful to model optimization problems which involve an ordering, or an assignment relationship combined with an ordering. If a problem involves one or several “containers” with “contained” elements, with several elements inside each container, an ordering on the elements in each container, and a requirement that every element belongs to at most, exactly, or at least one container, it can generally be modeled using list decisions linked together by a disjoint, partition, or cover constraint.

Lists are often used to model the order of customers visited by the vehicles in routing problems. For example, a pure Traveling Salesman Problem (TSP) is modeled with a single list x with a constraint count(x) == n in order to ensure that all cities are visited. For routing problems involving several vehicles, such as the Capacitated Vehicle Routing Problem (CVRP), the model associates one list decision to each vehicle, representing the customers served by this vehicle.

Another typical use case for list decision variables is disjunctive scheduling. Scheduling problems are modeled using interval variables representing the time span of the tasks. These decisions allow easy access to the start and end times of the tasks. However, when modeling a disjunctive scheduling problem, such as the Job Shop Scheduling Problem (JSSP), is it generally also useful to know the order in which the tasks are processed, to be able to access the task in position i in the schedule, or the neighboring tasks of a given task. In this context, we use one list decision variable for each disjunctive resource, representing the order of the tasks scheduled on this resource.

Detailed routing and scheduling examples are available in our code templates.