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.
No comments:
Post a Comment