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

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      .      . ;
```