Interval Variables¶

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

Mathematical principle and creation operator¶

Interval decisions are used to model the time range of an event. They are declared using the interval operator:

Hexaly Modeler
Python
C++
C#
Java

x <- interval(minStart, maxEnd);

x = model.interval(min_start, max_end)

HxExpression x = model.intervalVar(minStart, maxEnd);

HxExpression x = model.Interval(minStart, maxEnd);

HxExpression x = model.intervalVar(minStart, maxEnd);

with two integer operands representing the minimum start and maximum end of the decision respectively. The value of an interval decision is an integer interval [a, b), whose start a is included and whose end b is excluded, verifying a >= minStart, b <= maxEnd, and a <= b.

Based on this definition, the following examples represent valid values for an interval decision variable of minimum start 0 and maximum end 5:

[0, 1)  // Singleton (0 is included, but 1 is excluded)
[1, 4)
[2, 2)  // Degenerate interval (zero length)
[0, 5)  // Full interval (maximum length)

On the contrary, the following examples are invalid values:

[3, 6)  // Out of bounds for an interval of maximum end 5
[2, 0)  // An interval's start is lower or equal to its end

Optional intervals¶

Similarly to regular intervals, optional intervals are declared using the optionalInterval operator, with two operands representing the minimum start and maximum end:

Hexaly Modeler
Python
C++
C#
Java

x <- optionalInterval(minStart, maxEnd);

x = model.optional_interval(min_start, max_end)

HxExpression x = model.optionalIntervalVar(minStart, maxEnd);

HxExpression x = model.OptionalInterval(minStart, maxEnd);

HxExpression x = model.optionalIntervalVar(minStart, maxEnd);

Contrary to classical interval decision variables, optional intervals can also be void: the value of an optional interval decision variable can either be “absent” (void) or included in [minStart, maxEnd). When present, start is inclusive and end is exclusive. When absent, start and end are undefined.

Setting and retrieving values¶

As mentioned above, the value of an interval decision is an integer interval. This value is obtained with the syntax x.value in Hexaly Modeler, with x.value or x.get_interval_value() in Python, with getIntervalValue() in C++ and Java, and with GetIntervalValue() in C#. It returns an object of type HxInterval, that can be read through the methods: start, end, count, isVoid:

Hexaly Modeler
Python
C++
C#
Java

println(x.value.start());   // Current start of the interval
println(x.value.end());     // Current end of the interval
println(x.value.count());   // Current size of the interval
println(x.value.isVoid());  // 1 if the interval is absent (void), or 0 if it is present
println(x.value);           // Print the content of the interval

interval = x.value
print(interval.start())     # Current start of the interval
print(interval.end())       # Current end of the interval
print(interval.count())     # Current size of the interval
print(interval.is_void())   # True if the interval is absent (void), or False if it is present
print(interval)             # Print the content of the interval

HxInterval interval = x.getIntervalValue();
std::cout << interval.getStart() << std::endl;  // Current start of the interval
std::cout << interval.getEnd() << std::endl;    // Current end of the interval
std::cout << interval.count() << std::endl;     // Current size of the interval
std::cout << interval.isVoid() << std::endl;    // 1 if the interval is absent (void), or 0 if it is present
std::cout << interval.toString() << std::endl;  // Print the content of the interval

HxInterval interval = x.GetIntervalValue();
Console.WriteLine(interval.Start());  // Current start of the interval
Console.WriteLine(interval.End());    // Current end of the interval
Console.WriteLine(interval.Count());  // Current size of the interval
Console.WriteLine(interval.IsVoid()); // True if the interval is absent (void), or False if it is present
Console.WriteLine(interval);          // Print the content of the interval

HxInterval interval = x.getIntervalValue();
System.out.println(interval.getStart()); // Current start of the interval
System.out.println(interval.getEnd());   // Current end of the interval
System.out.println(interval.count());    // Current size of the interval
System.out.println(interval.isVoid());   // true if the interval is absent (void), or false if it is present
System.out.println(interval);            // Print the content of the interval

Setting the value of an interval variable can be done by creating a new HxInterval object. When using Hexaly Modeler, this is done by defining an integer range using the a...b syntax. When a <= b, this creates a regular interval [a, b), and when a > b, this creates a void interval:

Hexaly Modeler
Python
C++
C#
Java

x.value = 0...4;    // Interval [0, 4)
x.value = 1...1;    // Interval [1, 1)
x.value = 0...-1;   // Void interval

x.set_interval_value(HxInterval(0, 4))  # Interval [0, 4)
x.set_interval_value(HxInterval(1))     # Interval [1, 1)
x.set_interval_value(HxInterval())      # Void interval

