Use Global State in Constraints

[ulrich-grossmann]

Problem background

I am solving real-world school-timetable problems with Timefold and have many complex constraints like students of one grade having lessons together with students of another grade, lessons that have to span multiple consecutive timeslots and grades beeng divided into any number of subgroups that are taught different subjects by different teachers at the same time.
It is often difficult to express such constraints with the constraints-stream language of Timefold yet it is possible but it is even more difficult to express it in a performant way.

The global state pattern and its advantages

So I came across a different design pattern where I use global state in a singleton. This global state is updated before and after any variable change and thus supports fast and scalable incremental score calculation.
But this incremental score calculation goes even two steps ahead of the incremental score calculation provided by Timefold.

1. It removes any filtering, so filtering becomes O(1)
2. It makes basically any evaluation inside such a constraint O(1)

Another advantage is that any number of such constraint can be merged into one constraint if speed is important.
This design pattern improves score calculation significantly.
In my real world scenario I managed to improve score calculation speed from 30.000 up to 200.000.
In the POC scenario I provide below the speed improves even in the most basic scenario from 175.000 to 400.000.

A simple POC

In order to explain the pattern I have forked the school-timetable-helloworld quickstart:
https://github.com/ulrich-grossmann/timefold-quickstarts

The problems

There are significant problems with this pattern at the moment.

• It is detected as score corruption in all ASSERT modes even in FAST_ASSERT. In integration tests I see no problem though.
• It violates the principle of Timefold to make solving an everyday-programmers task - as it introduces a lot of complexity
• It makes explaining scores almost impossible.
• Many other problems have been outlined on stackoverflow

My questions

Still I want to use this approach and wonder if it could be helpful in other scenarios too. So I have some questions:

• In one respect this pattern implements java incremental score calculation inside constraints stream score calculation, so that both concepts can be combined - or is this already possible?
• In another respect it is a special kind of constraint. Could that maybe integrated into the constraints stream language?

[triceo]

Hello there, @ulrich-grossmann. Yours is an interesting question.

I'm going to approach this question from an entirely different perspective. Since you've already decided you want to get performance at whatever cost, why not look into IncrementalScoreCalculator? With this, you can implement literally anything you like, without being constrained by the programming model of Constraint Streams.

