Matching a general element-wise pattern using the consecutive sequences collector

[tomashauser]

Let us consider an instance of Nurse Rostering problem with a Shift as a planning entity and Employee as a planning variable. It is not unusual to want the consecutive shifts to adhere to a specific pattern. For example, an employee may want to avoid a (NIGHT, DAY) pattern due to sleep schedule adjustment issues, or perhaps prefer (NIGHT, BREAK, DAY) for the same reason. To avoid fixating specifically on day patterns, we may simply give each shift a tag and penalize/reward an occurrence of specific consecutive subsequence of tags within an employee's schedule, possibly including breaks.

In the incubator-kie-optaplanner project we may find a surprisingly awkward approach to this, using a dot product over the set of all shift assignments:

Constraint unwantedPatternShiftType2DaysPattern(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(PatternContractLine.class)
            .filter(patternContractLine -> patternContractLine.getPattern() instanceof ShiftType2DaysPattern)
            .join(ShiftAssignment.class,
                    Joiners.equal(
                            contractLine -> ((ShiftType2DaysPattern) contractLine.getPattern()).getDayIndex0ShiftType(),
                            ShiftAssignment::getShiftType),
                    Joiners.equal(PatternContractLine::getContract, ShiftAssignment::getContract))
            .join(ShiftAssignment.class,
                    Joiners.equal((contractLine, shift) -> shift.getEmployee(), ShiftAssignment::getEmployee),
                    Joiners.equal((contractLine, shift) -> shift.getShiftDateDayIndex() + 1,
                            ShiftAssignment::getShiftDateDayIndex),
                    Joiners.filtering((contractLine, shift1, shift2) -> {
                        ShiftType2DaysPattern pattern = (ShiftType2DaysPattern) contractLine.getPattern();
                        return pattern.getDayIndex1ShiftType() == null
                                || shift2.getShiftType() == pattern.getDayIndex1ShiftType();
                    }))
            .penalize(HardSoftScore.ONE_SOFT,
                    (contractLine, shift1, shift2) -> contractLine.getPattern().getWeight())
            .asConstraint("unwantedPatternShiftType2DaysPattern");
}

They also support a three-day-pattern in the same manner, they just use a third join.

When I saw that, I was glad we have the ConsecutiveSequencesCollector which presumably uses an efficient algorithm under the hood to provide the consecutive sequencues, and allows us to approach problems of this kind with a more general approach. My idea was following:

Constraint unwantedShiftPattern(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(Shift.class)
            .filter(shift -> shift.getEmployee() != null)
            .groupBy(Shift::getEmployee, ConstraintCollectors.toConsecutiveSequences(Shift::getEpochDay))
            .flattenLast(SequenceChain::getConsecutiveSequences)
            .join(ShiftPattern.class)
            .map((employee, seq, pattern) ->  countOccurencesOfPatternWithinSequence(employee, seq, pattern))
            .penalize(HardSoftBigDecimalScore.ONE_SOFT, (occurences) -> occurences)
            .asConstraint(SchedulingConstraint.UNWANTED_SHIFT_PATTERN.getLabel());
}

however, when I tried to extract the actual items from the ai.timefold.solver.core.api.score.stream.common.Sequence, I realized it won't let me. The seq.getItems() only returns the items before the first break, and then, there are only ai.timefold.solver.core.api.score.stream.common.Breaks which only expose the last item of the previous break and the first item of the next break. This is not enough information to extract the number of occurences of the pattern.

Then I resorted to simply going through the list of all shifts for each employee, yielding an awful O(n log(n)) constraint due to the need to also sort the array:

Constraint unwantedShiftPattern(ConstraintFactory constraintFactory) {
    return constraintFactory.forEach(Shift.class)
            .groupBy(Shift::getEmployee, ConstraintCollectors.toSortedSet((Comparator.comparing(Shift::getStart))))
            .join(ShiftPattern.class)
            .map(ShiftPatternMatcher::findMatches)
            .penalize(HardSoftBigDecimalScore.ONE_SOFT, (occurences) -> occurences)
            .asConstraint(SchedulingConstraint.UNWANTED_SHIFT_PATTERN.getLabel());
}

There has to be a better way of doing this. Am I missing something? Why are you not exposing the whole sequences? Is it because the underlying algorithms wouldn't be as fast? Thank you for any insights.

[triceo]

Hello @tomashauser!

Why are you not exposing the whole sequences?

We are. SequenceChain has all the ingredients, but your flattenLast chooses to look at each Sequence individually.

.groupBy(Shift::getEmployee, ConstraintCollectors.toConsecutiveSequences(Shift::getEpochDay))
.flattenLast(SequenceChain::getConsecutiveSequences)

