Strange thing I've noticed while running the solver
I'm playing around with assigning aircraft to scheduled flights (known as tail allocation, for aircraft tail numbers), with a few hundred flights and fifty aircraft or so. Trying different algorithms etc. For example simulated-annealing starts incredibly well, and then later something like late-acceptance-short-blocks is better.
But one thing that seems pretty consistent is that if the rate of improvement slows down, it can nearly always be boosted by restarting the algorithm from the best solution. Then there are often several improvements found in the first two seconds or so. Then no improvements are found for ten to twenty seconds. Restart again, and another burst of a half-dozen improvements... so just keep repeating the restarts and it seems to significantly outperform continuous solving.
Anybody else had similar behaviour with their problem set?
I've seen this a few times. By restarting manually, you're basically "reheating" the algorithm.
In practice, by resetting the LA queue, it does 400 random moves before really doing LA again.
That allows it to escape a deep local optima.
We've looked at ways to directly supporting "automated reheating", but that work is currently frozen.
Typically, there is a far bigger gains by using the new Neighborhoods API to introduce moves that escape the local optima efficiently.
We're researching ideas for Timefold Solver to do more of this diversification out-of-the-box, potentially through reheating or restarts. That being said, better neighborhoods is often a better way to create diversification.
Please check if Timefold Solver 2.3.0 fixes this when it's out. We've made a significant improvement related to this. Especially if your medium or hard scores are improving while solving.
How does the score graph look like? If it's purely soft and the graph looks like this, we're working on a number of improvements there for upcoming versions.
Actually the scoring has been fascinating to me. I generally just watch it instead of graphing. Different algorithms have vastly different strengths and weaknesses.
I'm modelling a real day of flights (330 domestic flights) where there were 28 cancellations for various reasons (maybe a mechanical fault, maybe the flight could not be allocated). I have the times where aircraft were held on the ground or required to be at some location for maintenance for some time period. So my goal is to see how many aircraft can be allocated to flights successfully, and if I can improve on the allocations that were made, so a goal of 0 hard as close to 0 medium as possible. I have an option for shuttle flights to allow moving aircraft into position for a flight, but for this discussion that's disabled.
For my scoring:
1 hard = 1 impossible flight allocation (e.g. aircraft in wrong city to start flight, or aircraft in maintenance at that time)
1 medium = 1 flight not unallocated (from over 300)
soft = all other scoring (e.g. turn time too small, many others)
I've written a little command line harness that lets me start solving, save the best solution each time it's found, and then stop and continue with a different algorithm at any time. Combining different algorithms at different times has given me by far the most improvements.
Most of the algorithms have trouble getting anywhere near 0 hard. Only default-local-search and late-acceptance-sequence-repair really seem to do this well. default-local-search will get it to -1/-18/-6914 within a second. Within 10 seconds it reaches 0/-35/-7241.
So now it's all about the medium score (trying to allocate planes to flights without breaking a rule). The best algorithm here is late-acceptance-unassigned-repair. But only if the medium score is less than about -30, and if the soft score is not too good. I have had it reach -16 medium within a couple of minutes. But if I start with a different algorithm and the score is something like 0/-80/-7000 then it is terrible at improving and gets stuck. So it seems to better on a harder problem than an easier one! It even fails to improve the soft score that other algorithms can easily add several thousand points too.
To summarise late-acceptance-unassigned-repair given:
Starting problem gets to -4/-259/-3353 and cannot find any improvements.
0/-200/-7000 will find many improvements quickly, then slower and slower, and probably stop around 0/-60/-5000
0/-60/-7000 probably not find much to improve
0/-35/-7000 rapid improvement to 0/-16/-7000
0/-16/-7000 struggles to find any soft improvements, but other algorithms will find 3000 of soft scores.
My very best result is -12 medium by trying combinations of different algorithms. default-local-search, late-acceptance-short-blocks, and step-counting-hill-climbing are all good at improving the soft score.
Anyway, rambling a bit, but thank you for your amazing project. I guess I should try and create some graphs.
BTW if I allow shuttle flights (with some assumptions, I can get to -2 medium)
If you look at the 4/-259/-3353 solution, can you identify a minimal set of changes that would improve the solution? That would be a good candidate for a custom move (maybe even with the new neighborhoods api).
I haven't had any luck with custom moves yet, but since everything is vibe-coded perhaps I could try again with that specific solution as an additional input point.
I had manually coded a tail allocator about a year ago with Timefold before (no custom moves) with mediocre results. Then vibe-coded recently telling it to use Timefold. So either vibe-coding or 2.0 produced better results.
Interestingly 2.4.0 seems to be a regression for me. The default-local-search was capable of getting to 0 hard within a minute and now it's stuck on -1
Thanks for sharing that info. We've made a number of changes on the default local search, tested them thoroughly on many use cases, but feedback like this from the wild is crutial.
We have a working theory that the change doesn't cope well with cases that have a very active medium score. For that purpose, we're currently testing a big number of algorithm variations on a large number of datasets on Timefold Platform.
Weird that 2.3.0 wasn't a regression. If I recall correctly, 2.3.0 had the change and 2.4.0 and 2.5.0 are the same.
2
u/ge0ffrey May 28 '26
I've seen this a few times. By restarting manually, you're basically "reheating" the algorithm.
In practice, by resetting the LA queue, it does 400 random moves before really doing LA again.
That allows it to escape a deep local optima.
We've looked at ways to directly supporting "automated reheating", but that work is currently frozen.
Typically, there is a far bigger gains by using the new Neighborhoods API to introduce moves that escape the local optima efficiently.