$ontext I have a challenge that I want to share with the group. This is not homework (but I may assign it as such if I teach the appropriate class again) and I have found one solution, so don't need anything urgent. This is more for fun to see if others can find a better solution than I did. The challenge: I want to read a book in a given number of days. I want to read an integer number of chapters each day (there are more chapters than days), no stopping part way through a chapter, and at least 1 chapter each day. The chapters are very non uniform in length (some very short, a few very long, many in between) so I would like to come up with a reading schedule that minimizes the variance of the length of the days readings (read multiple short chapters on the same day, long chapters are the only one read that day). I also want to read through the book in order (no skipping ahead to combine short chapters that are not naturally next to each other. My thought was that the optim function with method="SANN" would be an appropriate approach, but my first couple of tries did not give very good results. I have since come up with an optim with SANN solution that gives what I consider good results (but I accept that better is possible). Below is a data frame with the lengths of the chapters for the book that originally sparked the challenge for me (but the general idea should work for any book). Each row represents a chapter (in order) with 3 different measures of the length of the chapter. For this challenge I want to read the book in 128 days (there are 239 chapters). I will post my solutions in a few days, but I want to wait so that my direction does not influence people from trying other approaches (if there is something better than optim, that is fine). Good luck for anyone interested in the challenge, -------------------------------------------------------------------------------------------------------------- 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 Reference: http://thread.gmane.org/gmane.comp.lang.r.general/175564 There are different formulations possible for this, but I have not find any that could be solved easily using any of the solvers I have access to. The above Dynamic Programming alforithm in R seems to outperfom my models. $offtext set i 'chapters' / "1 Nephi 1"*"1 Nephi 22" "2 Nephi 1"*"2 Nephi 33" "Jacob 1"*"Jacob 7" "Enos 1", "Jarom 1", "Omni 1", "Words of Mormon 1" "Mosiah 1"*"Mosiah 29" "Alma 1"*"Alma 63" "Helaman 1"*"Helaman 16" "3 Nephi 1"*"3 Nephi 30" "4 Nephi 1" "Mormon 1"*"Mormon 9" "Ether 1"*"Ether 15" "Moroni 1"*"Moroni 10" /; table data(i,*) Words Letters Verses "1 Nephi 1" 908 3746 20 "1 Nephi 2" 879 3640 24 "1 Nephi 3" 1067 4295 31 "1 Nephi 4" 1262 4968 38 "1 Nephi 5" 761 3202 22 "1 Nephi 6" 202 777 6 "1 Nephi 7" 992 3941 22 "1 Nephi 8" 1221 4769 38 "1 Nephi 9" 259 1075 6 "1 Nephi 10" 924 3829 22 "1 Nephi 11" 1315 5159 36 "1 Nephi 12" 860 3527 23 "1 Nephi 13" 1899 7874 42 "1 Nephi 14" 1284 5236 30 "1 Nephi 15" 1488 6149 36 "1 Nephi 16" 1618 6555 39 "1 Nephi 17" 2523 10180 55 "1 Nephi 18" 1217 4960 25 "1 Nephi 19" 1292 5399 24 "1 Nephi 20" 698 2767 22 "1 Nephi 21" 945 3758 26 "1 Nephi 22" 1506 6275 31 "2 Nephi 1" 1543 6391 32 "2 Nephi 2" 1460 6151 30 "2 Nephi 3" 1170 4685 25 "2 Nephi 4" 1300 5267 35 "2 Nephi 5" 1169 4767 34 "2 Nephi 6" 895 3780 18 "2 Nephi 7" 405 1574 11 "2 Nephi 8" 812 3261 25 "2 Nephi 9" 2388 9985 54 "2 Nephi 10" 966 4106 25 "2 Nephi 11" 338 1332 8 "2 Nephi 12" 647 2557 22 "2 Nephi 13" 587 2454 26 "2 Nephi 14" 203 810 6 "2 Nephi 15" 857 3540 30 "2 Nephi 16" 370 1406 13 "2 Nephi 17" 687 2668 25 "2 Nephi 18" 570 2304 22 "2 Nephi 19" 587 2474 21 "2 Nephi 20" 928 3715 34 "2 Nephi 21" 520 2090 16 "2 Nephi 22" 134 533 6 "2 Nephi 23" 587 2442 22 "2 Nephi 24" 891 3587 32 "2 Nephi 25" 1699 7294 30 "2 Nephi 26" 1483 6363 33 "2 Nephi 27" 1461 5809 35 "2 Nephi 28" 1240 4997 32 "2 Nephi 29" 804 3197 14 "2 Nephi 30" 708 2941 18 "2 Nephi 31" 988 4065 21 "2 Nephi 32" 426 1743 9 "2 Nephi 33" 647 2539 15 "Jacob 1" 719 3149 19 "Jacob 2" 1365 5815 35 "Jacob 3" 619 2765 14 "Jacob 4" 929 4027 18 "Jacob 5" 3758 15366 77 "Jacob 6" 511 2091 13 "Jacob 7" 1242 4988 27 "Enos 1" 1160 4730 27 "Jarom 1" 734 3149 15 "Omni 1" 1398 5906 30 "Words of Mormon 1" 857 3704 18 "Mosiah 1" 966 4188 18 "Mosiah 2" 2112 8675 41 "Mosiah 3" 1117 4771 27 "Mosiah 4" 1605 6586 30 "Mosiah 5" 740 2965 15 "Mosiah 6" 309 1313 7 "Mosiah 7" 1555 6326 33 "Mosiah 8" 938 3948 21 "Mosiah 9" 864 3489 19 "Mosiah 10" 957 3942 22 "Mosiah 11" 1271 5205 29 "Mosiah 12" 1291 5309 37 "Mosiah 13" 1073 4300 35 "Mosiah 14" 391 1574 12 "Mosiah 15" 1056 4559 31 "Mosiah 16" 560 2393 15 "Mosiah 17" 650 2655 20 "Mosiah 18" 1382 5755 35 "Mosiah 19" 978 4070 29 "Mosiah 20" 963 4027 26 "Mosiah 21" 1328 5649 36 "Mosiah 22" 620 2651 16 "Mosiah 23" 1186 4978 39 "Mosiah 24" 954 3970 25 "Mosiah 25" 837 3610 24 "Mosiah 26" 1200 5112 39 "Mosiah 27" 1601 6733 37 "Mosiah 28" 812 3513 20 "Mosiah 29" 1879 7990 47 "Alma 1" 1496 6356 33 "Alma 2" 1433 6179 38 "Alma 3" 1016 4340 27 "Alma 4" 1035 4432 20 "Alma 5" 2787 11260 62 "Alma 6" 390 1657 8 "Alma 7" 1443 5913 27 "Alma 8" 1231 5033 32 "Alma 9" 1511 6274 34 "Alma 10" 1442 5835 32 "Alma 11" 1466 5865 46 "Alma 12" 1858 7802 37 "Alma 13" 1347 5776 31 "Alma 14" 1526 6295 29 "Alma 15" 711 3034 19 "Alma 16" 1010 4383 21 "Alma 17" 1848 7842 39 "Alma 18" 1623 6659 43 "Alma 19" 1701 6905 36 "Alma 20" 1279 5104 30 "Alma 21" 955 4162 23 "Alma 22" 1871 7733 35 "Alma 23" 764 3321 18 "Alma 24" 1509 6241 30 "Alma 25" 752 3212 17 "Alma 26" 1665 6840 37 "Alma 27" 1260 5294 30 "Alma 28" 575 2471 14 "Alma 29" 708 2748 17 "Alma 30" 2666 10762 60 "Alma 31" 1478 6269 38 "Alma 32" 1837 7479 43 "Alma 33" 855 3416 23 "Alma 34" 1576 6477 41 "Alma 35" 699 3043 16 "Alma 36" 1229 4719 30 "Alma 37" 2027 8764 47 "Alma 38" 651 2494 15 "Alma 39" 793 3168 19 "Alma 40" 1153 4790 26 "Alma 41" 701 2983 15 "Alma 42" 1229 5129 31 "Alma 43" 2221 9795 54 "Alma 44" 1243 5043 24 "Alma 45" 911 3913 24 "Alma 46" 1809 7635 41 "Alma 47" 1572 6693 36 "Alma 48" 1073 4669 25 "Alma 49" 1345 5968 30 "Alma 50" 1734 7508 40 "Alma 51" 1682 7271 37 "Alma 52" 1757 7543 40 "Alma 53" 1085 4730 23 "Alma 54" 988 4095 24 "Alma 55" 1218 5152 35 "Alma 56" 2177 9129 57 "Alma 57" 1517 6395 36 "Alma 58" 1748 7357 41 "Alma 59" 489 2166 13 "Alma 60" 1777 7512 36 "Alma 61" 854 3544 21 "Alma 62" 2220 9554 52 "Alma 63" 593 2505 17 "Helaman 1" 1418 6171 34 "Helaman 2" 599 2568 14 "Helaman 3" 1527 6542 37 "Helaman 4" 1076 4781 26 "Helaman 5" 2084 8655 52 "Helaman 6" 1797 7721 41 "Helaman 7" 1142 4751 29 "Helaman 8" 1210 5134 28 "Helaman 9" 1480 6032 41 "Helaman 10" 720 3013 19 "Helaman 11" 1561 6536 38 "Helaman 12" 873 3504 26 "Helaman 13" 1855 7527 39 "Helaman 14" 1241 5106 31 "Helaman 15" 824 3607 17 "Helaman 16" 1025 4247 25 "3 Nephi 1" 1340 5524 30 "3 Nephi 2" 769 3404 19 "3 Nephi 3" 1353 5947 26 "3 Nephi 4" 1518 6506 33 "3 Nephi 5" 931 3891 26 "3 Nephi 6" 1200 5256 30 "3 Nephi 7" 1132 4944 26 "3 Nephi 8" 871 3700 25 "3 Nephi 9" 965 4006 22 "3 Nephi 10" 807 3392 19 "3 Nephi 11" 1434 5732 41 "3 Nephi 12" 1294 5185 48 "3 Nephi 13" 834 3402 34 "3 Nephi 14" 628 2451 27 "3 Nephi 15" 731 2962 24 "3 Nephi 16" 913 3679 20 "3 Nephi 17" 879 3550 25 "3 Nephi 18" 1344 5429 39 "3 Nephi 19" 1233 5083 36 "3 Nephi 20" 1538 6354 46 "3 Nephi 21" 1155 4659 29 "3 Nephi 22" 507 2155 17 "3 Nephi 23" 415 1754 14 "3 Nephi 24" 620 2496 18 "3 Nephi 25" 183 721 6 "3 Nephi 26" 793 3326 21 "3 Nephi 27" 1269 4917 33 "3 Nephi 28" 1457 5856 39 "3 Nephi 29" 394 1589 9 "3 Nephi 30" 130 564 2 "4 Nephi 1" 1949 8300 49 "Mormon 1" 706 2987 19 "Mormon 2" 1262 5317 29 "Mormon 3" 939 3820 22 "Mormon 4" 822 3595 23 "Mormon 5" 1067 4483 24 "Mormon 6" 914 3664 22 "Mormon 7" 454 1805 10 "Mormon 8" 1710 6931 41 "Mormon 9" 1510 6225 37 "Ether 1" 901 3508 43 "Ether 2" 1370 5481 25 "Ether 3" 1253 5007 28 "Ether 4" 892 3623 19 "Ether 5" 226 891 6 "Ether 6" 1048 4265 30 "Ether 7" 899 3746 27 "Ether 8" 1231 5041 26 "Ether 9" 1424 5823 35 "Ether 10" 1415 5726 34 "Ether 11" 762 3238 23 "Ether 12" 1536 6443 41 "Ether 13" 1219 5053 31 "Ether 14" 1132 4664 31 "Ether 15" 1314 5370 34 "Moroni 1" 147 614 4 "Moroni 2" 119 459 3 "Moroni 3" 120 491 4 "Moroni 4" 153 629 3 "Moroni 5" 91 351 2 "Moroni 6" 335 1457 9 "Moroni 7" 1929 7812 48 "Moroni 8" 1064 4677 30 "Moroni 9" 1012 4305 26 "Moroni 10" 1149 4603 34 ; parameter v(i); v(i) = data(i,'verses'); display v; set t 'days' /day1*day128/; scalar avg 'average number of verses to read'; avg = sum(i,v(i))/card(t); variables x(i,t) 'assign chapter to day' numv(t) ssq ; binary variables x; positive variable numv; equations readonce(i) 'a chapter is read exactly one' minch(t) 'minimal one chapter per day' order1 'ordering' order2 'ordering' calcnumv(t) obj ; readonce(i).. sum(t,x(i,t)) =e= 1; minch(t).. sum(i, x(i,t)) =g= 1; order1(i+1,t).. x(i,t) =L= x(i+1,t)+x(i+1,t+1); order2(i+1,t).. x(i+1,t)+x(i+1,t+1) =L= 2-x(i,t); x.fx(i,t)$(ord(i)=1 and ord(t)=1)=1; x.fx(i,t)$(ord(i)=card(i) and ord(t)=card(t))=1; calcnumv(t).. numv(t) =e= sum(i, v(i)*x(i,t)); set notx(i,t) 'these are impossible'; notx(i,t)$(ord(t)>ord(i))=yes; notx(i,t)$(ord(i)-card(i)>ord(t)-card(t))=yes; display notx; x.fx(notx)=0; obj.. ssq =e= sum(t, power(numv(t)-avg,2)); option optcr=0; model m /all/; solve m minimizing ssq using miqcp; display x.l;