understanding how constraint streams calculate score deltas

[Behrouz-Babaki]

First of all, I take this opportunity to thank all TimeFold developers for their amazing work. I first learned about @ge0ffrey 's work in 2014, when OptaPlanner ranked second in the ICON energy scheduling challenge that I was helping organizing. But it was only very recently that I had the opportunity to have a closer look at TimeFold, and I must say that I'm even more impressed.

I'm trying to learn TimeFold by applying it to a real-world project. I have realized that when I'm defining the constraint streams, I need an understanding (even high level) of the delta calculation mechanism, based on which I can choose how to model the problem. I tried to form this understanding by reading the documentation, checking the GitHub discussions, and some of the messages in optaplanner-dev group. However, I'm still not sure if I have a correct model of this mechanism. That's why I decided to present my mental model, and ask a few questions. Apologies for the long message.

A mental model

Here is my mental model of how score delta calculation works. A move introduces some changes in genuine variables which, as described thoroughly in TimeFold documentation, trigger changes in shadow variables:

My assumption is that every change to a shadow variable is communicated to the ScoreDirector in VriableListener, and that's how ScoreDirector knows about all changed variables:

scoreDirector.beforeVariableChanged(somePlanningEntity, "someShadowVariable");
// changes ...
scoreDirector.afterVariableChanged(somePlanningEntity, "someShadowVariable");

and then when the constraint streams are used for calculating the score delta, in forEach(SomePlanningEntity.class), join(SomePlanningEntity.class), etc. there is an implicit filter that only considers the instances of a planning entity that contain a changed genuine or shadow variable.

Questions

1. Is there a formal description of the delta calculation mechanism in the documentation that I have missed? If not, is there an interest in adding that, and can I help that effort in any way?
2. Is the mental model that I summarized above roughly adequate? I know that it's not accurate, since when I trace the function calls next to moves (in a small TimeFold model), I see more calculations than I expect. However, do you think this mental model is sufficient in estimating the order of calls made for evaluating the moves?

Thanks again for your time.

[triceo]

Hello @Behrouz-Babaki! I remember the ICON challenge well, since I actually contributed much of OptaPlanner's submission there. :-)

Is there a formal description of the delta calculation mechanism in the documentation that I have missed? If not, is there an interest in adding that, and can I help that effort in any way?

There isn't. Constraint Streams API is implemented with an algorithm that is very similar to RETE.

As much as it would be good to have an overview of the architecture somewhere in the docs, let's take a look at your second question first, to understand why we haven't spent the time.

Is the mental model that I summarized above roughly adequate? I know that it's not accurate, since when I trace the function calls next to moves (in a small TimeFold model), I see more calculations than I expect. However, do you think this mental model is sufficient in estimating the order of calls made for evaluating the moves?

The mental model is roughly accurate, but there is so much more going on under the hood. I want to turn the question around - why do you feel like you need to understand what CS does, in order to be able to implement a solution using Timefold Solver? In my opinion, that's the wrong thinking - write a decent object-oriented model, and let it be our job to turn that model into an efficient incremental operation.

We do not want people reverse engineering the engine and making their modeling decisions on implementation details. Implementations change, and if understanding these details would be necessary to use Timefold Solver, then we have failed in our mission.

My advice is to write simple natural code, measure its performance, and if you see performance issues, then it's time to discuss those. We have also published some general recommendations to avoid the most typical issues.

Finally, I hope you don't mind a little correction - it's "Timefold", the "f" is not capitalized.

[Behrouz-Babaki]

Nice to meet you, @triceo! The performance of your submission (and the one of the winning team, which implemented a heuristic search algorithm from scratch) got me interested in local search, and shifted my view about how to solve optimization problems in real-scenarios. Thanks for that!

I want to turn the question around - why do you feel like you need to understand what CS does, in order to be able to implement a solution using Timefold Solver? In my opinion, that's the wrong thinking - write a decent object-oriented model, and let it be our job to turn that model into an efficient incremental operation.

I have a hard time answering this without going into subjective, philosophical arguments. I understand that the ultimate goal of all declarative paradigms is to completely separate the problem statement from the solving mechanism, but in my experience there is always a point after which the user needs to know what goes on under the hood. I acknowledge that this point is different for different solvers. As an example from exact optimization, the knowledge of the solving mechanism is more important when using a constraint programming solver, compared to a MIP solver.

As a concrete example, consider the way that minimizeTravelTime is modelled in Vehicle Routing Quick Start Guide:

factory.forEach(Vehicle.class)
        .penalizeLong(HardSoftLongScore.ONE_SOFT,
                Vehicle::getTotalDrivingTimeSeconds)
       // ...

