User:Gmaxwell/coin selection

From Bitcoin Wiki
Revision as of 22:42, 28 May 2012 by Gmaxwell (talk | contribs) (coin selection)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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[1] 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      .      . ;