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