This website uses cookies to collect usage information in order to offer a better browsing experience. By browsing this site or by clicking on the "ACCEPT COOKIES" button you accept our Cookie Policy.

# The Knapsack Problem Implementation in R

Contributor:
Quantpedia
Visit: Quantpedia

Senior Analyst, Quantpedia.com

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”. Feel free to contact us with any questions or new ideas!

Commented and ready to be copied code:

##### Simulated annealing Knapsack optimization ####

#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´s 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)
}

Author: Matus Padysak, Senior Analyst, Quantpedia.com

##### Disclosure: Interactive Brokers

Information posted on IBKR Traders’ Insight that is provided by third-parties and not by Interactive Brokers does NOT constitute a recommendation by Interactive Brokers that you should contract for the services of that third party. Third-party participants who contribute to IBKR Traders’ Insight are independent of Interactive Brokers and Interactive Brokers does not make any representations or warranties concerning the services offered, their past or future performance, or the accuracy of the information provided by the third party. Past performance is no guarantee of future results.

This material is from Quantpedia and is being posted with permission from Quantpedia. The views expressed in this material are solely those of the author and/or Quantpedia and IBKR is not endorsing or recommending any investment or trading discussed in the material. This material is not and should not be construed as an offer to sell or the solicitation of an offer to buy any security. To the extent that this material discusses general market activity, industry or sector trends or other broad based economic or political conditions, it should not be construed as research or investment advice. To the extent that it includes references to specific securities, commodities, currencies, or other instruments, those references do not constitute a recommendation to buy, sell or hold such security. This material does not and is not intended to take into account the particular financial conditions, investment objectives or requirements of individual customers. Before acting on this material, you should consider whether it is suitable for your particular circumstances and, as necessary, seek professional advice.

In accordance with EU regulation: The statements in this document shall not be considered as an objective or independent explanation of the matters. Please note that this document (a) has not been prepared in accordance with legal requirements designed to promote the independence of investment research, and (b) is not subject to any prohibition on dealing ahead of the dissemination or publication of investment research.

Any trading symbols displayed are for illustrative purposes only and are not intended to portray recommendations.