Mutual exclusivity variables in mixed integer programming problems

Question

I am working on a employee scheduling problems (assigning shifts to temporary workers) by modeling it as a MIP. There is a one shift per day constraint for the employees that restricts more than one shift per day. While doing that we have overnight shifts and need to take care of the day boundaries -- for example an employee working between 8pm on a day till 2am the next day can not start their shift the next day without having a rest time of x hours. So in summary, there are overlapping shifts and need to choose a single shift from the set of overlapping shifts. There can be multiple such overlapping groups for a single employee. We have modeled it as mutual exclusive constraints. But the problem is that in certain cases,the number of variables in such constraints is quite big (1000+) and these are all binary variables. So the problem is getting hard to solve pretty fast. I wanted to know if there is any other way to model this or can we simplify in any way. Thank you.

Answer 1

It will depend a bit on what language you're modelling in and what solver you're using. Some languages are designed for this kind of problem, for example in MiniZinc there are scheduling constraints so that you can directly specify that certain resources cannot be allocated to overlapping tasks or shifts (and you can incorporate rest times into those constraints as well).

If you don't have access to that kind of constraint, then you will have to find other ways to implement them, and unfortunately they are going to involve a lot of variables because scheduling is a complicated problem. One way to improve the efficiency of the program may be to add some redundant constraints - that is, introduce constraints that are already logically implied by the model that may help the solver to eliminate bad solutions more quickly. This might involve, for example, tightly bounding the total number of hours worked by all employees across all shifts.