[R] Binary optimization problem in R

[Hans W Borchers]

Michael Haenlein <haenlein <at> escpeurope.eu> writes:

> Dear all,
> 
> I would like to solve a problem similar to a multiple knapsack problem and
> am looking for a function in R that can help me.
> 
> Specifically, my situation is as follows: I have a list of n items which I
> would like to allocate to m groups with fixed size. Each item has a certain
> profit value and this profit depends on the type of group the item is in.
> My problem is to allocate the items into groups so the overall profit is
> maximized while respecting the fixed size of each group.
> 
> Take the following example with 20 items (n=5) and 5 groups (m=5):
> 
> set.seed(1)
> profits <- matrix(runif(100), nrow=20)
> size<-c(2,3,4,5,6)
> 
> The matrix "profits" describes the profit of each item when it is allocated
> to a certain group. For example, when item 1 is allocated to group 1 it
> generates a profit of 0.26550866. However, when item 1 is allocated to group
> 2 it generates a profit of 0.93470523. The matrix "size" describes the size
> of each group. So group 1 can contain 2 items, group 2 3 items, group 4 4
> items, etc.
> 
> I think this is probably something that could be done with constrOptim() but
> I'm not exactly sure how.

The task you describe is an integer optimization problem and can most likely
not be solved with a numeric optimization routine like constrOptim().

In the example above, the solution I get is a maximal profit of 16.31194
with these allocations:
    group 1:   4, 18
          2:   1,  9, 15
          3:   3,  6, 11, 12
          4:   8, 10, 16, 17, 20
          5:   2,  5,  7, 13, 14, 19

(mis)using the mixed-integer package 'lpSolve' in the following way
(with 100 binary variables):

    library("lpSolve")

    obj <- -c(profits)                  # we will look for a minimum
    dir <- rep("==", 25)                # discrete equality constraints
    rhs <- c(c(2,3,4,5,6), rep(1, 20))

    # Assign 2, 3, 4, 5, 6 items to groups 1--5 resp.
    mat <- matrix(0, 25, 100); mat[1,  1: 20] <- 1; mat[2, 21: 40] <- 1
    mat[3, 41: 60] <- 1;       mat[4, 61: 80] <- 1; mat[5, 81:100] <- 1
    # Assign each item to only one group
    for (i in 1:20) {
        mat[i+5, c(i, i+20, i+40, i+60, i+80)] <- 1
    }

    sol <- lp("min", obj, mat, dir, rhs, all.bin=TRUE)

    # RESULT
    -sol$objval                 # 16.31194
    # ALLOCATIONS
    which(sol$solution==1) - rep(seq(0, 80, 20), 2:6)
    # 4 18  1  9 15  3  6 11 12  8 10 16 17 20  2  5  7 13 14 19

In case you have thousands of items and many groups, packages like 'lpSolve',
'Rglpk', or 'Rsymphony' will not be able to handle the task and you might be
forced to look for tools outside the R realm.

Hans Werner