2
$\begingroup$

I am working on a workforce scheduling MIP -- given a set of shift candidates (different shapes and sizes of shifts created out of labor demand) and a set of workers, optimally assign the shifts under some hard and soft constraints (demand coverage, worker min weekly/daily hours, etc.). The worker-shift matching is done based on worker and shift tag sets (location, roles like cashier, clerk, etc., department, suborn, etc.). From my observation some instances of this MIP become pretty hard (many times takes a very long time in proving optimality) to solve while some others with similar configuration are quite easy. Is there a way to find out if a problem instance is going to be hard to solve beforehand? I suspect the tag interactions between workers and shifts and/or tag layout (worker having several conflicting tags and shifts having a large permutation set of tags) makes it easier or harder but not sure if there is a way to find that out or derive from the data.

$\endgroup$
2
  • 2
    $\begingroup$ Theoretically speaking, I think you could solve a gazillion test cases, classify them as "easy" or "hard", and use machine learning to look for predictors. Practically speaking, I don't think there is any easy way to know up front if your next instance is going to solve quickly or take a long time. $\endgroup$
    – prubin
    Commented Feb 7 at 20:26
  • $\begingroup$ Thanks. Going ML way sounds like a good idea, moreso as we already have a huge amount of customer data. But I was looking for some known predictors if any for the popular MIP techniques (Simplex+branch&bound, etc.). $\endgroup$
    – SDC
    Commented Feb 7 at 21:22

1 Answer 1

1
$\begingroup$

You could run a solver for a short time, to evaluate the score of that output on feasibility (broken hard constraints) or unassigned shifts, but even that will take solving time.

In practice, when scaling out in size or complexity, time-bound is typically better than score-bound: it's better to switch your mindset from "find the optimal solution" to "find the best solution in the available time", regardless if it's a 1 hour batch job at night or a 2-minute solving while a user is waiting for it (including real-time replanning for workforce scheduling). In the later case, make sure you show the intermediate score to the user that is waiting in front of the screen while it is solving.

Once you have that mindset in place, the next question becomes: How long should I solve? To answer that, create a score graph to plot the score (fitness function objective) versus time. Here's an example:

enter image description here

With that graph in hand, for a number of datasets, you can have a meaningful conversation with your business people (and those who pay for the cloud hardware costs) on how long it should solve. Is solving another 15 minutes for a 1% improvement worth it? It depends. And that's a business decision!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.