Incremental calculator is the fastest you can possibly be with Timefold Solver. Essentially, the limit there is how fast your hand-rolled Java code can be. There is even a variant (ConstraintMatchAwareIncrementalScoreCalculator) which allows you to integrate this with score analysis etc. (Although that is a niche use case, which doesn't see much use; there be lions.)

But let's assume you want to stick with Constraint Streams. If we're talking about IncrementalCountingConstraint, what you have there should be doable by a custom constraint collector and therefore a single groupBy. (See UniConstraintCollector, or Bi..., Tri..., Quad....) Writing constraint collectors is not simple, but it is the preferred way of getting incremental performance out of complex logic.

I'm not saying whether or not you'll keep your 7x improvement. Most likely you will land somewhere in the middle. But I will argue that you have not actually achieved a 7x improvement, because your code has score corruptions. Choosing performance over correctness is not a choice I can recommend.

[ulrich-grossmann]

Thank you for the quick responses, @triceo.

The problem with IncremantalScoreCalculator for me is, that I have many constraints (~20) written as ConstraintStream with unit tests and feel safe about their correctness. Plus, I don't have the resources to rewrite them all. So I'm definitely stuck with constraint streams at the moment.

Considering the custom constraint collectors using for instance groupBy that approach is incremental until you evaluate all the objects grouped in your list. There it is as I understand non-incremental and O(n) where n is the size of the list. I didn't manage to get above 40.000/s in my scenario with this approach (and I really tried to squeeze water from a stone...). IncrementalCountingConstraint will in my opinion be O(1) here. That seems to be the reason it is that much faster.

But I fully agree that choosing performance over correctness is not the way to go. That's why I'm searching for some kind of compromise.

[triceo]

You are correct that toList() is, in fact, non-incremental. Which is why I kinda regret we even introduced it as an option - because once people see that it exists, all thinking of incrementality goes out the window and we're safely back in the comfortable territory of iterating over lists. :-)

My point with a custom collector was different, though. Consider a groupBy() like this:

.groupBy(myCustomCollector(...))
.penalize(..., (customCollectorResult) -> // do something)

With a properly implemented collector, you can have what used to be global, but built locally inside the constraint, fully incrementally. There is no need to put anything into a list, or to do any iteration - assuming you can write a collector which doesn't do those things. Since you already have code that doesn't do those things, converting the code to a custom collector should not be too hard.

[ulrich-grossmann]

Thank you for clarifying on the custom-collector-approach @triceo, it works as expected and even faster. It improves the speed of the basic teacher, student group and room conflict constraints in the school timetable quickstart from ~200.000 up to ~700.000.
In the updated PoC quickstart fork I use a custom shadow variable listener to plugin global singletons that do basically the same thing as a IncrementalScoreCalculator but inside the constraints stream framework.
This way I should be able to combine both approaches and to optimise some constraints using incremental java calculation while keeping others within the safety of the constraint stream framework.
When using the shadow variable listener the PoC survives 10 minutes of FULL_ASSERT so on the surface this use of globals seems to be legitimate.
Below that surface I'm stuck with some problems:

• I had to register my custom shadow variable listener that plugs in the global incremental score calculator on the planning entity Lesson. A lesson now holds the global score derived from the conflicts of all lessons together as a shadow variable. This feels semantically wrong to me. Can I register the shadow variable listener on the planning solution instead but still listen to changes in the planning entities?
• The implementation of the PoC as of now only passes FULL_ASSERT when I reset all global counters and maps on resetWorkingSolution. But this breaks the integration tests, because in order to get a correct result in integration tests I must not reset anything during resetWorkingSolution. The problem arises I think when resetWorkingSolution is called between construction heuristics and local search. So my question here is: How does the resetWorkingSolution call work exactly?
• I had to register my custom shadow variable listener so that it listens to both planning variables at once. But this means that inside the beforeVariableChanged and afterVariableChanged methods I have (unlike with a IncrementalScoreCalculator) no means to detect which variable has been changed.

In essence im searching for a way to combine constraint streams with an IncrementalScoreCalculator simply adding up the scores from both - would be very helpful to have that option built in inside Timefold like

.withScoreDirectorFactory(new ScoreDirectorFactoryConfig()
                                .withIncrementalScoreCalculatorClass(JavaIncrementalCalculatorUsingGlobalState.class)
                                .withConstraintProviderClass(TimetableConstraintProvider.class))

[triceo]

For as long as you rely on any approach which uses global state, I am unable to give you any advice. Any such approach is fundamentally flawed and will likely never work reliably with the solver. Even if you fix the current issue, you will uncover another one, and another one after that - this is a rabbit hole, it goes very deep, and there is no solution at the bottom.

Let's go back to the basics. Our general recommendation is to achieve a score calculation speed of 10k+, for the solver to give good results. What score calculation speeds are you getting for your problem, with clean constraints? And if they're in high 5 digits, or even 6 digits, why are they not enough? I'm guessing here, but if (with these speeds) the solver still isn't giving you good enough results, perhaps the problem is elsewhere? Perhaps you need custom moves to get the solver unstuck?

[ulrich-grossmann]

With normal scores the speed is ~30k, and "good" results are reached within 10 - 20 minutes. I would call them "good" regarding the problem complexity, but "good" is a relative term.
This speed is only possible for me if I make heavy use of hashing etc., thus only if I already use a complicated infrastructure like needed for IncrementalScoreCalculator.
Increasing the speed shortens the feedback-cycles both for users and developers, which I think is important. It would also enhance the user experience.
I have two timetable projects. Only in one of them the custom moves were beneficial so far. Implementing better custom moves is definitively one direction of improvement.
But another direction is applying something like bayesian optimisation on solver parameters (like the simulated annealing starting temperature or the sorting used for construction heuristics). Here the calculation speed matters a lot and in the end influences quality.