optimization challenge

Greg

Nice problem: I wasted my whole day on it :-)

I was explaining my plan for a solution to a colleague who is a
computer scientist, he pointed out that I was trying to re-invent the
wheel known as dynamic programming.  here is my code, apparently it is
called "bottom up dynamic programming".  It runs pretty quickly, and
returns (what I hope is :-) the optimal sum of squares and the
cut-points.

function(X=bom3$Verses,days=128){
# find optimal BOM reading schedule for Greg Snow
# minimize variance of quantity to read per day over 128 days
#
N = length(X)
Nm1 = N-1
SSQ<- matrix(NA,nrow=days,ncol=N)
Cuts <- list()
#
#  SSQ[i,j]: the ssqs about the overall mean for the optimal partition 
#           for i days on the chapters 1 to j
#
M = sum(X)/days
CS = cumsum(X)
SSQ[1,]= (CS-M)^2
Cuts[[1]]= as.list(1:N)
#
for(m in 2:days){
Cuts[[m]]=list()
#for(i in 1:(m-1)) Cuts[[m]][[i]] = Cuts[[m-1]][[i]]
for(n in m:N){
      	    	  CS = cumsum(X[n:1])[n:1]
            	  SSQ1 = (CS-M)^2
	    	  j = (m-1):(n-1)
            	  TS = SSQ[m-1,j]+(SSQ1[j+1])
		  SSQ[m,n] = min(TS)
                  k = min(which((min(TS)== TS)))+m-1
                  Cuts[[m]][[n]] = c(Cuts[[m-1]][[k-1]],n)
}
}
list(SSQ=SSQ[days,N],Cuts=Cuts[[days]][[N]])
}

$SSQ
[1] 11241.05

$Cuts
  [1]   2   4   7   9  11  13  15  16  17  19  21  23  25  27  30  31  34  37
 [19]  39  41  44  46  48  50  53  56  59  60  62  64  66  68  70  73  75  77
 [37]  78  80  82  84  86  88  89  91  92  94  95  96  97  99 100 103 105 106
 [55] 108 110 112 113 115 117 119 121 124 125 126 127 129 131 132 135 137 138
 [73] 140 141 142 144 145 146 148 150 151 152 154 156 157 160 162 163 164 166
 [91] 167 169 171 173 175 177 179 181 183 185 186 188 190 192 193 194 196 199
[109] 201 204 205 207 209 211 213 214 215 217 220 222 223 225 226 228 234 236
[127] 238 239

optimization challenge

Thread (8 messages)