Causes of Score Corruption

[kentbill]

Hi,

I found a case for Score Corruption in Timefold presentations.

https://github.com/TimefoldAI/timefold-presentations/blob/63b0533992436e54922e6bc689a77bd6f88a06ad/events/2024-11-05-BYOM_score_calculation.html#L290

I don't understand its causes. Could someone explain why?

This constraint ensures that a task's start time is no earlier than the end time of its dependent task.

Why does using task.start < task.dependencyTask.end as a condition cause Score Corruption? However, finding a task and its dependent tasks using join and checking if the times are reasonable doesn't cause this exception?

.join(Task.class, equal(task -> task, task -> task.dependencyTask) .filter(task1, task2 ->task1.start < task2.end)

Many thanks!

[triceo]

This is a transitive score corruption.

Constraint Streams are incremental - meaning they only recompute constraints when something changes. In this case, task changes, and the solver will recalculate all the constraints where it is used.

What the solver won't do and can't do is to look inside your filter - the lambda is a black box to us. Because of that filter though, your constraint depends not only on task. It also depends on task.dependencyTask. And the solver doesn't know that.

What happens therefore is that the constraint will only be recomputed when task changes - and when the task that is reference by dependencyTask changes, the solver will not know, and the constraint will cause a score corruption.

The fixed constraint code solves the problem by explicitly declaring a dependency on the other task as well. That way, the constraint will be recomputed when either of them change, getting rid of any score corruptions.

[kentbill]

Okay, thank you so much for your detailed explanation! @triceo

I'm not sure if this is a correct understanding: when a task changes, the solver detects this and recalculates the score between the task and its dependencyTask. However, when the dependencyTask changed, the solver is unaware of this change between the task and its dependencyTask, and therefore cannot detect this action (in fact, their times have changed). Consequently, no recalculation of the score is triggered, and score corruption occurs.

[triceo]

Yep.