Simplified nurse scheduling problem I'm currently handling a project with a problem that is very similar to nurse scheduling problem in many respects. It is a part time workforce scheduling system whereby we need to determine which staff is most suitable to work on that a particular day in a course of 30 days. There are a few constraints:
Hard constraints


*

*10 staffs will be hired 

*only 5 staffs are required to work in a day

*each staff could only work for a maximum of 20 days 

*in a month there will be some days where the staff has indicated that they could not
work due to inavailability


Soft constraint


*

*there will be also some days where the staff is less preferred to
work on that day


I was suggested to use linear programming to build this project however I don't see how mathematics can be applied in this case. However, I could be wrong. In that case can anyone point me to the right direction as to what method or techniques should I be using to solve this case?
 A: This could also be modeled as a max flow problem. Model a bipartite graph with the two disjoint sets $U$ (the staff) and $V$ (the days of the month). Connect now each staff node $u \in U$ with each day $v \in V$ he is willing to work with an edge with capacity 1. 
Connect all $u \in U$ with the source with the capacity 20 (the maximal day a person is allowed to work) and all $v \in V$ with the sink with the capacity 5 (number of staff required for the day).
If you can solve this max flow problem with a maximum flow of $days * 5$ a solution for the problem exists. If not you might remove the soft constraints one by one (which means add edges between $U$ and $V$)  
A: One way of formulating this as a linear program is to create one binary variable for each worker-day: $x_{i,j}$ represents worker $i$ working on day $j$, where we constrain $0\le x_{i,j} \le 1$ (eventually we will force $x_{i,j}$ to be either 0 or 1, but let us leave them as real numbers to start out.
The constraint that worker $i$ works at most 20 days is
$$\sum_j x_{i,j} \le 20$$
and the constraint that there are at least 5 workers on day $j$ is
$$\sum_i x_{i,j} \ge 5$$
we can force a worker to not work on a given day by setting $x_{i,j}=0$
The soft constraints can be handled as part of the objective  Let $c_{i,j}$ be a measure of how little a worker wants to work that day, with $c_{i,j}=1$  being a normal day and $c_{i,j}=n$ being that worker $i$ would rather work $n$ normal days instead of just working that day.  So our objective would be to minimize
$$\sum_{i,j}c_{i,j}x_{i,j}$$.
Now it it possible, even probable, that after solving this not all the variables will be 0 or 1.  The easiest thing to do is to constrain a variable that is close to 0 or 1 to 0 or 1 and resolve.  In a problem this small a computer will get a solution in microseconds.
