Comment by binarymax
11 hours ago
A loonnngggg time ago when I was green, and wasn't taught about constraint solving in my State University compsci program, I encountered the problem when trying to help a friend with his idea.
He wanted to make an app to help sports club owners schedule players for the day based on a couple simple rules. I thought this was going to be easy, and failed after not realizing what I was up against. At the time I didn't even know what I didn't know.
I often look back on that as a lesson of my own hubris. And it's helped me a lot when discussing estimates and timelines and expectations.
This might be a dumb question (as I'm not familiar with constraint solvers) but would a linear optimization approach be better? I've used linear optimization for scheduling in the past. The nice thing is that linear optimization handles rule conflicts well, because you just set weights on all your rules and the optimizer will find the "least bad" solution to the conflicts.
This is what major sports leagues use for season scheduling (source: https://mathstodon.xyz/@j2kun/108975072813565989)
Well if your using MiniZinc you're free to use a CP solver, MIP solver, SAT solver, CP-SAT-LP solver. In general the model is roughly the same, even though some formulations work better for some solvers than others.
But CP (and CP-SAT) solvers tend to do very well on scheduling problems
> I thought this was going to be easy, and failed after not realizing what I was up against. At the time I didn't even know what I didn't know
This reminds me of high school ~25 years ago when I just started learning TI-Basic on my calculator and was dabbling in VB6 on my PC, and I was flipping burgers at Steak n Shake as my part time job. The manager moaned about how hard it was to write the employee schedules out each week (taking into account requested days off, etc) and I thought “ooh, I know how to write software now, I’ll make a scheduling program!” I told the manager I bet I could do it.
… it took a very short time for 16 year old me to realize writing scheduling software to solve for various constraints is pretty damned hard. I never brought it up after that.