with getTotalDrivingTimeSeconds() defined as:

public long getTotalDrivingTimeSeconds() {
    if (visits.isEmpty()) {
        return 0;
    }

    long totalDrivingTime = 0;
    Location previousLocation = homeLocation;

    for (Visit visit : visits) {
        totalDrivingTime += previousLocation.getDrivingTimeTo(visit.getLocation());
        previousLocation = visit.getLocation();
    }
    totalDrivingTime += previousLocation.getDrivingTimeTo(homeLocation);

    return totalDrivingTime;
}

If I trust my mental model, I conclude that this loop over all visits is performed with every change in a route. In order to avoid this, I model this value as two constraints:

factory.forEach(Visit.class)
        .penalize(HardSoftLongScore.ONE_SOFT, 
               Visit::getDurationFromPrevious)
       // ...

and

factory.forEach(Route.class)
        .penalizeLong(HardSoftLongScore.ONE_SOFT,
                Vehicle::getLastEdgeDuration)
       // ...

Do you advise against such practices? I think what you're saying is that the performance improvements that the user can obtain by considering the solving mechanism, are not critical or significant in real-world applications.

Thanks again for your response, and thanks for reminding me of the correct spelling of Timefold. It is a name that I think I will be using a lot in future.

[triceo]

In the case you're describing, the getTotalDrivingTimeSeconds() is very inefficient - it iterates over a collection, which makes it non-incremental. Its performance will become more and more of a bottleneck, with the growing size of the collection.

In this case, I have to agree with you - to have efficient constraints, you need to understand the ground rules. In this case, one such ground rule would be "if you're iterating over collections, you're killing performance."

If instead the constraint were defined as:

factory.forEach(Visit.class)
    .penalize(HardSoftLongScore.ONE_SOFT, 
           Visit::getDurationFromPrevious)

And getDurationFromPrevious is just a simple:

 previousLocation.getDrivingTimeTo(currentLocation)

Then this system is completely incremental. When a single Visit changes, only that one will be recomputed, as opposed to the entire list of visits. To implement this constraint efficiently, you only need to understand the one ground rule, not the engine itself.

I think what you're saying is that the performance improvements that the user can obtain by considering the solving mechanism, are not critical or significant in real-world applications.

To some extent, I am saying that. Even poorly performing constraints are often fine, because only very few organizations actually have problems on the scale where this performance bottleneck would actually become a problem. Rule number one of performance optimization in general: premature optimization is the root of all evil. Once your system suffers from a bottleneck, fix it; but not earlier than that.

Thanks again for your response, and thanks for reminding me of the correct spelling of Timefold. It is a name that I think I will be using a lot in future.

We're happy to have you in our community!

[Christopher-Chianelli]

As noted in our general recommendations:

Always remember that premature optimization is the root of all evil. Make sure your design is flexible enough to allow configuration-based tweaking.

The performance difference between the unoptimized "loop through all vehicle visits" version and the optimized "penalize each visit distance to previous" version is minimal until you hit medium to large datasets. However, the "loop through all vehicle visits" is immediately understandable and easy to modify if the definition of the constraint changes.

One of the key differences between Timefold and other solvers is that you are able to write constraints using your domain classes, and don't need to convert them to mathematical equations or formulas. That is extremely valuable; if you optimize the wrong thing (i.e. incorrect constraints or fitness function), getting the optimum solution would either break your hard constraints, or give you a solution that is worse according to the correct fitness function.

In a perfect world, we would be able to take the most inefficient user code and change it to the most efficient version. However, to do that would necessitate either reading the bytecode and recognizing patterns (incredible difficult to maintain and fragile) or require the user to write their filters, joiners, etc. using a domain specific language (that does not currently exist, and would be more difficult to write than plain Java or Python).

There are many advance tools available in Timefold that often has a larger impact on score quality than score calculation speed. For example:

• Changing your domain to restrict search space
• Custom Moves
• Custom Shadow Variables
• Custom Phases
• Filtering Moves

Some of these are currently harder to configure than we would like, and we are working on improving them so users can easily configure them for their planning problems.

[Behrouz-Babaki]

Thanks @triceo and @Christopher-Chianelli. I will try to resist the force of habit and avoid the trap of premature optimization.

There are many advance tools available in Timefold that often has a larger impact on score quality than score calculation speed. For example:

• Changing your domain to restrict search space
• Custom Moves
• Custom Shadow Variables
• Custom Phases
• Filtering Moves

I was thinking where I should look next, and this list answers exactly that question!