**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.