Search code examples
optimizationoptaplannertimefold

Retrieve problems for each assignment of planning variable

I'm working on a school scheduling application based on OptaPlanner that displays problems interactively during drag and drop:

enter image description here

I have naively implemented this by looping over every valid timeslot, assigning it to the lecture then retrieving the constraint matches for the resulting schedule using solutionManager.explain(schedule).getConstraintMatchTotalMap(). (I collect the errors in a map from timeslot to list of problems and return to front end.)

The problem

My problem is that with a couple of hundred lectures and 5-minute intervals (~500 timeslots), this becomes very slow. It takes about 5 seconds before the problems are fully computed for all positions.

I notice that during the CH phase, valid slots are computed insanely fast. I don't know a lot about OptaPlanner internals, but I suspect it's because it does incremental changes to the schedule, instead of starting all over for every lecture / timeslot assignment.

My question

Is there any way I can speed up this errors-by-timeslot scanning procedure?

My thoughts so far

If there's no first class support for this use case, I'm open to unholy hacks. I'm thinking of creating a custom solver, with a move list factory that feeds OptaPlanner with timeslot assigments for the dragged lecture, just to make the computation incremental. Is there a better way?!

After further research: Would it be possible to solve this using a custom phase? I.e. by calling changeWorkingSolution for each timeslot update? If so, how would I retrieve the current score explanation? Would I have to fiddle with SolutionUpdatePolicy?

Solution

  • I'm still not sure I understand the problem well enough. The following call indeed does not use incremental calculation, and therefore will be slow:

    solutionManager.explain(schedule).getConstraintMatchTotalMap()

    Hooking into ScoreDirector instead of SolutionManager could possibly get you closer to the bits that do incremental score calculation. (And outside the realm of public API.) That said, constraint justifications were never really optimized for performance; that feature is not designed to provide real-time information.

    The use case (as much as I understand it) does make sense though. We may yet do something about this in Timefold.