I am making a solver to choose the best assignment to a set of people for an event, given their availability (chosen in a set $T$ of time slots), jobs preferences (among $J$ possible jobs) and some of other predefined constraints. We refer to a particular pair of (job, time slot) as a shift.I'm not optimizing the entire workforce at once but instead I assign one person at a time.* Here's an overview of how I modeled the sub-problem:Enumerate the set $S$ of all possible shifts ($|S| = |J|\times|T| = 90$ in my case)Use an objective function related to the number of people already assigned to each shift (and the need for that shift)Find solution $x \in \{0,1\}^{|S|}$ that associates to each element of $S$ a value in $\{0, 1\}$The constraints are the following:Each person can be assigned up to N shifts (depending on their preference)Up to 2 shifts during the same dayNo consecutive shifts except when the job remains the sameEach person can do only up to two different jobs during the entire eventI managed to encode all the constraints as a linear program except the last one. Any idea on how that could be done ? If that is not possible at all (which I suspect), what tool can I use to solve this problem ?* I know that is sub-optimal, but finding a better algorithm will probably be the subject of another question ;)
Choose N pairs of (job, time slot) with a constraint on the number of different jobs
optimization;linear programming;integer programming
The last constraint is also no problem. You already have variables $x_{j,t}$, that say if the person works the $j$th job on the time slot $t$. Now you can introduce new binary variables $y_j$, that represent, if the person works at the job $j$ or not. Then you can model the constraint by:$$\sum_{j \in J} y_j \le 2$$The only part left is how you connect the information from the $x_{j,t}$ with $y_j$. But that is also not hard. If any of the $x_{j,t}$ is $1$, then you can force $y_j$ to also be $1$ with the constraints$$y_j \ge x_{j,t}\qquad\forall t \in T, \forall j \in J$$and force $y_j$ to $0$ if all $x_{j,t}$ are $0$. This can be done with:$$y_j \le \sum_{t \in T} x_{j,t}\qquad\forall j \in J$$