What are potential reasons for high move count per step for "easy" problem instances?

[greyhairredbear]

Context

We have used Timefold (currently version 1.10.0) to model a capacitated VRP with pickups, deliveries and time windows. To move loads from one vehicle to another, we use custom composite moves created with a MoveIteratorFactory to move pickup and dropoff actions of a load together (to avoid pointless hard constraint violations where related pickup or dropoff actions would end up on different vehicles).

For termination, we use unimprovedStepCountLimit (which is admittedly quite high), which actually works quite well for our purposes. However, we noticed some unexpected behavior lately. For rather "easy" problem scenarios (e.g. picking up two loads from two different locations), the solver takes very long, sometimes running until our minutesSpent termination kicks in.

If the problems are just a little bit more complex (e.g. delivering 7 loads to different locations), the solver exits after a comparably short amount of time (a few seconds to maybe half a minute).

Investigation & Findings

For the scenario with two loads, the unimprovedStepCountLimit is never reached. The problemScale in the benchmark report is at 2.079.181. For the other scenario, the solver stops after reaching the unimprovedStepCountLimit. problemScale is 14.426.130.

Interestingly, the "Move Count per Step" statistic (UPDATE: for moves selected) is between 900 and 3000 for the problem instance with two loads, while it is between 50 and 200 for the other one. For reference, here is the output from the benchmarker:

"Easy"

"A little less easy"

Questions

• Has this behavior been experienced by other users before? If so, what are potential reasons?
• Could this possibly be linked to our implementation of the MoveIteratorFactory classes? To be more concrete, I speculate there could be an error in our implementation of hasNext, which could return true too often, causing the solver to unnecessarily create moves for too long.
• A bit unrelated, but are there some good guesses/heuristics of how to choose an unimprovedStepCountLimit? My first approach would be gathering more data when doing benchmarking and then lowering this limit accordingly. However, this would only mitigate the issue a little bit - the less complex problem would most probably still run longer than the other one.

Closing remark
Since this currently occurs only on problem instances that are solved by a human quite easily, it's currently not a big issue for us. Just wanted to figure out what's causing this behavior and if we might have an underlying issue in our code.

[triceo]

Hello @greyhairredbear,

Has this behavior been experienced by other users before? If so, what are potential reasons?

I have not seen this behavior before.

Could it be that with the smaller problem, there were many more moves which were not doable, therefore forcing the solver to generate many more moves inside the step? It's the thing that immediately comes to mind that would cause the solver to generate meaningfully more moves.

Could this possibly be linked to our implementation of the MoveIteratorFactory classes? To be more concrete, I speculate there could be an error in our implementation of hasNext, which could return true too often, causing the solver to unnecessarily create moves for too long.

As far as I know, the solver only generates moves until it has just enough to satisfy the accepted count limit.

A bit unrelated, but are there some good guesses/heuristics of how to choose an unimprovedStepCountLimit? My first approach would be gathering more data when doing benchmarking and then lowering this limit accordingly. However, this would only mitigate the issue a little bit - the less complex problem would most probably still run longer than the other one.

Generally, unimprovedStepCountLimit is intended to help with debugging and testing the solver. It allows the user to terminate the solver in a predictable reproducible stable, which a time-based termination wouldn't be able to guarantee. The step count family of terminations was never intended for use in production.

[greyhairredbear]

Hi, thanks for the (once again) quick reply!

Note on what I forgot to mention in the original post: The accepted count limit is at 1 (I suppose the default for the default local search, late acceptance iirc), so the move count per step statistic I was referring to is the selected statistic. I'll update the original post. But I think this probably doesn't make any difference.

Thank you for the hint, this sounds quite reasonable, so I'll investigate in that direction.

Generally, unimprovedStepCountLimit is intended to help with debugging and testing the solver. It allows the user to terminate the solver in a predictable reproducible stable, which a time-based termination wouldn't be able to guarantee. The step count family of terminations was never intended for use in production.

That is quite an interesting point and piece of information. We're currently using this more or less for the reason you've mentioned, for getting comparable results across different environments (currently, we're planning very problems on AWS lambda and delegating more complex problems to AWS Fargate, which is a lot faster, but has some startup overhead).

Regarding the termination, I have a followup question I'll post in a different discussion.