Advice for a solver rewrite..

[mikepictor]

I am trying to understand some solver behaviour following a fairly big rewrite of my code. I had a solution that worked...mostly. Solutions were good, but often with a lot of caveats and occasional weird results. I have know for a while though that I had some very inefficient scenarios that I couldn't resolve without a rewrite. It would take 3 or 4 minutes to produce a solve that I usually could describe as "decent", but not often much better than that.

Without breaking it into massive detail, I had a Task with a start time planning variable and a value range provide with time intervals throughout the day, and it contained 1 or more TaskAssignment with an employee planning variable, and a value range provider with a pool of employees. Assignments would get assigned to employees, I'd evaluate things like minimum employee count, conflicts, etc...

It worked, but the complexity was massive. I changed my solver, and the main change was to scrap TaskAssignment entirely. Instead my Task now just as an assignedEmployees interger, and a value range provider of 1 up to my max limit. This allowed me to scrap 4 of my 10 constraints entirely, and speed up 3 of the others. The benchmark tool shows a problem complexity that is less than half what it used to be, and an entity count a third of what it was. Awesome

However, my solver now finishes nearly instantly (I have an unimproved-spent-limit of 20 seconds, and the solve finishes in 20.5 seconds). The resulting solution is very bad, conflicts all over the place. This is all reflected in the score, my solutionManager.analyze call shows every problem as a constraint match, so the score is clearly explained...but I don't know why it can't find a better solution. Why did it take half a second to get a bad solution, and then spend 20 seconds failing to improve it, so it stops there?

I could quote some actual entity structures here if it helps, but I mainly just want some inspiration as to what may cause it to just give up after getting a bad solution. It barely manages to resolve my hard constraints (sometimes...I've had hard penalties too, but they usually resolve), but I am getting a lot of medium constraints and a LOOOOOOOOT of soft constraints. It's like it's not really making an effort anymore.

[triceo]

Questions like this are impossible to answer without understanding the domain. And if we can see the domain, we often don't have the time to do an in-depth analysis of the issue. That's what paid consulting is for. That said, there are some things I can say in general:

• By reducing the search space, you sometimes introduce built-in hard constraints which can not be broken anymore. This may be a good thing, since you no longer do pointless moves. Or it may prevent the solver from making progress. YMMV.
• Many problems suffer from insufficient move variety. If the solver cannot reach the better solutions, it won't give any. Deep thinking may be required to come up with custom moves that help the solver explore the search space better. We've been providing more and more of these out of the box lately (K-Opt, Ruin & Recreate etc.), but problems often benefit from having a custom move that is tailored to the domain. (For example, if you always expect people with a particular skill on a particular shift, replacing the standard change move with a change move that understands this will bring benefits.)
• Sometimes the constraints are implemented so inefficiently that the score calculation speed is too low for the solver to efficiently crawl through the search space. Typically, this is on the order of thousands of scores per second.
• Sometimes the constraints implement score traps. If you can choose to penalize by the number of overlapping shifts, or by the number of overlapping minutes in those shifts, choose the latter. This makes the score more granular, and therefore reflects smaller evolutionary changes, helping the solver move forward.

As you can see, there are many things that could be wrong. To an extent, designing a good model is a combination of science and art.

[mikepictor]

Yeah, completely understood you can't just point out a fix, I am mainly trying to point my head in the right direction. My constraints are faster if anything (except one is slightly slower, but I am hoping the reduced entity count and problem scale makes up for that). I am indeed using overlap constraints that score per minute of overlap. I did notice that a 100% overlap is a fixed penalty in this case (EG a 10 minute task fully overlapping a 30 minute task can move back and forward inside that space with no score change). I changed that to go by proximity to start or date time (whichever is smaller) so any change should always produce some effect, but this small hold was in my old solution too, and my change didn't seem to fix much.

I don't have any custom moves, I am not sure how you even go about making them, maybe I have to read up on them. I did notice something that caught me off guard in

Solving ended: time spent (20130), best score (-16hard/-434medium/-458358soft), score calculation speed (21933/sec), phase total (2), environment mode (REPRODUCIBLE), move thread count (NONE).

Is move thread count (NONE) something that deserves attention?

How do I tell what move selectors I have? I don't have an XML config file, I am entirely SpringBoot powered setup, so I am supposing I have whatever move selectors come out of the box.

[mikepictor]

actually, if you'll indulge me, I noticed a bit of a pattern, and it directly relates to my change.

My brand new planning variable is this...

@PlanningVariable
var assignedEmployees: Int? = 1

@ValueRangeProvider
var employeeRange: List<Int> = listOf()

with the range being initialized afterwards (before we start solving) as a list of 1 to a max value (generally 2 to 4). So for example it would be a list of [1,2,3,4]

Most of the flaws of my solve can be summed up I think by assignedEmployees having a value of 1. Sometimes 1 is good, but sometimes it must be higher to solve other constraints. The constraints are computing, and they are scoring, and those scores would be improved with that number being higher. I think maybe my issue is in understanding the impacts of an list of Integers being my value range provider.

I did by the way try the IntValueRange available in Timefold, however there is an issue with my being a Kotlin project, there was a conflict between a kotlin Int, and a Java Integer, so that particular model didn't work.

[triceo]

Is move thread count (NONE) something that deserves attention?

It is an enterprise feature aimed at achieving higher score calculation speeds.

How do I tell what move selectors I have? I don't have an XML config file, I am entirely SpringBoot powered setup, so I am supposing I have whatever move selectors come out of the box.

Yes, in that case, you have the defaults. Which means you likely don't have pillar moves, but other than that, there aren't any generic moves that we could provide. Custom moves may be the way to go.

Although the fact that this issue apparently showed up after you significantly changed your model points me in the direction of newly introduced unbreakable constraints.

[mikepictor]

I found it.

My shadow variable wasn't told about my new planning variable. I had to turn TRACKED_FULL_ASSERT back on and it showed the score corruption. I added my new planning variable, now it runs normally.