Solver can't get to better solution because of "gets better before it gets worse" logic...advice sought

[mikepictor]

I have a scenario where sometimes I end up with 2 tasks, one after another in a solver that is solving start times. The solution is ok, but not great, but it would be much better if task 2 came first, before task 1 (for various reasons, I will gloss over specifics). Being where it is is generating a fairly sizable soft constraint penalty. If it came first, it would be a much smaller penalty (or even maybe zero)

However if the tasks ever OVERLAP, then it generates a medium penalty equal to the number of minutes of overlap. So what I imagine is happening is that any time it tries to make task 2 come earlier, the soft penalty goes down, but the medium penalty goes up as the tasks start to overlap. The more they overlap, the larger the medium penalty. However, if it persevered until they no longer overlapped, things would be great, but I have to get over that hump of maximum overlap, and maximum medium penalty.

Is my thinking about the solver behaviour here at all realistic, and if so, what is the suggested way of handling this? The best idea I have is to always delete the old solution before trying again (rather than starting with the previous solve), and sometimes task 2 does come first and everything is great. It seems almost random if task 2 will come second or not.

[triceo]

Hello @mikepictor!

Local search is generally well-suited to handle these situation. Both Late Acceptance (the default algorithm in Timefold Solver) and Simulated Annealing are designed to pick worsening solutions in order to escape local optima, up to a point. However, sometimes the solver needs a bit of help to understand that some things only move together, or that particular situations are unwanted. This is a typical use case for custom moves.

In your case, your custom move would be to try to swap two tasks. If there is some logic in your business that tells you which two tasks it is beneficial to switch, even better; you get to avoid a lot of useless moves. But the more interesting question is: why would you even need to add this custom move? SwapMove already does that, and it is part of the default configuration of the solver. There's likely something else going on.

The fact that the solver didn't find a particular solution doesn't mean it couldn't. Given more time, perhaps it would've gotten there. Have you checked the best score graph? If you're not seeing a flat line there, it means the solver still has more to give.

Or perhaps you have a score trap with some of your other constraints, resulting in the solver getting stuck on a number of different solutions which all result in the same score?

Or perhaps you need a better configuration for local search, allowing the solver to be more adventurous in picking worsening moves. The benchmarker is your friend here.

I have given you several avenues to investigate, but in general, I don't think this is a problem we can solve here. We do not know your problem, and even if we did, investigating this kind of an issue is time-consuming and usually a job for consulting.

[mikepictor]

The solver is ending on its own, before it's maximum duration by hitting the unimproved-spent-limit, so it does feel it found as good a solution as it can. I am certainly looking at score traps, but I think I've caught them all (hard to know for sure), and my benchmarks look fine, but this is production data and it's always more complex than the test scenarios I've made up for benchmarking. I am not super familiar with how swap moves work, but since the tasks have different lengths, I worry that swapping them creates an overlap constraint if the second task is longer (since they now overlap), so maybe is seen as a bad choice, unless it experiments further after the swap and discovers it can distance them again. I ran the solution 5 times this morning, and in 2 cases the task was on the "right" side (and in fact, comes HOURS before the other task in this case), so I know it's capable of getting there. The soft penalty it is incurring is massive when it is stuck on the wrong side, so the scenarios where it comes where it should makes for such a better score.

I think I probably need to master the benchmarker more, I have mostly used it for constraint performance (and it's been very useful there). I am curious about your statement "allowing the solver to be more adventurous in picking worsening moves"...how do you work that into configuration? I don't even know of that as something subject to control.

[triceo]

I worry that swapping them creates an overlap constraint if the second task is longer (since they now overlap)

This could be a candidate for a custom move. To swap two in such a way that the overlap doesn't happen, or to only swap such that overlap can not happen.

[triceo]

The soft penalty it is incurring is massive when it is stuck on the wrong side, so the scenarios where it comes where it should makes for such a better score.

Seems like what you actually want is for tasks not to be stuck on "the wrong side". You seem to care a lot about this soft constraint; maybe it's not a soft constraint after all?