Score Analysis in an Over Constrained Planning Problem

[lepsch22]

Hey all,

I was wondering if there's a recommended way to perform score analysis in an over-constrained solution.

I've read through the Score Analysis section in the Timefold documentation, but I'm not sure it will fully addresses my situation.

My planning problem involves continuous scheduling, so I use unassigned @PlanningEntity instances to represent entities that would otherwise cause hard constraint violations. This means I often end up with unassigned entities when the solution is over-constrained due to numerous hard constraints.

I'd like to build a service that can tell someone what hard constraints were broken (even though they weren't technically broken as it only will break that medium unassigned constraint). From my understanding, the ScoreAnalysis tool would just indicate that the entity is unassigned and thus breaking the unassigned constraint, but it wouldn't explain the hard constraints that were broken.

So my questions are:

Am I misunderstanding the capabilities of the ScoreAnalysis tool?

Does anything exist (or is there a strategy) to help diagnose why a specific @PlanningEntity was left unassigned?

Has anyone encountered and addressed a similar challenge in over-constrained, continuous scheduling use cases?

Any insights or references would be greatly appreciated!

[triceo]

Hello @lepsch22!

The solver unfortunately cannot tell you why something didn't happen - the solver goes where the constraints tell it to go. Had the constraints been different, the score would have been different, and the solver would have taken an entirely different path, likely giving vastly different solutions.

If you want to see what would happen if the entity was assigned, use SolutionManager.analyze(...) and give it a solution simulating that situation; using score analysis, you can see which constraints it broke, and from that make some conclusions. However, that still isn't the perfect proxy for what you want, because the fact that such a solution exists doesn't mean that the solver would have found it.

[lepsch22]

Hey @triceo thanks for the quick response and sorry for my late response haha!

So if I did have a planning problem where the solver determined the PlanningEntity being assigned to a TimeSlot would break a hard constraint and it left the PlanningEntity unassigned what would be a good strategy to figure out as to why? Sounds like there isnt a good out of the box option so Im wondering if we could take that PlanningSolution take all assigned entities and one of the unassigned pin them all and then run the solve then analyze the score?

This was my first thought, if you think there might be a better way let me know. Trying to avoid having to make a tool where I have to duplicate the constraints and do a deterministic analysis on the unassigned PlanningEnitity to see the hard constraints that it may have broke.

[triceo]

@lepsch22 Answering the "why did the solver do something" question is very hard - one could argue it is impossible to say with certainty. There may be several reasons behind it:

• The solver did not do something, because doing it would have resulted in worse solutions than if it had done so. If you think these solutions are not worse, then you need to fix your constraints to tell the solver that. Otherwise if those solution are indeed worse, why worry about why the solver didn't pick them?
• The solver did not do something, because it did not encounter a combination of inputs where that thing would occur. It either needs to run for longer, or it needs to run faster, or it needs a larger move variety to explore different parts of the search space.

The first part is something you may want to look into. But the second part is not a problem in the constraints, or in the solver - it's a fundamental property of the metaheuristics used by the solver, that we can not guarantee we will find any particular solution in a finite amount of time. For that reason, this "why" question may not have a useful answer; you can do your absolute best, and it is still possible that a particular magical solution X will never be found.