Hi, I have a problem I've been trying to think of an appropriate way to frame for several days, and I can't quite get it correct. The issue is as follows: I have a set of 20 days and some number of employees, which we'll call Y. There is a separate variable for each employee on each day (10_1 would be a binary for employee 10 worked on day 1). I need to impose a constraint such that IF the employee was scheduled to work 5 days or fewer, then those 5 days MUST be spread apart by 4 days. In other words, they would have to work on day 1, 5, 9, 13, 17. Or they could work on day 2, 6, 10, 14, 18. Or if they're working only 3 days it could be 1, 8, 19. However, IF the employee is scheduled to work more than 5 days, then 5 of those days still must follow the constraint mentioned previously, but the rest of the days can be anywhere. I believe I have a way to solve the case where it's 5 or more days by setting an indicator variable to 1 if they're working more than 5 days, and another indicator equal to 1 if one of the possible 4spaced subsets are completely filled. Then those two indicators can just be set equal as a constraint. However, the case where it's fewer than 5 days is not as straightforward to me, because now I don't necessarily know the spacing without making every single combination of variables, which would just blow up. Any ideas would be appreciated! asked 10 May '15, 11:08 napaman56 
"Spread apart by four days" sounds like "must have at least three off days between work days" to me. Suppose that we let binary variable \(x_{w,t}\) be 1 if worker \(w\) works on day \(t\), and let binary variable \(y_{w,t}\) be 1 if worker \(w\) starts a three day break on day \(t\). We need to ensure that workers do not work during breaks, which can be done with the constraints \( \sum_{t=\tau  1}^{\tau + 1} y_{w,t} + x_{w,t} \le 1 \forall w, t \) (with the usual finagling of indices that are out of bounds). These constraints also preclude two credited breaks overlapping. Now we need to ensure a sufficient number of breaks, which if I'm interpreting your question correctly would be \(\min(4, z_w  1)\) where \(z_w = \sum_t x_{w,t}\) is the number of days \(w\) works. That's going to require another binary variable \(u_w \), which will be 1 if \(z_w \ge 5\), with the constraints\[\begin{aligned}z_{w} & \le4+16u_{w}\\ z_{w} & \ge5u_{w}\\ \sum_{t}y_{w,t} & \ge4u_{w}\\ \sum_{t}y_{w,t} & \ge z_{w}120u_{w}. \end{aligned}\] answered 10 May '15, 15:47 Paul Rubin ♦♦ While "at least three off days" makes sense from a practical point of view, in my interpretation, there have to be exactly 3 days off, iff there are at least 5 working days.
(12 May '15, 04:06)
rschwarz
You could interpret the original statement that way, but it would be odd to mandate exactly three days off when working five or more days but accept longer breaks when working fewer days (as in the 1, 8, 19 example). We'll have to wait for the OP to clarify.
(12 May '15, 10:38)
Paul Rubin ♦♦

In the constraint programming community, there is the concept of the regular global constraint. It enforces patterns (e.g., of work, break) that can be represented as regular expressions. The implementation uses a finite (deterministic) state machine that is then "timeexpanded" to yield a network flow model. This model can be used as is in a MIP model (or LP relaxation). Have a look at the paper Modeling the Regular Constraint with Integer Programming by LouisMartin Rousseau and others. From the abstract:
answered 12 May '15, 04:12 rschwarz For ease of notation, let's assume that your rule of 4spaced working days applies for shifts with at least 3 working days. A regular expression modelling your constraint could then be: (b*)(b*wb*)(b*wb*wb*)(b*(wbbb)*b*) Here, "b" denotes a break, while "w" denotes a working day and "*" denotes repetition (at least 0 times). The first three terms of the disjunction "" cover the cases of 0, 1, or 2 working days. The last term covers 3 or more working days, using the pattern of exactly 3 days off between working days.
(12 May '15, 04:18)
rschwarz

I would introduce an additional index for the variable, i.e. \(x_{92}^1\) means that the the first working day of employee 9 is day 2, \(x_{92}^2\) means that the second working day of employee 9 is day 2 etc. Once you have these variables, you can impose conditions that make sure that the difference between the first and second working day is at least 4, second and third is at least 4 and so on. For the sixth, seventh and so on working days, you impose no conditions so that they can be placed arbitrarily. Furthermore, you need conditions of the form \(x_{92}^1 \geq x_{92}^2 \geq x_{93}^3\) to make sure that the working days are assigned in the designated order. answered 10 May '15, 15:53 JF Meier 
Thanks for the answer. I think I may have not emphasized part of the problem enough in that it should be easy to frame the part of a worker cannot work without at least a 3day break after working for one day. The way I'm currently modeling this is to have indicators for each worker that indicates whether the following is equal to 1: if d1+d2+d3+d4 = 1 => y1 = 1 if d2+d3+d4+d5 = 1 => y2 = 1 etc Then iff the employee worked 5 or more days, the following condition must hold: sum(y_i) >= 1 If they worked fewer than 5 days, then sum(yi) = sum(di) In other words, the number of days they're scheduled to work must be the sum of the indicators of unique 4day spaced sets. Does that make sense? rschwartz, I don't think Gurobi support constraint programming, right? If I switch to CPLEX I could look at that, but I'm not currently using it. answered 12 May '15, 17:10 napaman56 You don't need a Constraint Programming solver for the approach using the regular constraint. Indeed, the linked paper is all about the formulation as an integer program.
(13 May '15, 03:45)
rschwarz

"IF the employee was scheduled to work 5 days or fewer, then those 5 days MUST be spread apart by 4 days". Do you mean 5 days or more?