# Difference between revisions of "User:Gmaxwell/coin selection"

(coin selection) |
m (wikipedia link) |
||

Line 1: | Line 1: | ||

Optimal coin selection is generally a mixed-interger non-linear program problem. These kinds of problems are often NP-complete, though there are heuristic-based solvers which can usually find excellent solutions quickly. | Optimal coin selection is generally a mixed-interger non-linear program problem. These kinds of problems are often NP-complete, though there are heuristic-based solvers which can usually find excellent solutions quickly. | ||

− | Below is an example AMPL input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. | + | Below is an example AMPL[http://en.wikipedia.org/wiki/AMPL] input which can be used with solvers like Bonmin[https://projects.coin-or.org/Bonmin] to find good coin selections. |

==AMPL program== | ==AMPL program== |

## Revision as of 22:46, 28 May 2012

Optimal coin selection is generally a mixed-interger non-linear program problem. These kinds of problems are often NP-complete, though there are heuristic-based solvers which can usually find excellent solutions quickly.

Below is an example AMPL[1] input which can be used with solvers like Bonmin[2] to find good coin selections.

## AMPL program

set coins ordered; param f_min {coins} >= 0, default 0; param f_max {j in coins} >= f_min[j], default 1; param value {coins} >= 0; param age {coins} >= 0; param sigsz {coins} >= 0; param target >= 0; param target_max >= 0; param thresh_prio >= 0; param max_outputs >= 0, default Infinity; param min_out >= 0; param basesz >= 0; # -------------------------------------------------------- var Use {j in coins} integer >= f_min[j], <= f_max[j]; # -------------------------------------------------------- minimize priority: sum {j in coins} value[j] * age[j] * Use[j] / (basesz+(sum {i in coins} sigsz[i] * Use[i])); # -------------------------------------------------------- subject to Free: thresh_prio <= sum {j in coins} value[j] * age[j] * Use[j] / (basesz+(sum {i in coins} sigsz[i] * Use[i])); subject to Enough: target <= sum {j in coins} value[j] * Use[j]; subject to NotTooMuch: target_max >= sum {j in coins} value[j] * Use[j]; subject to size: max_outputs >= sum {j in coins} Use[j]; subject to NoDustChange: min_out <= sum {j in coins} value[j] * Use[j] - target; #subject to NoChange: # target = sum {j in coins} value[j] * Use[j];

### Example AMPL problem data

param target := 150000000; param target_max := 500000000; param thresh_prio := 100; param min_out := 1000000; param max_outputs := 100; param basesz := 100; param: coins: value age sigsz f_min f_max := "aaaa" 100000001 1 100 . . "aaab" 50000000 20000 100 . . "aaac" 100000000 2 50 . . "aaad" 1 1 100 . . ;