## Wednesday, March 27, 2013

### There are 293 ways to make change for a dollar (2)

In a previous model we used cuts to find all solutions (http://yetanothermathprogrammingconsultant.blogspot.com/2013/03/there-are-293-ways-to-make-change-for.html). This time we use the solution pool in Cplex. This is quite an adventure:

• The documentation on the solution pool in http://www.gams.com/dd/docs/solvers/cplex.pdf is really bad. It also contains some things I think are wrong or confusing.
• The solution pool does not work with a constant objective.
• But eventually, we got it to work and then it is very fast. We find all 293 integer solutions in just 46 simplex pivots:
 MIP Solution: 1.000000 (46 iterations, 1162 nodes)
This is quite some performance.

 \$ontext    There are 293 ways to make change for \$1     http://realfacts.snapple.com/dontgochanging/     Solution Pool version \$offtext sets    c 'coin (or bill)' /dollar,halfdollar,quarter,dime,nickel,penny/ ; parameter    value(c) /penny 0.01, nickel 0.05, dime 0.1,              quarter 0.25, halfdollar 0.50, dollar 1/    target / 1 / ; variables    count(c)    z ; integer variable count; count.up(c) = floor(1e-6 + target/value(c)); equation    totalvalue   'total value of coins = target'    dummy        'dummy objective' ; * dummy objective * solution pool does not work correctly with an objective of the form *    dummy.. z =e= 1; * don't know why. I don't see any message indicating any problem. * The message is after just the first solution: *  Populate has completed the enumeration of solutions. * which is obviously wrong. * This objective seems to work better: dummy.. z =e= sum(c,count(c)); * total value should be 1\$ totalvalue..  sum(c, value(c)*count(c)) =e= target; model m2 /all/; m2.optfile=1; solve m2 minimizing z using mip; sets   soln            'possible solutions in the solution pool' /file1*file1000/   solnpool(soln)  'actual solutions' ; parameter allcount(soln,c); * * some ugly code to read the solutions * file fsol; execute_load 's.gdx', solnpool=Index; loop(solnpool(soln),    put_utility fsol 'gdxin' / solnpool.te(soln):0:0;    execute_loadpoint;    allcount(soln,c) = count.l(c); ); option allcount:0; display allcount; * * option file. some options were set by trial and error. * the documentation really sucks. * the advice to use SolnPoolAGap=0.0 is wrong but that may be because * we had to change the obj.  * \$onecho > cplex.opt *SolnPoolAGap=0.0 solnpool=s.gdx solnpoolintensity=4 solnpoolpop=2 populatelim=100000 \$offecho

The final results shows all solutions:

 ----     71 PARAMETER allcount               dollar  halfdollar     quarter        dime      nickel       penny file1             1 file2                         2 file3                         1           2 file4                         1           1           2           1 file5                         1           1           2                       5 file6                                     3           2           1 file7                                     3           1           3 file8                                     2           2           6 file9                                     3           2                       5 file10                                    3           1           2           5 file11                                    2           2           5           5 file12                                    2           2           4          10 file13                        1           1           1           3 file14                        1           1                       5 file15                        1           1           1           2           5 file16                        1           1           1           1          10 file17                        1           1           1                      15 file18                        1           1                       4           5 file19                        1           1                       3          10 file20                                    2           2           3          15 file21                                    2           2           2          20 file22                                    3                       5 file23                                    2                      10 file24                                    3                       4           5 file25                                    3                       3          10 file26                                    2                       9           5 file27                                    3                       2          15 file28                                    3                       1          20 file29                                    2                       8          10 file30                                    2                       7          15 file31                                    2                       6          20 file32                                    2                       5          25 file33                                    2                       4          30 file34                                    3                                  25 file35                                    1                      15 file36                                                           20 file37                                    1                      14           5 file38                                    1                      13          10 file39                                                           19           5 file40                                    1                      12          15 file41                                    1                      11          20 file42                                    1                      10          25 file43                                    1                       9          30 file44                                    2           1           8 file45                                    2           1           7           5 file46                                    1           1          13 file47                                                1          18 file48                                    1           1          12           5 file49                                    1           1          11          10 file50                                    1           1          10          15 file51                                    1           1           9          20 file52                                    1           1           8          25 file53                                    1           1           7          30 file54                                    1           1           6          35 file55                                    1           1           5          40 file56                                    1           1           4          45 file57                                    1           1           3          50 file58                                    1           1           2          55 file59                                    1           1           1          60 file60                                    2           1           6          10 file61                                    2           1           5          15 file62                                    2           1           4          20 file63                                    2           1           3          25 file64                                    2           1           2          30 file65                                    2           2           1          25 file66                                    2           2                      30 file67                                    3           1           1          10 file68                                    3           1                      15 file69                        1                       2           6 file70                        1                       1           8 file71                        1                       2           5           5 file72                        1                       2           4          10 file73                        1                       1           7           5 file74                        1                       1           6          10 file75                        1                       2           3          15 file76                        1                                  10 file77                        1                                   9           5 file78                        1                                   8          10 file79                        1                                   7          15 file80                        1                                   6          20 file81                        1                                   5          25 file82                        1                                   4          30 file83                        1                                   3          35 file84                        1                                   2          40 file85                        1                                   1          45 file86                        1                                              50 file87                        1                       2           2          20 file88                        1                       2           1          25 file89                        1                       2                      30 file90                        1           1                       2          15 file91                        1           1                       1          20 file92                                                1          17           5 file93                                                1          16          10 file94                                                1          15          15 file95                                                1          14          20 file96                                                1          13          25 file97                                                1          12          30 file98                                                1          11          35 file99                                                1          10          40 file100                                   2           5 file101                                   2           4           2 file102                                   2           3           4 file103                                   2           4           1           5 file104                                   2           4                      10 file105                                   2           3           3           5 file106                                   2           3           2          10 file107                                   1           7           1 file108                                   1           7                       5 file109                                   1           6           3 file110                                   1           5           5 file111                                   1           6           2           5 file112                                   1           6           1          10 file113                                   1           6                      15 file114                                   1           5           4           5 file115                                   1           5           3          10 file116                                   1           4           7 file117                                   1           4           6           5 file118                                   1           4           5          10 file119                                   1           4           4          15 file120                                   1           4           3          20 file121                                   1           4           2          25 file122                                              10 file123                                               9           2 file124                                               9           1           5 file125                                               8           4 file126                                               8           3           5 file127                                               8           2          10 file128                                   1           5           2          15 file129                                   1           5           1          20 file130                                   1           5                      25 file131                                               8           1          15 file132                                               8                      20 file133                                   1           4           1          30 file134                                   1           4                      35 file135                       1           1                                  25 file136                                   2                       3          35 file137                                   2                       2          40 file138                                   2                       1          45 file139                                   2                                  50 file140                                   2           1           1          35 file141                                   2           1                      40 file142                                                          18          10 file143                                                          17          15 file144                                                          16          20 file145                                                          15          25 file146                                                          14          30 file147                                                          13          35 file148                                                          12          40 file149                                                          11          45 file150                                                          10          50 file151                                                           9          55 file152                                                           8          60 file153                                                           7          65 file154                                                           6          70 file155                                                           5          75 file156                                                           4          80 file157                                                           3          85 file158                                   2           3           1          15 file159                                   2           3                      20 file160                                   1           2          11 file161                                   1           2          10           5 file162                                               2          16 file163                                               2          15           5 file164                                               2          14          10 file165                                   1           2           9          10 file166                                   1           2           8          15 file167                                               2          13          15 file168                                               2          12          20 file169                                               2          11          25 file170                                               2          10          30 file171                                               2           9          35 file172                                               2           8          40 file173                                               2           7          45 file174                                               2           6          50 file175                                               2           5          55 file176                                               2           4          60 file177                                               2           3          65 file178                                               2           2          70 file179                                               2           1          75 file180                                               2                      80 file181                                   1                       8          35 file182                                   1                       7          40 file183                                   1                       6          45 file184                                   1                       5          50 file185                                   1                       4          55 file186                                   1                       3          60 file187                                   1                       2          65 file188                                   1                       1          70 file189                                   1                                  75 file190                                   1           2           7          20 file191                                   1           2           6          25 file192                                   1           2           5          30 file193                                   1           2           4          35 file194                                   1           2           3          40 file195                                   1           2           2          45 file196                                   1           2           1          50 file197                                   1           2                      55 file198                                               1           9          45 file199                                               1           8          50 file200                                               1           7          55 file201                                               1           6          60 file202                                               1           5          65 file203                                               1           4          70 file204                                               1           3          75 file205                                               1           2          80 file206                                               1           1          85 file207                                               1                      90 file208                                   1           3           9 file209                                   1           3           8           5 file210                                   1           3           7          10 file211                                   1           3           6          15 file212                                   1           3           5          20 file213                                   1           3           4          25 file214                                   1           3           3          30 file215                                   1           3           2          35 file216                                   1           3           1          40 file217                                   1           3                      45 file218                                                           2          90 file219                                                           1          95 file220                                                                     100 file221                                   1           1                      65 file222                                               7           6 file223                                               7           5           5 file224                                               7           4          10 file225                                               7           3          15 file226                                               7           2          20 file227                                               7           1          25 file228                                               7                      30 file229                                               6           8 file230                                               5          10 file231                                               6           7           5 file232                                               6           6          10 file233                                               4          12 file234                                               4          11           5 file235                                               3          14 file236                                               3          13           5 file237                                               3          12          10 file238                                               4          10          10 file239                                               4           9          15 file240                                               4           8          20 file241                                               3          11          15 file242                                               3          10          20 file243                                               3           9          25 file244                                               3           8          30 file245                                               6           5          15 file246                                               6           4          20 file247                                               6           3          25 file248                                               6           2          30 file249                                               6           1          35 file250                                               6                      40 file251                                               5           9           5 file252                                               4           7          25 file253                                               4           6          30 file254                                               4           5          35 file255                                               4           4          40 file256                                               4           3          45 file257                                               4           2          50 file258                                               4           1          55 file259                                               4                      60 file260                                               3           7          35 file261                                               3           6          40 file262                                               3           5          45 file263                                               3           4          50 file264                                               3           3          55 file265                                               3           2          60 file266                                               3           1          65 file267                                               3                      70 file268                       1                       5 file269                       1                       4           2 file270                       1                       3           4 file271                       1                       4           1           5 file272                       1                       4                      10 file273                       1                       3           3           5 file274                       1                       3           2          10 file275                       1                       3           1          15 file276                       1                       3                      20 file277                                               9                      10 file278                                               5           8          10 file279                                               5           7          15 file280                                               5           6          20 file281                                               5           5          25 file282                                               5           4          30 file283                                               5           3          35 file284                                               5           2          40 file285                                               5           1          45 file286                                               5                      50 file287                       1                       1           5          15 file288                       1                       1           4          20 file289                       1                       1           3          25 file290                       1                       1           2          30 file291                       1                       1           1          35 file292                       1                       1                      40 file293                                   4