Thursday, March 7, 2013

There are 293 ways to make change for a dollar

Only if you include \$0.50 coins and the dollar bill itself…

 \$ontext    There are 293 ways to make change for a dollar     http://realfacts.snapple.com/dontgochanging/ \$offtext sets    c 'coin (or bill)' /dollar,halfdollar,quarter,dime,nickel,penny/    n 'number of coins of the same type' /n1*n100/    cn(c,n)    w0 'ways' /w1*w300/    w(w0) ; parameter    value(c) /penny 0.01, nickel 0.05, dime 0.1,              quarter 0.25, halfdollar 0.50, dollar 1/    countall(w0,c) ; cn(c,n)\$(ord(n)*value(c) <= 1) = yes; display cn; w(w0) = no; countall(w0,c)=0; binary variable x(c,n); positive variable count(c); variable z; equation    totalvalue   'total value of coins = 1\$'    order(c,n)   'ones at the beginning, i.e. 1,1,1,0,0,0'    dummy        'dummy objective'    counting(c)  'count coins'    different    'different than all previous found solutions' ; * dummy objective dummy.. z =e= 1; * count coins of each value counting(c).. count(c) =e= sum(cn(c,n),x(cn)); * total value should be 1\$ totalvalue..  sum(c, value(c)*count(c)) =e= 1; * we only want to have 1,1,1,0,0,0 * i.e. the ones at the beginning order(cn(c,n+1)).. x(c,n+1) =l= x(c,n); * configuration of coins should be different than earlier solutions different(w).. sum(cn(c,n)\$(ord(n)<=countall(w,c)), x(cn))                 =L= sum(c,countall(w,c))-1; model m /all/; * speed up solver m.solprint=2; m.solvelink=5; scalar ok /1/; option countall:0; loop(w0\$ok,    solve m minimizing z using mip; * optimal or integer feasible?    if (m.modelstat=1 or m.modelstat=8,        w(w0) = yes;        countall(w0,c) = round(count.l(c));    else        ok = 0;    ); ); display countall;