x.setIntervalValue(HxInterval(0, 4));   // Interval [0, 4)
x.setIntervalValue(HxInterval(1));      // Interval [1, 1)
x.setIntervalValue(HxInterval());       // Void interval

x.SetIntervalValue(new HxInterval(0, 4)); // Interval [0, 4)
x.SetIntervalValue(new HxInterval(1));    // Interval [1, 1)
x.SetIntervalValue(new HxInterval());     // Void interval

x.setIntervalValue(new HxInterval(0, 4)); // Interval [0, 4)
x.setIntervalValue(new HxInterval(1));    // Interval [1, 1)
x.setIntervalValue(new HxInterval());     // Void interval

With Hexaly Optimizer APIs, this is done by using HxInterval’s constructor. It can be used with zero operand to create a void interval, with a single operand a to create a degenerate interval [a, a), or with two operands a <= b to create an interval [a, b).

Operators on intervals and optional intervals¶

Unary operators¶

The start operator returns the start of a non-void interval (included), or NaN if applied to a void interval. For example, the following lines compute the earliest start time of a given set of tasks:

Hexaly Modeler
Python
C++
C#
Java

tasks[i in 0...nbTasks] <- interval(0, horizon);
earliestStart <- min[i in 0...nbTasks](start(tasks[i]));

tasks = [model.interval(0, horizon) for i in range(nb_tasks)]
earliest_start = model.min(model.start(tasks[i]) for i in range(nb_tasks))

std::vector<HxExpression> tasks(nbTasks);
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.intervalVar(0, horizon);
}
HxExpression earliestStart = model.min();
for (int i = 0; i < nbTasks; ++i) {
    earliestStart.addOperand(model.start(tasks[i]));
}

HxExpression[] tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.Interval(0, horizon);
}
HxExpression earliestStart = model.Min();
for (int i = 0; i < nbTasks; ++i) {
    earliestStart.AddOperand(model.Start(tasks[i]));
}

HxExpression[] tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.intervalVar(0, horizon);
}
HxExpression earliestStart = model.min();
for (int i = 0; i < nbTasks; ++i) {
    earliestStart.addOperand(model.start(tasks[i]));
}

The end operator returns the end of a non-void interval (excluded), or NaN if applied to a void interval. For example, the following lines define a set of tasks as interval decisions and sets the objective function as the makespan (latest end time):

Hexaly Modeler
Python
C++
C#
Java

tasks[i in 0...nbTasks] <- interval(0, horizon);
makespan <- max[i in 0...nbTasks](end(tasks[i]));
minimize makespan;

tasks = [model.interval(0, horizon) for i in range(nb_tasks)]
makespan = model.max(model.end(tasks[i]) for i in range(nb_tasks))
model.minimize(makespan)

std::vector<HxExpression> tasks(nbTasks);
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.intervalVar(0, horizon);
}
HxExpression makespan = model.max();
for (int i = 0; i < nbTasks; ++i) {
    makespan.addOperand(model.end(tasks[i]));
}
model.minimize(makespan);

HxExpression[] tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.Interval(0, horizon);
}
HxExpression makespan = model.Max();
for (int i = 0; i < nbTasks; ++i) {
    makespan.AddOperand(model.End(tasks[i]));
}
model.Minimize(makespan);

HxExpression[] tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.intervalVar(0, horizon);
}
HxExpression makespan = model.max();
for (int i = 0; i < nbTasks; ++i) {
    makespan.addOperand(model.end(tasks[i]));
}
model.minimize(makespan);

The length operator returns the length of a non-void interval, or NaN if applied to a void interval. If x is an interval decision, length(x) is equivalent to end(x) - start(x). For example, the following constraint ensures that the length of the interval is equal to the duration of the task it represents:

Hexaly Modeler
Python
C++
C#
Java

task <- interval(0, horizon);
constraint length(task) == duration;

task = model.interval(0, horizon)
model.constraint(model.length(task) == duration)

HxExpression task = model.intervalVar(0, horizon);
model.constraint(model.length(task) == duration);

HxExpression task = model.Interval(0, horizon);
model.Constraint(model.Length(task) == duration);

HxExpression task = model.intervalVar(0, horizon);
model.constraint(model.eq(model.length(task), duration));

The count operator returns the number of elements inside the interval. It is the set-based counterpart of the length operator: both return the same value for non-void intervals, but the count operator returns 0 when applied to a void interval (instead of NaN). Indeed, on the one hand, the length operator regards intervals as time intervals, and considers that the length of a void interval is undefined, and on the other hand, the count operator regards intervals as collections of consecutive integers, and considers that the number of elements inside a void interval is zero. For example, the following lines constraint the total size of subtasks in a preemptive scheduling problem to be equal to the whole duration of the task:

