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.

integerCuts