{"id":8457,"date":"2020-10-16T22:57:31","date_gmt":"2020-10-16T20:57:31","guid":{"rendered":"https:\/\/quantpedia.com\/?p=8457"},"modified":"2025-06-04T14:01:14","modified_gmt":"2025-06-04T12:01:14","slug":"the-knapsack-problem-implementation-in-r","status":"publish","type":"post","link":"https:\/\/vvv.quantpedia.com\/es\/the-knapsack-problem-implementation-in-r\/","title":{"rendered":"The Knapsack problem implementation in R"},"content":{"rendered":"\n

Our own research paper ESG<\/a> Scores<\/a> and Price Momentum Are More Than Compatible<\/a> utilized the Knapsack problem to make the ESG strategies more profitable<\/a> or Momentum strategies<\/a> significantly less risky. The implementation of the Knapsack problem was created in R, using slightly modified Simulated annealing optimization algorithm. Recently, we have been asked about our implementation and the code. The code is commented and probably could be implemented more efficiently (in R or in another programming language). For example, R is more efficient with matrices, but the code would not be that “straightforward”. Lastly, the most important tuning parameter is the temperature decrease (the probability of accepting a new solution is falling with the rising number of iterations). Feel free to contact<\/a> us<\/a> with any questions or new ideas!<\/strong><\/p>\n\n\n\n

Commented and ready to be copied code:<\/p>\n\n\n\n

##### Simulated annealing Knapsack optimization ####
### this parametrization minimizes the value ###
### in the application, pick the vector of values accordingly ### 
### for example the inverse of ESG scores ###

#m is vector of weights
#c is vector of values
#M is weight cap
#numbit is number of iterations, 100000 was used in the Knapsack ESG-Momentum
#par is a plotting paramter, if the plotting is enabled, plots and returns each par\u00b4s result
#tau is initial temperature
#pt controls the temperature decrease; decrease is set to be linear and pt was set to be 2.5 in the paper
#plotting - logical, TRUE if plotting is enabled, FALSE if disabled
knap.sann<-function(m,c,M,numbit,par,tau,pt,plotting){
#vectors for plotting
weight<-rep(0,numbit\/par)
value<-rep(0,numbit\/par)
#setting the n 
n<-length(m)
x<-rep(0,n)
#solutions
bestval<-0
bestsol<-c(0)
for (i in 1:numbit){
y<-x
#generating random item 
p<-sample(1:n,1)
y[p]<-abs(y[p]-1)
#new item is placed into knapsack (or dropped from knapsack) only if it fits into knapsack, 
#if it does not fits,
#one item from the knapsack is taken into hand and either chosen item (p) or item in the hand (hand) is dropped
while (t(y)%*%m>M){
hand<-sample(x,1)
y[sample(c(p,hand),1)]<-0
}
#Simulated annealing part; section three in the paper ESG Scores and Price Momentum Are More Than Compatible 
if (runif(1) < exp((t(x)%*%c - t(y)%*%c) \/ (tau \/ (pt*i)))) {
if(t(y)%*%c>bestval){
bestval<-t(y)%*%c
bestsol<-y
}
x <- y
}
#plotting
if(plotting==TRUE){
if(i %% par ==0){
print(t(x)%*%c)
print(t(x)%*%m)
weight[i\/par]<-t(x)%*%m
value[i\/par]<-t(x)%*%c
}
}
}
if(plotting==TRUE){
osX<-seq(1:length(weight))
par(mfrow=c(2,1))
plot(osX,weight)
lines(osX,rep(M,length(osX)),col=\"red\")
plot(osX,value)
}
#results
results <- list()
results$first <- bestsol
results$second <- bestval
return(results) 
#return(bestsol)
}<\/pre>\n\n\n\n
Author: Matus Padysak<\/a>, Senior Analyst, Quantpedia.com<\/strong><\/p>\n\n\n\n
\n\n\n\n
Are you looking for more strategies to read about? Sign up for our newsletter<\/a> or visit our Blog<\/a> or Screener<\/a><\/strong>.<\/p>\n\n\n\n
Do you want to learn more about Quantpedia Premium service? Check how Quantpedia works<\/a>, our mission<\/a> and Premium pricing offer<\/a>.<\/strong><\/p>\n\n\n\n
Do you want to learn more about Quantpedia Pro service? Check its description<\/a>, watch videos<\/a>, review reporting capabilities<\/a> and visit our pricing offer<\/a>.<\/strong><\/p>\n\n\n\n
Are you looking for historical data or backtesting platforms? Check our list of Algo Trading Discounts<\/a><\/strong>.<\/p>\n\n\n\n
Would you like free access to our services<\/a>? Then, open an account with Lightspeed<\/a> and enjoy one year of Quantpedia Premium at no cost.<\/strong><\/p>\n\n\n\n
\n\n\n\n
Or follow us on:<\/strong><\/p>\n\n\n\n
Facebook Group<\/a>, Facebook Page<\/a>, Twitter<\/a>, Linkedin<\/a>, Medium<\/a> or Youtube<\/a><\/strong><\/p>\n\n\n","protected":false},"excerpt":{"rendered":"
Our own research paper ESG Scores and Price Momentum Are More Than Compatible<\/strong><\/a> utilized the Knapsack problem to make the ESG strategies more profitable<\/strong><\/a> or Momentum strategies<\/strong><\/a> significantly less risky. The implementation of the Knapsack problem was created in R, using slightly modified Simulated annealing optimization algorithm. Recently, we have been asked about our implementation and the code. The code is commented and probably could be implemented more efficiently (in R or in another programming language). For example, R is more efficient with matrices, but the code would not be that \u201cstraightforward\u201d. Lastly, the most important tuning parameter is the temperature decrease (the probability of accepting a new solution is falling with the rising number of iterations). <\/strong><\/p>","protected":false},"author":21001,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[155,161,159],"class_list":["post-8457","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-alternative-data","tag-esg-investing","tag-own-research"],"_links":{"self":[{"href":"https:\/\/vvv.quantpedia.com\/es\/wp-json\/wp\/v2\/posts\/8457","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vvv.quantpedia.com\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vvv.quantpedia.com\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vvv.quantpedia.com\/es\/wp-json\/wp\/v2\/users\/21001"}],"replies":[{"embeddable":true,"href":"https:\/\/vvv.quantpedia.com\/es\/wp-json\/wp\/v2\/comments?post=8457"}],"version-history":[{"count":0,"href":"https:\/\/vvv.quantpedia.com\/es\/wp-json\/wp\/v2\/posts\/8457\/revisions"}],"wp:attachment":[{"href":"https:\/\/vvv.quantpedia.com\/es\/wp-json\/wp\/v2\/media?parent=8457"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vvv.quantpedia.com\/es\/wp-json\/wp\/v2\/categories?post=8457"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vvv.quantpedia.com\/es\/wp-json\/wp\/v2\/tags?post=8457"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}