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

December 30, 2016 at 12:03 pm

[…] 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 […]

April 27, 2016 at 3:19 pm

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/

April 27, 2016 at 4:03 pm

Neat output! Thanks.

April 27, 2016 at 3:17 pm

[…] 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 […]

April 22, 2016 at 5:09 pm

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.

April 22, 2016 at 5:45 pm

Ah!, trust wordpress for botching R code… I updated the code but some garbage may remain….

April 22, 2016 at 2:03 am

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.

April 22, 2016 at 7:50 am

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!

April 22, 2016 at 12:43 am

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)

April 22, 2016 at 7:50 am

Thanks!

April 21, 2016 at 9:40 am

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.

April 21, 2016 at 10:21 am

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…

April 21, 2016 at 8:25 pm

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>