Not 100% trivial this MIP model. Equations order and different are probably not completely obvious. The integer cut is simplified to speed things up. A constraint programming solver would probably make this easier. This particular formulation gives:

 ----     82 PARAMETER countall            dollar  halfdollar     quarter        dime      nickel       penny w1             1 w2                         2 w3                         1           2 w4                         1                       4           2 w5                         1                       3           4 w6                                     1           1           1          60 w7                                     1           2                      55 w8                                                                       100 w9                                                 1                      90 w10                                                5                      50 w11                                    4 w12                                    3                                  25 w13                                    3                       5 w14                                    1                      15 w15                                                            1          95 w16                        1           1           2           1 w17                                                1           1          85 w18                                               10 w19                                                9                      10 w20                                                           20 w21                                                            2          90 w22                                    2           5 w23                                    3           2                       5 w24                                                1          18 w25                        1           1                       1          20 w26                                                2           1          75 w27                                    1                                  75 w28                        1                                              50 w29                                                            3          85 w30                                                            4          80 w31                                    2                      10 w32                                                1           2          80 w33                        1                                   1          45 w34                                                1           3          75 w35                                                1           4          70 w36                                                           18          10 w37                                    3           2           1 w38                                    2                       1          45 w39                                    2           4           2 w40                        1           1           1           3 w41                                    1           7           1 w42                        1           1           1                      15 w43                        1                       5 w44                        1                       2           5           5 w45                                    1                       1          70 w46                                    3                       1          20 w47                                                2                      80 w48                                                3                      70 w49                                                4                      60 w50                        1                       1                      40 w51                        1           1                       5 w52                                                9           2 w53                                    3           1           3 w54                        1                       1           8 w55                                    3           1           2           5 w56                                    2           2           6 w57                                                1           5          65 w58                        1           1           2                       5 w59                                    1           4           5          10 w60                        1                                  10 w61                        1                       2           6 w62                                    1                       2          65 w63                                    2           3           4 w64                                    2                       2          40 w65                                    3           1                      15 w66                                                            5          75 w67                        1           1           1           1          10 w68                                    1           3           9 w69                                    3                       2          15 w70                                    1           4           7 w71                                    1           7                       5 w72                        1                       3                      20 w73                                                9           1           5 w74                        1           1           1           2           5 w75                                    1           5           5 w76                        1           1                                  25 w77                                    2           4                      10 w78                        1                       2                      30 w79                                    1           3                      45 w80                                    1           6           3 w81                        1                       3           1          15 w82                                                           19           5 w83                                    2           3           1          15 w84                                    2           3                      20 w85                                    1           4                      35 w86                                    1           3           1          40 w87                                    2           2           1          25 w88                                    1           4           1          30 w89                                    2           2                      30 w90                        1                       1           7           5 w91                                    3           1           1          10 w92                                    2           4           1           5 w93                                    1           5           1          20 w94                                    2           3           3           5 w95                                                8                      20 w96                                    1           5           2          15 w97                                    3                       4           5 w98                                    1           2           1          50 w99                        1                       4           1           5 w100                                               4          12 w101                       1                       4                      10 w102                                   3                       3          10 w103                                   1           5                      25 w104                                               8           1          15 w105                       1                       3           3           5 w106                                   2           3           2          10 w107                                   2           2           2          20 w108                                   1           1                      65 w109                                   2           1                      40 w110                                               7                      30 w111                                   1           5           4           5 w112                                   1           2          11 w113                                   2           1           1          35 w114                                   1           6           2           5 w115                       1                       2           1          25 w116                                   1           6           1          10 w117                                   1           4           6           5 w118                                   1           1          13 w119                                               3          14 w120                                   1           4           3          20 w121                                   1           6                      15 w122                       1           1                       4           5 w123                                               7           5           5 w124                                   2           2           3          15 w125                                                          14          30 w126                                   2           2           5           5 w127                                   1           1           3          50 w128                                   1           3           3          30 w129                                   2           2           4          10 w130                                   1           3           5          20 w131                                   2                       4          30 w132                                               4           1          55 w133                                   1           3           8           5 w134                       1                       2           2          20 w135                                               7           1          25 w136                                   1           3           2          35 w137                                               8           4 w138                                               7           6 w139                                   1           2          10           5 w140                                               5           7          15 w141                                   1           4           2          25 w142                                   1           3           6          15 w143                                   2           1           8 w144                       1                       2           4          10 w145                                               8           3           5 w146                                               3          13           5 w147                                               1          17           5 w148                                   2           1           3          25 w149                                   1           2           8          15 w150                                   2           1           2          30 w151                                   1           4           4          15 w152                                               6           8 w153                                   2           1           7           5 w154                                               2          16 w155                                   1           5           3          10 w156                                               8           2          10 w157                       1                       3           2          10 w158                                               5          10 w159                                   2                       3          35 w160                                   2                       6          20 w161                                   2                       7          15 w162                                               3           1          65 w163                                               6           2          30 w164                                   1           2           2          45 w165                       1           1                       3          10 w166                       1                       1           4          20 w167                                   2                       9           5 w168                                   2           1           6          10 w169                                               3           3          55 w170                                   1           1           2          55 w171                                               3           4          50 w172                                               4           2          50 w173                       1           1                       2          15 w174                                   2           1           5          15 w175                                               3           2          60 w176                                   1           2           3          40 w177                       1                                   9           5 w178                                               7           3          15 w179                                               7           4          10 w180                                   1           2           5          30 w181                                   1           1           5          40 w182                                   2           1           4          20 w183                       1                       2           3          15 w184                                               2           2          70 w185                                   1           3           7          10 w186                                   2                       8          10 w187                                   1                      13          10 w188                                               6           7           5 w189                                   1           3           4          25 w190                                               6           4          20 w191                                               1           7          55 w192                       1                       1           2          30 w193                                                           7          65 w194                                   2                                  50 w195                                               6           1          35 w196                                               3          12          10 w197                                               4          11           5 w198                                               6                      40 w199                                               1          16          10 w200                                   1           2           4          35 w201                                               7           2          20 w202                                               6           5          15 w203                                               4           4          40 w204                       1                       1           1          35 w205                                               5           5          25 w206                                   1           1          12           5 w207                                   1                       3          60 w208                                   1           1           4          45 w209                                               3          11          15 w210                                                           8          60 w211                                                          11          45 w212                                               2          11          25 w213                                                          12          40 w214                                   2                       5          25 w215                                               5           1          45 w216                                               2          15           5 w217                                               2          14          10 w218                                               1          11          35 w219                                               4          10          10 w220                                               2           7          45 w221                       1                       1           5          15 w222                                               6           6          10 w223                                                          16          20 w224                                   1           2           9          10 w225                                                           9          55 w226                                               5           4          30 w227                                               5           9           5 w228                                               4           7          25 w229                                               2           8          40 w230                                               5           6          20 w231                                               5           8          10 w232                       1                                   5          25 w233                                               5           2          40 w234                                   1           2           6          25 w235                       1                                   7          15 w236                                                           6          70 w237                                               1          10          40 w238                                   1                      12          15 w239                                               1          12          30 w240                                               1          15          15 w241                                               5           3          35 w242                       1                                   4          30 w243                                               3           6          40 w244                       1                       1           3          25 w245                                   1                       7          40 w246                                                          10          50 w247                                               6           3          25 w248                       1                       1           6          10 w249                                               2           3          65 w250                                   1                      14           5 w251                                               4           6          30 w252                                               4           9          15 w253                                   1                       9          30 w254                                   1           1          10          15 w255                                   1           1          11          10 w256                                               2           5          55 w257                                               4           8          20 w258                                               1          14          20 w259                       1                                   8          10 w260                                   1                      10          25 w261                                               2           9          35 w262                       1                                   6          20 w263                                               2          13          15 w264                                                          17          15 w265                                   1                       4          55 w266                       1                                   3          35 w267                                               3           9          25 w268                       1                                   2          40 w269                                   1           2           7          20 w270                                               4           3          45 w271                                   1                      11          20 w272                                               3          10          20 w273                                               1          13          25 w274                                                          13          35 w275                                               1           9          45 w276                                                          15          25 w277                                               2           4          60 w278                                   1                       8          35 w279                                               4           5          35 w280                                               2          12          20 w281                                   1           1           9          20 w282                                               2          10          30 w283                                   1                       5          50 w284                                   1           1           7          30 w285                                               1           6          60 w286                                               3           8          30 w287                                               3           7          35 w288                                               1           8          50 w289                                   1           1           8          25 w290                                   1           1           6          35 w291                                   1                       6          45 w292                                               3           5          45 w293                                               2           6          50

I use binary variables to make the cuts easier. The cuts are similar to the ones shown here: http://yetanothermathprogrammingconsultant.blogspot.com/2011/10/special-case-of-integer-cuts.html.

Note: There are at least four different ways to implement the cuts:

1) Most general way:

 `different(w)..    sum(cn(c,n)\$(ord(n)<=countall(w,c)), x(cn))` - sum(cn(c,n)\$(ord(n)>countall(w,c)), x(cn))               =L= sum(c,countall(w,c))-1;

2) Exploit coins add up to fixed amount:

 `different(w).. sum(cn(c,n)\$(ord(n)<=countall(w,c)), x(cn))` =L= sum(c,countall(w,c))-1;

3) Exploit further that patterns like 1,0,1 are not allowed (only 1,1,0).

 `different(w).. sum(cn(c,n)\$(ord(n)=countall(w,c)), x(cn))` =L= sum(c\$countall(w,c),1)-1;

4) Use cuts that forbid integer solutions directly instead of just binary solutions. This can be done as shown below. This approach is not very efficient for this model as we need to add binary variables during each iteration of the solve loop. In the previous approaches we augmented the model with binary variables only once (the subsequent cuts only add constraints but no extra variables). Actual implementation confirmed this general integer cuts are inferior on this problem.