User:Gmaxwell/coin selection

From Bitcoin Wiki
Revision as of 22:53, 28 May 2012 by Gmaxwell (talk | contribs) (AMPL program)
Jump to: navigation, search

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

This program finds a zero fee mixture of inputs which _minimizes_ the priority, subject to being zero-fee and meeting the required output and not making a txn which is excessively large or has more than a maximum amount of change. By minimizing the priority we avoid burning priority excessively, resulting in paying more fees in the future. The minimizing process also tends to sweep the wallet of small inputs as a side effect.

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