[R] Optimizing

[Gabor Grothendieck]

On Wed, Nov 14, 2012 at 8:23 PM, Sam Asin <asin.sam at gmail.com> wrote:
> Hello,
>
> I am fairly new with R and am having trouble finding an optimal group.  I
> checked the help functions for the various optimize commands and it was a
> little over my head.
>
> I have a dataset with 4 columns, name, type, value, and cost.  The set
> consists of a list of people, which have 3 types.  I want to choose 6
> people, two of each type, and maximize the sum of their values.  However,
> I'm subject to the constraint that the wage of the three people has to sum
> to less than 20 dollars.  Here is some sample data.
>
> people <- c("A", "B", "C", "D", "E", "F", "G", "H", "I")
> type<- c(1, 1, 1, 1, 2, 2, 3, 3, 3)
> value<-c(25.20, 24, 38, 20, 14, 20, 31, 11, 8)
> wage<- c(4, 3.8, 5.1, 3.5, 2.4, 3, 6, 2.4, 2)
>
> data<- data.frame(people, type, value, wage)
>
> With this small dataset the question isn't very interesting, but the answer
> would be something like person C, D, E, F, G, and I (I didn't check to see
> that those prices sum to less than $20).
>
> How can I write a program that will do this?  Can I just use the optimize
> command?  Do I have to transform my dataset into something that is easier
> to use the optimize command on?  Or should I write my own code that does
> the process?
>

This can be formulated as an integer programming problem. Note that
the proposed solution in your post is infeasible as it violates the
wage constraint.

library(lpSolve)

people <- c("A", "B", "C", "D", "E", "F", "G", "H", "I")
type<- c(1, 1, 1, 1, 2, 2, 3, 3, 3)
value<-c(25.20, 24, 38, 20, 14, 20, 31, 11, 8)
wage<- c(4, 3.8, 5.1, 3.5, 2.4, 3, 6, 2.4, 2)

con.mat <- rbind(type == 1, type == 2, type == 3, wage)
con.dir <- c("==", "==", "==", "<=")
con.rhs <- c(2, 2, 2, 20)
binary.vec <- seq_along(people)
out <- lp("max", value, con.mat, con.dir, con.rhs, binary.vec = binary.vec)
out$solution #  1 0 1 0 1 1 0 1 1
people[out$solution == 1] # "A" "C" "E" "F" "H" "I"
out # 116.2

# note: proposed solution in post violates wage constraint
proposed.soln <- c("C", "D", "E", "F", "G", "I")
crossprod(wage, people %in% proposed.soln) # 22


--
Statistics & Software Consulting
GKX Group, GKX Associates Inc.
tel: 1-877-GKX-GROUP
email: ggrothendieck at gmail.com