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