Partial score calculation with bailout/shortcut

[ge0ffrey]

Currently, a score is always calculated entirely (all-or-nothing).
For example, when a move changes shift A to Beth, but Beth doesn't have the right skill for A, it will calculate all the hard and soft constraints.

So if there's 40 constraints, and the first 1 constraint breaks a hard constraint, it will still calculate 39 other constraints and then throw away the move. So maybe it can be made up to 40 times faster?

But it could be more:
Some constraints are cheap. For example forEach().filter().penalize().
Other constraints are expensive. For example forEach().join().join().filter().penalize().

We could run the cheap hard constraints first.
For each constraint, we know the number of join/groupBy/... nodes at bootstrap time.
For each constraint, we know the penalty, so we can filter out the hard ones.
It's far from perfect, but it can give a good enough automatic sorting of the constraints by estimated speed.

Why was calculateScore() always all-or-nothing?
Because it's a design decision that unfeasible moves can be foraged to escape local optima.
No idea if that ever happens. In this "partial score calc mode" this would be impossible.

So just bail out when a hard penalty occurs?
Not really. In allowsUnassigned=false (the default) cases, the output can be -123hard/-45soft, with the last 10 CH steps doing hard breaking moves all the time. That must still work.
So instead of bailing out when a hard impact happens, we should bail out only if the hard score gets worse AND if there is an initial solution (= in Local Search only, not in CH).

Would it always do partial score calculation?
No, score analysis and many other functions will keep calling a full (= normal) scoring. Probably all of CH too.

What if there are .reward(HARD)?
Don't do partial score calculations. You can't guarantee there won't be a false positive bailout. And you must!

Should we do it for medium too?
No. We have a design decision that Score.isFeasible() separates the score into. In HardMediumSoftScore, it separates the hard score from the medium+soft score. This applies to BendableScore etc too. Good thing we forces users to tell us that declaratively all those years ago.

How does incremental score calculation work if a bailout happens?
No idea yet. Good luck with that. :)

Current situation

interface ScoreDirctor {

    Score calculateScore();
    
}

Proposal A

interface ScoreDirctor {

    Score calculateScore();
    
    Tuple<Boolean,Score> calculateScoreWithBailout(Score minScore); // boolean is true if bailout happened because it guarantees a score below minScore
}

[triceo]

I am doubtful this could work. The fact that one hard constraint got worse doesn't mean some other constraint didn't get better with that same change. And that second improvement may positively outweigh the first negative impact. Therefore we would always have to run all the hard constraints, possibly eliminating recomputing soft constraints.

But even if it could work, I question the performance impact. To be able to do this correctly, each node would have to keep a memory of the inputs that have not been propagated to it yet (and which are going to have to be propagated eventually), and maintaining that memory throughout all the inserts, updates and retracts would bring a considerable amount of overhead on its own.

In order to prove or disprove this, CS would have to be pretty much rewritten, making for a very expensive PoC. I am not in favor of this.