Search code examples
rlinear-programminglpsolve

select children for kindergarden group with binary linear programming

I have the following selection problem. I have some kids, each of them has some possible weekday-combinations when it could join a kindergarden group. Each weekday-combination has its own revenue (more days per week, more revenue). There are some restrictions on the maximum number of kids per weekday. Not every child has to be chosen . The aim is to maximize the total revenue. Here is an example dataset:

df <- data.frame(kid.nr=c(1,1,2,3,3, 3),
             kid.comb.nr=c(1,2,1,1,2, 3), 
             monday=c(0,0,1,0,1, 0),  
             tuesday=c(1,0,1,0,1, 0), 
             wednesday=c(0,1,0,0,1, 0), 
             thursday=c(0,0,1,1,1, 0), 
             friday=c(0,0,1,0,1, 0), 
             revenue.per.combn =c(100, 100, 400, 100, 500, 0)  )

# kid.nr 3 doesnt necessarily has to bee chosen

max.nr.kids.per.weekday <- c(1,2,3,2,1)

As far as I know, lpsolve could manage this binary linear progrmming problem? How could it be done? Especially, how do I cope with the fact that some kids have more than 1 posible weekday-combination, but each kid should only be considered once?

Solution

  • The first thing to do is to develop a mathematical model. This can look like:

    enter image description here

    Then you need to implement this into R. I would suggest using the OMPR package.

    Basically the wrinkle is the following: we have binary variables x(i,j) where i=kids and j=daycombinations. Now x(i,j) is somewhat "ragged": it does not exist for all i,j. E.g. i=kid 2 has only one j. This type of thing can be handled by OMPR (they call this a "filter").