an integer programming riddle

[This article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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


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:


for (a in 0:1)
for (b in 0:a)
for (k in 0:8)
for (d in 0:4){
  if (max(cost)<=0){ gain=f.obj%*%c(a,b,k,d) if (gain>sol){

which returns the value:

> sol
[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,
Success: the objective function is 425 
> lp("max",f.obj,f.con,f.dir,f.rhs,$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

To leave a comment for the author, please follow the link and comment on their blog: R – Xi'an's Og. offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)