This often works well, because we typically want to look at numbers of shifts in sequence. For detecting complex patterns which need to span breaks too, you currently have no other option than to go through the entire SequenceChain and search for the specific pattern.

This operation will not be incremental and therefore not perform optimally, but that won't matter much for short chains. (Planning window for these problems typically isn't too long.)

[Christopher-Chianelli]

Depends on the JVM you are using. If the method references are the same instance (i.e. a == b), and the constraint stream has the same prefix, then the node will be shared. The Enterprise edition has a feature to rewrite the bytecode to guarantee identical functions share the same instance (see https://docs.timefold.ai/timefold-solver/latest/enterprise-edition/enterprise-edition#automaticNodeSharing).

[triceo]

@tomashauser I wouldn't expect such a JIT optimization here - for a basic explanation of how CS works, you can look up the RETE algorithm, which CS takes heavy inspiration from.

Your findings are puzzling. Joins are yet another feature where the benefits will only show on larger datasets - building and rebuilding the indexes does bring significant overhead, and only outperforms simpler techniques at scale. One thing to try:

return constraintFactory.forEach(Shift.class)
          .join(Shift.class, 
              equal(Shift::getEmployee), 
              lessThanOrEqual(Shift::getEnd, Shift::getStart),
              filtering((shift1, shift2) -> shift1.getHoursDistanceFromShift(shift2) < MIN_BREAK_HOURS_BETWEEN_SHIFTS))

This will make the filter part of the join, and therefore could make the join somewhat smaller. The key to max join performance is to minimize the cross-product.

That said, judging JVM performance is really tricky without hands-on access to the codebase and the workload - you're probably well aware of that yourself.

Side note:

constraintFactory.forEach(Shift.class)
.groupBy(Shift::getEmployee, ConstraintCollectors.toSortedSet((Comparator.comparing(Shift::getStart))))
.something(...)

If all 3 constraints look like this, and exactly like this (same lambda instances even), CS will be able to node-share the common part. And therefore the groupBy would only be executed once, even though it is part of 3 constraints. In Community Edition of the Solver, you need to ensure this manually - the Enterprise Edition does some bytecode tricks to make sure this happens automatically where possible. (Which Chris just wrote in his comment, while I was writing mine. :-))

[tomashauser]

I found a score corruption. Will report later if anything changed.

[tomashauser]

Nevermind, it was just one corrupted dataset. I'm pasting my original comment below.

The Enterprise edition has a feature to rewrite the bytecode to guarantee identical functions share the same instance

Cool! Although one could argue that's an example of a leaky abstraction; although I undestand that this is for the most demanding users. There is a point, where we might be better off just implementing the raw incremental solver or even used ILP or other approaches.

I wouldn't expect such a JIT optimization here

Well then one could join the while/foor loops manually by merging the two constraints. I wouldn't mind that if it significantly improved my score calculation speed. The only thing stopping me right now is that one condition is medium, while the other is soft. I suppose there isn't a way to join them like that. Although I could squeeze a few thousand there as well...

Your findings are puzzling.

Are they though? I keep adding stuff to the same node as opposed to adding up the cost of consecutive sequences calculation which I would traverse it regardless.

This will make the filter part of the join, and therefore could make the join somewhat smaller. The key to max join performance > is to minimize the cross-product.
True, I forgot that there is also filtering. Here are some numbers:

Problem Size	Loops (Operations/s)	Smarter Join (Operations/s)	Difference (Operations/s)	% Difference
30 nurses, 1 location	66,543/s	62,589/s	3,954/s	+6.3%
100 nurses, 1 location	68,062/s	70,113/s	-2,051/s	-2.9%
200 nurses, 5 locations	64,727/s	61,029/s	3,698/s	+6.1%

I guess we could say they're about equal. It's frightening how such a small thing like using filter vs filtering can cost you 30 % on performance. Although it's 100% skill issue on my part.

To see if your idea holds, I also ran the 200-nurses-5-locations on maxConsecutiveDays with consecutive collector and got only 50k/s. The score graph looks kinda concerning though. Seems like its kinda climbing up, and maybe with a giant dataset, it would eventually surpass the loops but that's really beyond the scope of most users I would say. It also seems much more unstable than the graphs from other test runs.

I will eventually get to parsing data from NRP competitions and actual hospital data, so we will see there, maybe my demo data generator is doing something stupid. Will keep you notified.

Lastly, I wanted to create a nice comparison but I can't, for the love of God, get your benchmark aggregator to work. Do you still maintain that? Looks kinda ancient.

[triceo]

Wrt. the aggregator - it is truly ancient, and it does not have any test coverage. We recently had some fixes from another user to this code, and they will be released in June. If you still see issues after the release, please report them. I'm not personally using the aggregator, but as long as it is part of the codebase, we will fix bugs reported.