Hexaly Modeler
Python
C++
C#
Java

subtasks[k in 0...nbSubtasks] <- optionalInterval(0, horizon);
constraint sum[k in 0...nbSubtasks](count(subtasks[k])) == duration;

subtasks = [model.optional_interval(0, horizon) for k in range(nb_subtasks)]
total_size = model.sum(model.count(subtasks[k]) for k in range(nb_subtasks))
model.constraint(total_size == duration)

std::vector<HxExpression> subtasks(nbSubtasks);
for (int k = 0; k < nbSubtasks; ++k) {
    subtasks[k] = model.optionalIntervalVar(0, horizon);
}
HxExpression totalSize = model.sum();
for (int k = 0; k < nbSubtasks; ++k) {
    totalSize.addOperand(model.count(subtasks[k]));
}
model.constraint(totalSize == duration);

HxExpression[] subtasks = new HxExpression[nbSubtasks];
for (int k = 0; k < nbSubtasks; ++k) {
    subtasks[k] = model.OptionalInterval(0, horizon);
}
HxExpression totalSize = model.Sum();
for (int k = 0; k < nbSubtasks; ++k) {
    totalSize.AddOperand(model.Count(subtasks[k]));
}
model.Constraint(totalSize == duration);

HxExpression[] subtasks = new HxExpression[nbSubtasks];
for (int k = 0; k < nbSubtasks; ++k) {
    subtasks[k] = model.optionalIntervalVar(0, horizon);
}
HxExpression totalSize = model.sum();
for (int k = 0; k < nbSubtasks; ++k) {
    totalSize.addOperand(model.count(subtasks[k]));
}
model.constraint(model.eq(totalSize, duration));

The presence operator returns 1 if the interval is present (non-void), and 0 if it is void. For example, the following lines ensure that we constrain the size of an interval to be equal to the corresponding task’s duration only if it is present:

Hexaly Modeler
Python
C++
C#
Java

task <- optionalInterval(0, horizon);
constraint presence(task) ? length(task) == duration : true;

task = model.optional_interval(0, horizon)
model.constraint(model.iif(model.presence(task), model.length(task) == duration, True))

HxExpression task = model.optionalIntervalVar(0, horizon);
model.constraint(model.iif(model.presence(task), model.length(task) == duration, true));

HxExpression task = model.OptionalInterval(0, horizon);
model.Constraint(model.Or(model.Presence(task) == 0, model.Length(task) == duration));

HxExpression task = model.optionalIntervalVar(0, horizon);
model.constraint(model.iif(model.presence(task), model.eq(model.length(task), duration), 1));

Binary operators¶

The lt (resp. gt) operator, with shortcut < (resp. >) returns 1 if the first interval is strictly before (resp. after) the second one: it returns 1 if the end of the first interval is lower of equal to the start of the second one, and 0 if not. The expression x < y is equivalent to end(x) <= start(y). It returns NaN if at least one operand is void. For example, the following lines express a precedence constraint between two intervals:

Hexaly Modeler
Python
C++
C#
Java

x <- interval(0, horizon);
y <- interval(0, horizon);
constraint x < y;

x = model.interval(0, horizon)
y = model.interval(0, horizon)
model.constraint(x < y)

HxExpression x = model.intervalVar(0, horizon);
HxExpression y = model.intervalVar(0, horizon);
model.constraint(x < y);

HxExpression x = model.Interval(0, horizon);
HxExpression y = model.Interval(0, horizon);
model.Constraint(x < y);

HxExpression x = model.intervalVar(0, horizon);
HxExpression y = model.intervalVar(0, horizon);
model.constraint(model.lt(x, y));

The contains operator takes an interval as a first operand, and an interval or an integer as a second operand. It returns 1 if the second operand if fully contained within the first one. A non-void interval b is considered fully contained within a non-void interval a if b’s start is greater or equal to a’s start and if b’s end is lower of equal to a’s end. If the first operand is a void interval, the contains operator returns 0. If the second operand is a void interval, the contains operator returns NaN. For example, the following lines count the number of tasks that are active at a given time t:

Hexaly Modeler
Python
C++
C#
Java

tasks[i in 0...nbTasks] <- interval(0, horizon);
nbActiveTasks <- sum[i in 0...nbTasks](contains(tasks[i], t));

tasks = [model.interval(0, horizon) for i in range(nb_tasks)]
nb_active_tasks = model.sum(model.contains(tasks[i], t) for i in range(nb_tasks))

