# maximum number of BoolVar 's before or-tools is no longer feasible to use

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?

• 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. – dhasson Aug 18 '20 at 0:08
• 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. – Kevin Dalmeijer Aug 18 '20 at 0:57
• Thanks Kevin and dhasson! – David Ash Aug 19 '20 at 17:31