2
$\begingroup$

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 day
  • No consecutive shifts except when the job remains the same
  • Each person can do only up to two different jobs during the entire event

I 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 ;)

$\endgroup$
2
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ Awesome, thanks a lot ! I'm not used to LP so I would never have found this trick myself. Great to how one's can shift its view of this kind of problems. $\endgroup$ – Simon Aug 11 '17 at 9:25
  • 1
    $\begingroup$ You're welcome. This trick can be used in a variation of different topics. I know it from graph problems (MST, TSP, ...) where you have constraints on the edges, but then also want to apply some additional constraints on the vertices. $\endgroup$ – Jakube Aug 11 '17 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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