std::vector<HxExpression> tasks(nbTasks);
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.intervalVar(0, horizon);
}
HxExpression nbActiveTasks = model.sum();
for (int i = 0; i < nbTasks; ++i) {
    nbActiveTasks.addOperand(model.contains(tasks[i], t));
}

HxExpression[] tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.Interval(0, horizon);
}
HxExpression nbActiveTasks = model.Sum();
for (int i = 0; i < nbTasks; ++i) {
    nbActiveTasks.AddOperand(model.Contains(tasks[i], t));
}

HxExpression[] tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.intervalVar(0, horizon);
}
HxExpression nbActiveTasks = model.sum();
for (int i = 0; i < nbTasks; ++i) {
    nbActiveTasks.addOperand(model.contains(tasks[i], t));
}

The distinct operator takes as input an interval 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 within the time span of a task:

Hexaly Modeler
Python
C++
C#
Java

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

task = model.interval(0, 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(task, product_type)) <= 2)

HxExpression task = model.intervalVar(0, 10);
std::vector<hxint> productTypesData = {0, 1, 2, 1, 2, 0, 0, 1, 2, 1};
HxExpression productTypes = model.array(productTypesData.begin(), productTypesData.end());
HxExpression productType = model.createLambdaFunction(
    [&productTypes](HxExpression i) { return productTypes[i]; });
model.constraint(model.count(model.distinct(task, productType)) <= 2);

HxExpression task = model.Interval(0, 10);
HxExpression productTypes = model.Array(new long[] { 0, 1, 2, 1, 2, 0, 0, 1, 2, 1 });
HxExpression productType = model.LambdaFunction(i => productTypes[i]);
model.Constraint(model.Count(model.Distinct(task, productType)) <= 2);

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

N-ary operators¶

The hull operator returns the smallest interval containing all the intervals given as arguments. If all operands are void, it returns a void interval. If at least of operand is non-void, it returns an interval whose start is equal to the smallest start among all non-void operands, and whose end is equal to the largest end among all non-void operands. For example, the following lines define a set of tasks as interval decisions and defines the objective function as the makespan (latest end time):

Hexaly Modeler
Python
C++
C#
Java

tasks[i in 0...nbTasks] <- interval(0, horizon);
makespan <- end(hull[i in 0...nbTasks](tasks[i]));
minimize makespan;

tasks = [model.interval(0, horizon) for i in range(nb_tasks)]
makespan = model.end(model.hull(tasks))
model.minimize(makespan)

std::vector<HxExpression> tasks(nbTasks);
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.intervalVar(0, horizon);
}
HxExpression taskArray = model.array(tasks.begin(), tasks.end());
HxExpression makespan = model.end(model.hull(taskArray));
model.minimize(makespan);

HxExpression[] tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.Interval(0, horizon);
}
HxExpression makespan = model.End(model.Hull(tasks));
model.Minimize(makespan);

HxExpression[] tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
    tasks[i] = model.intervalVar(0, horizon);
}
HxExpression makespan = model.end(model.hull(tasks));
model.minimize(makespan);

The intersection operator returns the biggest interval fully present in all operands. If at least one operand if void, it returns a void interval. For example, the following lines maximize the intersection between the time span of a task and a preferred production period:

Hexaly Modeler
Python
C++
C#
Java

task <- interval(0, horizon);
preferredRange <- prefStart...prefEnd;
maximize intersection(task, preferredRange);

task = model.interval(0, horizon)
preferred_range = model.range(pref_start, pref_end)
model.maximize(model.intersection(task, preferred_range))

HxExpression task = model.intervalVar(0, horizon);
HxExpression preferredRange = model.range(prefStart, prefEnd);
model.maximize(model.intersection(task, preferredRange));

HxExpression task = model.Interval(0, horizon);
HxExpression preferredRange = model.Range(prefStart, prefEnd);
model.Maximize(model.Intersection(task, preferredRange));

HxExpression task = model.intervalVar(0, horizon);
HxExpression preferredRange = model.range(prefStart, prefEnd);
model.maximize(model.intersection(task, preferredRange));

Modeling with intervals¶

Intervals are used to model the time span of tasks in scheduling problems. Optional intervals model optional tasks, which are often encountered in multi-mode, prize-collecting, or preemptive scheduling problems.

When modeling disjunctive scheduling problems, interval decisions are often paired with list decisions. Indeed, it is often useful to know the order in which the tasks are processed on a disjunctive resource, to access the task in position i, or the neighboring tasks of a given task. In this case, the list decisions represent the order in which the tasks are processed on each machine.

Detailed scheduling examples using interval (and list) decision variables are available in our code templates.