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 |
