set covering problem (2009-7-13)

<pre> we have a set coverage problem with N variables x[i,j,k] where x[i,j,k]=1 means that employee I on day J covers shift K (and viceversa). Domains are: i=1..NEmp j=1..NDay k=1..NShf We introduce the new array Coverage[j,k]=x[1,j,k]+x[2,j,k]+...x[NEmp,j,k] so Coverage[j,k] gives the total number of employees that work shift k on day j. We are given an array of integers OptimalDist: array[1..NDay,1..NShf] of integer where OptimalDist[j,1..NShf] gives the optimal coverage of employees on day J To make things clear, OptimalDist[j,1]+OptimalDist[j,2]+ ..OptimalDist[j,NShf]=NEmp for each J Along many other conditions to satisfy (that we wont discuss here), we want to enforce the condition that the coverage we get on day J is as close to the (relative value of) OptimalDist as possible. Due to the many other conditions we have to satisfy, it is likely that we WONT get the exact distribution OptimalDist, but we want to go as close as possible to it. In a ideal free math world, we would pass the solver the classic chi-squared formula: minimize ( Coverage[j,1]-OptimalDist[j,1] )**2 + ( Coverage[j,2]-OptimalDist[j,2] )**2 ... ( Coverage[j,NShf]-OptimalDist[j,NShf] )**2 Alas, we cannot do it: our solver only accepts linear equations. This means that abs, squared, etc functions are not allowed. Inequalities allowed are only of type: Ax[...]+Bx[...]+Cx[...]+... >= RHS or Ax[...]+Bx[...]+Cx[...]+... <= RHS or Ax[...]+Bx[...]+Cx[...]+... = RHS Coefficients are integers (but this condition can be relaxed). Which inequalities can we pass to the solver (in place of the chi-squared function) so to get coverage close to the wanted distribution ? I am not interested in a particular modelling language. Please use any modelling language you are comfortable with. Please note that _no code_ at all is required. We only need a suggestion re how to write the problem in linear form </pre>