Greedy Algorithm for MNL-CE

Read in the Data

Data of any size can be provided in an excel or csv file. Value of alpha can be provided here as well.

#dataf<- (read.csv(file.choose(), header=T))
Items = c(1, 2, 3,4) 
Revenue = c(10, 7, 3,4) 
Preference.weight = c(0.01, 0.5, 200,50 ) 
dataf = data.frame(Items, Revenue, Preference.weight) 
alpha<-0.01 #medium
summary(dataf)

##      Items         Revenue      Preference.weight 
##  Min.   :1.00   Min.   : 3.00   Min.   :  0.0100  
##  1st Qu.:1.75   1st Qu.: 3.75   1st Qu.:  0.3775  
##  Median :2.50   Median : 5.50   Median : 25.2500  
##  Mean   :2.50   Mean   : 6.00   Mean   : 62.6275  
##  3rd Qu.:3.25   3rd Qu.: 7.75   3rd Qu.: 87.5000  
##  Max.   :4.00   Max.   :10.00   Max.   :200.0000

Complete Code and Output for Greedy Algorithm

#Declare variables
n<-max(dataf$Items, na.rm = TRUE)
Q1<-matrix(0,n,n)
V0<-vector(,n)
item_index<-vector(,n)
f1<-vector(,n+1)

#Compute No-Choice
for (j in 1:n){
V0[j]<-exp(j*alpha)}

#Start Algorithm A1
k=1
f1[1]<-0

while(k<=n){
  
            for(i in 1:n){
              if (k==1){Q1[i,k]<-(dataf$Revenue[i]*dataf$Preference.weight[i])/(dataf$Preference.weight[i]+V0[k])
              }
              else
                  { 
                    Q1[i,k]<-((dataf$Revenue[i]*dataf$Preference.weight[i])/(P1f+dataf$Preference.weight[i]+V0[k])
                        +(P2f/(P1f+dataf$Preference.weight[i]+V0[k]))) }
            }
           for(z in item_index){Q1[z,k]<-0}
           f1[k+1]<-max(Q1[,k],na.rm=FALSE)
           
#Identify highest expected revenue and corresponding item
           if(f1[k+1]>f1[k]){
             item_index[k]<-which.max(Q1[,k])
             P1=NULL
             P2=NULL
             P1f=NULL
             P2f=NULL
             for(j in item_index){ P1[j]<-(dataf$Preference.weight[j])
             P2[j]<-(dataf$Preference.weight[j]*dataf$Revenue[j])
             }
             P1f<-sum(P1,na.rm=TRUE)
             P2f<-sum(P2,na.rm=TRUE)
              k=k+1  }
           else
             {cat("Assortment returned by Algorithm 1 = ", item_index, "\n")
             break}
}

## Assortment returned by Algorithm 1 =  4 2 1 0

Brute Force Algorithm

Compare the result from Greedy Algorithm with a Brute force solution technique.

# Brute force--all 2^n assortments
#Use the function to generate all assortments and calculate their expected revenues
# Create a vector to store all revenues
d=NULL
PW=NULL
s = n;
res <- sapply(0:(s-1),function(x)rep(c(rep(0,2^x),rep(1,2^x)),2^(s-x-1)))
t<-2^n
E=matrix(0,t,n)
for(i in 1:t){
  d<-rowSums(res)
  for(j in 1:n){
    if(res[i,j]>0){
      PW[j]<-dataf$Preference.weight[j]
    }
    else
    {PW[j]<-0}
    }
    PWSum<-sum(PW,na.rm=TRUE)
    for (k in 1:n){
      if(res[i,k]>0){
    E[i,k]<-(dataf$Revenue[k]*dataf$Preference.weight[k])/(PWSum+V0[d[i]])}
      else{E[i,k]<-0}
        }
 }
Final<-rowSums(E)
max(Final)

## [1] 3.950295

BFSolution<-which( E[which.max(Final),]>0, arr.ind=TRUE)
cat("Assortment returned by brute force = ", BFSolution, "\n")

## Assortment returned by brute force =  1 2 4

Conclusion

The greedy algorithm always returns an optimal solution.