4
$\begingroup$

The standard nurse scheduling problem which is used as an example for OR-Tools (see for example https://developers.google.com/optimization/scheduling/employee_scheduling) attempts to assign boolean values to boolean variables in the following line of code:

shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))

For this toy problem, OR-Tools runs fine, but only 105 boolean variables are created (5 nurses, 7 days, 3 shifts $\Rightarrow 3\times 5\times7=105$ booleans to assign as to whether a given nurse works a given shift).

I'm exploring the use of OR-Tools to solve a more realistic real-world scheduling problem. For the real-world problem I'm dealing with, shifts are assigned in 15-minute increments and there are more workers and more roles involved. In the end, I end up with 11,064 booleans to be assigned.

Is this too many to expect OR-Tools to work realistically? I find that it quickly produces a (not very good) schedule but then even if I let it run for an hour it doesn't improve at all upon the initial schedule that it came up with in the first few seconds.

Is this typical behavior for OR-Tools? Any thoughts?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Not an answer to the question, but might help anyway: You could get the trial license for a commercial integer programming solver, see if it gets a better solution than or-tools in the desired execution time, and if the projected savings or value is worth the license cost. If not, you may want to review the literature and design or adapt a heuristic/metaheuristic solution. $\endgroup$
    – dhasson
    Aug 18, 2020 at 0:08
  • 1
    $\begingroup$ I second this. As a rule of thumb, the complexity of the problem typically increases exponentially in the number of boolean variables. So the real world problem may be much, much, much more difficult. For scheduling problems, constraint programming software such as ibm.com/analytics/cplex-cp-optimizer may also be useful. $\endgroup$
    – Kevin Dalmeijer
    Aug 18, 2020 at 0:57
  • $\begingroup$ Thanks Kevin and dhasson! $\endgroup$
    – David Ash
    Aug 19, 2020 at 17:31

1 Answer 1

Reset to default
4
$\begingroup$

There are no good answers to that question. It depends on the model, on the complexity of the problem. My gut reaction is that OR-Tools routinely solves to optimality bigger problems, but some much smaller problems can be impossible to prove, or even to find a feasible solution.

OR-Tools is a good CP solver (it won all 4 gold medals of the last 2 minizinc challenges). It is also a decent MIP solver (it closed 5 open MIPLIB 2017 instances and improved bounds on a few more).

I would suggest, or repeat the above suggestions:

  • compare to a commercial MIP solver (Gurobi, Cplex, Xpress) and try your luck.
  • compare to CPLEX CP-Optimizer. I would not expect it to be better following discussions I had with academic researchers who did the comparison, but this might be a problem when CPO performs superbly.
  • send your model to the or-tools users mailing list and ask for help or comments, in particular around the search parameters.
Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks to you and to Kevin and dhasson for your earlier comments. I discovered a bug in how I was setting up my constraints. I'm now seeing gradually improving results the longer I let it run. The performance is now probably sufficient for our immediate needs but we may try one of the other solvers mentioned as our problem becomes more complex, which it likely will. $\endgroup$
    – David Ash
    Aug 19, 2020 at 17:24
  • $\begingroup$ Can you add num_search_workers:8 to the sat parameters ? It will enable multi-threading that has usually a dramatic influence. $\endgroup$
    – Laurent Perron
    Aug 19, 2020 at 18:59

Your Answer

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

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