# A knapsack riddle [#2]?

February 16, 2017
By

(This article was originally published at R – Xi'an's Og, and syndicated at StatsBlogs.)

Still about this allocation riddle of the past week, and still with my confusion about the phrasing of the puzzle, when looking at a probabilistic interpretation of the game, rather than for a given adversary’s y, the problem turns out to search for the maximum of

$\mathbb{E}[L(x,Y)]=\sum_{i=1}^{10} i\{P(Y_ix_i)\}$

where the Y’s are Binomial B(100,p). Given those p’s, this function of x is available in closed form and can thus maximised by a simulated annealing procedure, coded as

utility=function(x,p){
ute=2*pbinom(x[1]-1,100,prob=p[1])+
dbinom(x[1],100,p[1])
for (i in 2:10)
ute=ute+2*i*pbinom(x[i]-1,100,prob=p[i])+
i*dbinom(x[i],100,p[i])
return(ute)}
#basic term in utility
baz=function(i,x,p){
return(i*dbinom(x[i],100,p[i])+
i*dbinom(x[i]-1,100,p[i]))}
#relies on a given or estimated p
x=rmultinom(n=1,siz=100,prob=p)
maxloz=loss=0
newloss=losref=utility(x,p)
#random search
T=1e3
Te=1e2
baza=rep(0,10)
t=1
while ((t<T)||(newloss>loss)){
loss=newloss
i=sample(1:10,1,prob=(10:1)*(x>0))
#moving all other counters by one
xp=x+1;xp[i]=x[i]
#corresponding utility change
for (j in 1:10) baza[j]=baz(j,xp,p)
proz=exp(log(t)*(baza-baza[i])/Te)
#soft annealing move
j=sample(1:10,1,prob=proz)
if (i!=j){ x[i]=x[i]-1;x[j]=x[j]+1}
newloss=loss+baza[j]-baza[i]
if (newloss>maxloz){
maxloz=newloss;argz=x}
t=t+1
if ((t>T-10)&(newloss<losref)){
t=1;loss=0
x=rmultinom(n=1,siz=100,prob=p)
newloss=losref=utility(x,p)}}


which seems to work, albeit not always returning the same utility. For instance,

> p=cy/sum(cy)
> utility(argz,p)
[1] 78.02
> utility(cy,p)
[1] 57.89


or

> p=sy/sum(sy)
> utility(argz,p)
[1] 82.04
> utility(sy,p)
[1] 57.78


Of course, this does not answer the question as intended and reworking the code to that purpose is not worth the time!

Filed under: Kids, R, Statistics Tagged: integer programming, knapsack problem, mathematical puzzle, optimisation

Please comment on the article here: R – Xi'an's Og

Tags: , , , , , ,

 Tweet

Email: