an integer programming riddle

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.

12 Responses to “an integer programming riddle”

  1. Cheers for the inspiration; I took a dplyr approach to solving your optimisation, and an alternative limSolve::linp one too.

    http://jcarroll.com.au/2016/04/27/solving-inequality-the-math-kind/

  2. […] This neat approach showed up recently as an answer to a FiveThirtyEight puzzle and of course I couldn't help but throw it at dplyr as soon as I could. Turns out that's not a terrible idea. The question posed is […]

  3. Reggie Talbot Says:

    The first code part doesn’t work for me. I get – Error: unexpected ‘if’ in:
    ” cost=f.con%*%c(a,b,k,d)-f.rhs
    if (max(cost)<=0){ gain=f.obj%*%c(a,b,k,d) if"

    AND a simple insepction of that code shows you have 3 open curly brackets, {, and only 2 close, },.
    Would appreciate some help. Thanks.

  4. Sir Bill International Says:

    You can do this in your head : the solution of a=1 and b=o comes directly from the constraints , once that is done the problem is maximize 2c + d subject to 3c +d <= 12. QED.

    • Sure. The main point in writing these little pieces of code is to have illustrations at the ready for my students in my R course!

  5. agiltools Says:

    Hello Xi’an, thanks for the post, very interesting.
    Just a quick note on the right hand side vector should be f.rhs<-c(100,0,1,8,4)

  6. The question you answered is: how to get there as fast as possible. But that is not the question asked by he Riddler: you actually want to get there first. (Also, the constraint is really c leq 6 because of the fuel.)
    With your solution, if a competitor has a larger budget than you, they could take a=1, b=1, c=3, d=4, for a sum of 550, beating you by 125 days.
    Instead, you should buy all the xenon fuel available in the world (cost 60), and two of the 3 big Russian engines, so that your opponent can only buy one. You still have enough to get one ion engine: a=1, b=1, c=1, d=0, sum=350. The best your opponent can do is a=1, b=0, c=0, d=4, sum=300. You are guaranteed to get there first.

    • Thanks Robin for the correction, here’s yet another puzzle/riddle I read the wrong way!!! Of course this resolution of yours assumes you can move faster than any opponent to purchase those items…

    • Well, ok, but if you go with the assumption that your opponent is reasonably intelligent — so he wants to go fast, too — then getting there as fast as possible is certainly equivalent to getting there first. If you didn’t go as fast as possible, someone else will get there first. Unless you also posit that you want to spend as little of that billion as possible (saving the rest to spend on Jovian barflies), either of your solutions is OK>

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s