(This article was originally published at R – Xi'an's Og, and syndicated at StatsBlogs.)
A puzzle on The Riddler this week that ends up as a standard integer programming problem. Removing the little story around the question, it boils down to optimise
200a+100b+50c+25d
under the constraints
400a+400b+150c+50d≤1000, b≤a, a≤1, c≤8, d≤4,
and (a,b,c,d) all non-negative integers. My first attempt was a brute force R code since there are only 3 x 9 x 5 = 135 cases:
f.obj<-c(200,100,50,25)
f.con<-matrix(c(40,40,15,5,
-1,1,0,0,
1,0,0,0,
0,0,1,0,
0,0,0,1),ncol=4,byrow=TRUE)
f.dir<-c("=","=","=","=","=","=")
f.rhs<-c(100,0,1,8,4)
sol=0
for (a in 0:1)
for (b in 0:a)
for (k in 0:8)
for (d in 0:4){
cost=f.con%*%c(a,b,k,d)-f.rhs
if (max(cost)<=0){ gain=f.obj%*%c(a,b,k,d)
if (gain>sol){
sol=gain
argu=c(a,b,k,d)}}}
which returns the value:
> sol
[,1]
[1,] 425
> argu
[1] 1 0 3 3
This is confirmed by a call to an integer programming code like lpSolve:
> lp("max",f.obj,f.con,f.dir,f.rhs,all.int=TRUE)
Success: the objective function is 425
> lp("max",f.obj,f.con,f.dir,f.rhs,all.int=TRUE)$sol
[1] 1 0 3 3
which provides the same solution.
Filed under: Books, Kids, R Tagged: 538, cross validated, FiveThirtyEight, integer programming, The Riddler
Please comment on the article here: R – Xi'an's Og
