Grouping a BiConstraintStream

[mikepictor]

I am hoping I can get some advice for how to frame this, because it's escaping me.

I have a series of Task planning entities, and a set of time intervals in my solution that I called a ShiftSlice that is marked with @ProblemFactCollectionProperty. What I need to do is add up all the tasks that overlap a given slice of time, to see if I have to many tasks at any one given point in time for a predefined limit (each slice has a property for the limit of that slice of time).

What I am trying to do (maybe wrongly) is

constraintFactory.forEach(Task::class.java)
            .join(
                ShiftSlice::class.java,
                overlapping(Task::startDateTime, Task::endDateTime, ShiftSlice::startDateTime, ShiftSlice::endDateTime)
            )
            .groupBy { _, slice ->
                slice,
                toList<Task>()
            }
...

This last part is where it is falling apart, and I am pretty sure I am approaching grouping incorrectly. Basically I want to get a given slice, and a list of all tasks that overlap that slice, so I can count them per slice and assign a possible penalty. I so see there is a sum collector, which i will have to explore (because ultimately that's what I am doing), but am I even approaching this in the right line of thought?

[mikepictor]

I should add, I have the constraint fully functional by grouping all tasks into one mega list and then looping it with all slices, but the benchmark tests show that it's just painfully slow, so I am trying to approach this in a more performant way.

[triceo]

You hit the nail on the head with performance - every time you see a collection inside of a constraint stream, you have given up on incrementality, and therefore on performance.

Iteration kills performance. We're looking for O(1) if we can get it, not O(n) or even worse.

[triceo]

Without having access to your codebase, I'm going to type up some Java code to solve your issue, hoping that you'll be able to adapt it to the specifics of your codebase:

.forEach(Task.class)
.join(ShiftSplice.class, overlapping(...)) // So far still identical to your example.
.groupBy(task, sum((task, splice) -> splice.getDuration()) // Results in BiConstraintStream<Task, Integer> 
.penalize(...)

This code will take all the splices overlapping a task, group them by task, and sum their durations.
The output tuple will carry a Task and an Integer sum of the durations of its splices, assuming the Splice::getDuration returns an int. (We also have sumDuration and sumLong collector variants for this use case.)

Side note: in the summation function, you'd be well-advised to only sum the actual overlap, and not the entire splice duration; that way, your penalty will better reflect the size of the actual breach of the constraint, and therefore help you avoid score traps.

[mikepictor]

yeah sorry, I am working in kotlin, but the format conversion isn't generally that hard. My slices are 5 minutes (tasks start every 5 minutes, so the 5 minute interval is always a start of a possible slice). I am not trying to add the duration, but the number of tasks (actually the number of assigned employees IN the task, but that shouldn't change anything)

I can sort that out, it's just the syntax of the grouping that eludes me. If I try your
groupBy(task, sum((task, splice) -> splice.getDuration())
even though it's not duration I want as such, but I can fix that later, but I just get Unresolved reference: task immediately.

I think I figured it out as a version of your line, with the following

.groupBy(
                { _, slice -> slice },
                sum { task, _ ->
                    task.assignedEmployees ?: 0
                })

This compiles, and streams what I expect (a BiConstraintStream with my ShiftSlice, and an Int), thank you. I don't think I would have quite unravelled that.

But my test fails because it just doesn't see the ShiftSlice objects. The solution has the annotation

@ProblemFactCollectionProperty
var shiftSlices: MutableList<ShiftSlice> = mutableListOf()

but ShiftSlice doesn't itself have an annotation (it's not a planning entity, it never changes). Does ShiftSlice have to be annotated with something?

[triceo]

No, problem fact classes don't need to be annotated - only the collection needs an annotation, as you did.

At the risk of stating the obvious, are you certain that some ShiftSlice instances are present in that collection? That is the most obvious explanation for what you're seeing - another explanation being a strange bug in a functionality that is battle-proven and used by many on a daily basis.

Also, how exactly are you testing this? If you're using ConstraintVerifier, then a planning solution doesn't even enter the picture. If you're not using ConstraintVerifier, then I suggest you start.

[mikepictor]

they are 100% there, I can see that in my debugger.

I am using ConstraintVerifier yes...but I am surprised by your statement the solution doesn't enter into it.

constraintVerifierTest.verifyThat()
            .given(
                solution, // <-- so...not useful?
                fillingTask1,
                fillingTask2,
                fillingTask3,
                splittingTask,
                splittingTask2
            )
            .scores(ofHard(-52), "Task assignment is not in Employee AvailabilityRange")

I changed it to

constraintVerifierTest.verifyThat()
            .given(
                fillingTask1,
                fillingTask2,
                fillingTask3,
                splittingTask,
                splittingTask2,
                * buildList {
                    addAll(schedule.shiftSlices)
                }.toTypedArray()
            )
            .scores(ofHard(-52), "Task assignment is not in Employee AvailabilityRange")

and it does run!!

and passes!!

if you're curious, my final constraint looks like

constraintFactory.getTasks(SPLIT, FILL)
            .join(
                ShiftSlice::class.java,
                overlapping(Task::startDateTime, Task::endDateTime, ShiftSlice::startDateTime, ShiftSlice::endDateTime)
            )
            .groupBy(
                { _, slice -> slice },
                sum { task, _ ->
                    task.assignedEmployees ?: 0
                })
            .penalize(ONE_HARD) { slice, cnt ->
                maxOf(0, cnt - slice.employeeLimit)
            }
            .asConstraint("Tasks exceed employee availability")

time to run my benchmark test, I'm expecting big things 😀

[mikepictor]

well, it's way faster (twice as fast?), but still my slowest constraint unfortunately. However it may be fast enough to justify the re-write I am doing. It is a rather big list (1 8 hour shift as 96 slices, but a few dozen tasks, so it's a fairly hefty join)

I'll think about whether I can see ways to try and tune that better. Thanks for all the help

[triceo]

Wrt. the solution - if you're using scores(...), then in fact yes, solution does enter into the picture. (I am quite surprised it works without it.) When I said solution is not relevant, I was expecting you're testing individual impact, not the score as a whole.