I need to write up a model for a scheduling problem using linear integer programming. This goes well so far but I am stuck with one constraints that I do not know how to write up.
I will try to explain the problem with a small example.
Let us say that we have 3 destinations and for each destination we have to collect a number of interviews. We have 4 days to collect these interviews and each day there are three different shift (morning, midday and night). Our demand parameter is $d$
$d = \begin{bmatrix} 30\\ 55\\ 47 \end{bmatrix}$
SO $d_1=30$ tells us that after 4 days we need to have 30 interviews for destination 1.
Each day I can only assign one employee to one shift. (one shift can be assigned to several employees, so we can for example have two employees working in the morning at tuesday).
We need to know something about how good the employees are and for this we have $h_{i}$ which tells us how many interviews employee $i$ can collect during one shift.
$h = \begin{bmatrix} 60\\ 43\\ 26 \\ 30 \end{bmatrix}$
so we have 4 employees.
I assume now that we have 3 shifts each day (morning, mid-day and night) and we have 4 days to collect the interviews. We have the following matrices $A_k$ which tell us how many passengers there are at shift $j$ on day $l$.
$A_1 = \begin{bmatrix} 10 & 150 & 160 & 70 \\ 150& 0 & 1 & 40 \\ 40& 19 & 0 & 20 \end{bmatrix}$
$A_2 = \begin{bmatrix} 30 & 16 & 0 & 110\\ 15& 17 & 91 & 20\\ 10& 0 & 40 & 63 \end{bmatrix}$
$A_3 = \begin{bmatrix} 14 & 25 & 40 & 15 \\ 83 & 0 & 1 & 180 \\ 80 & 17 & 0 & 63 \end{bmatrix}$
so here $j = 3$ and $l = 4$, we have 3 shifts each day and we have 4 days. The matrix $A_k$ tells us how many passengers there are available to interview on shift $j$ on day $l$.
Now if I let $x_{ijlk}$ be the decision variable such that if $x_{ijlk}=1$ then employee $i$ does shift $j$ on day $l$ for destination $k$.
I write up the first constraint which states that only one shift is assigned to one employee per day and destination.
$\sum_{j=1}^3 x_{ijlk} \leq 1 \quad for \quad i=1,\ldots,4, l=1,\ldots,4, k=1, 2, 3$
So for example $x_{1111}=1$ says that employee 1 does shift 1 (morning shift) on day 1 for destination k.. but note that we can also have $x_{1112}=1$ so the same employee on the same shift and day does destination 2. This needs to be allowed because for example employee 1 can collect 60 interviews, so it does nok make sense that he collects 60 interviews from destination 1 when only 30 are needed and in fact he can only collect 10 because there are only 10 passengers available.
So what I first did was that I introduced variable $w_{ilk}$ which tells me how employee $i$ on day $l$ weighs destination $k$. I write up the constraint
$$\sum_{i=1}^4\sum_{j=1}^3\sum_{l=1}^4 w_{ilk} e_{i}x_{ijlk} \geq d_k \quad for \quad k =1,2, 3$$
now I know that $$\sum_{k=1}^3 w_{ilk} = 1$$ so he has to use his whole shift but spread it among the destinations (or maybe use the whole shift on one destination if he can).
Also note that
$$w_{ilk}e_{i}x_{ijlk} \leq A_{kjl} \quad for \quad i,j,l,k$$
since the amount of interviews collected on shift j at day l for destination k is restricted to the number of passegers available.
My problem is now that if I do it like this, then I have two variables multiplied and I cannot have that since the constraints have to be linear. Is there anyway to rewrite the two last constraints where $w_{ilk}x_{ijlk}$ is included?
Best Regards