Coin Selection Problem

description.md

Bitcoin transactions are made up of 1 or inputs and 1 or more outputs. Inputs are discrete amounts of bitcoin that you control. Outputs are where you want to send the bitcoin (and exactly how much). The sum of all the outputs must be less than or equal to the sum of all the inputs (otherwise you could create money from nothing).

When creating a bitcoin transaction, you have a list of eligible inputs to source and need to pick which you want to use. It is not possible to "partially source" an input, but if you selected too much money you can create something called a "change output" which allows you to sending money back to yourself. Note: you can not send yourself less than 100000 amount.

Few defintions for a transaction:

"Mining fee" is defined as the SUM(chosen input amounts) - SUM(chosen output amounts) which is effectively how much money the transaction "destroys".

"Transaction size" is defined as: 148 * COUNT(chosen inputs) + 10 + 34 * COUNT(chosen outputs)

"FeeRate" is defined as "Mining fee" / "Transaction size"

---

For a transaction to be valid, it needs to have at least a certain feeRate. If the transaction pays more fees than is required, the amount paid in excess is known as "miningSacrifice" (which is the absolute amount of money you wasted by over paying).

--

The goal of the problem is to minimize the "cost". The cost of a transaction is simply:

$INPUT_COST * COUNT(chosen inputs) + ($CHANGE_COST if the transaction uses a change output) + miningSacrifice

input.dzn

number_of_input_sources = 10;
input_sources_amounts = [ 4950000, 10100, 1000, 3000000000, 5000, 10000, 2500, 3000, 9000, 1489201];

number_of_mandatory_outputs = 1;
mandatory_output_amounts = [2999932277];

number_of_optional_outputs = 4 ;
optional_output_amounts = [4300, 1005, 10023, 40000000 ];

minimal_fee_rate =  300;
consolidation_fee_rate = 50;

model.mzn

int: number_of_input_sources;
set of int : input_sources = 1..number_of_input_sources;
array[input_sources] of int : input_sources_amounts;

int: number_of_mandatory_outputs;
set of int : mandatory_outputs = 1..number_of_mandatory_outputs;
array[mandatory_outputs] of int : mandatory_output_amounts;

int: number_of_optional_outputs;
set of int: optional_outputs = 1..number_of_optional_outputs;
array[optional_outputs] of int : optional_output_amounts;

int: minimal_fee_rate;
int: consolidation_fee_rate;


int: dust_threshold = 1000;

int: input_size = 148;
int: input_cost = input_size * (minimal_fee_rate - consolidation_fee_rate);

int: fixed_size = 10;

int: output_size = 34;

int: change_cost = (input_size * consolidation_fee_rate) + (output_size * minimal_fee_rate);


array[input_sources] of var bool: selected_inputs;
array[optional_outputs] of var bool: selected_optional_outputs;

var bool: change_output;

var int: change_amount;

var int : mandatory_outputs_sum = sum (p in mandatory_outputs)(mandatory_output_amounts[p]);
var int :selected_input_amounts = sum (p in input_sources where selected_inputs[p] = true) (input_sources_amounts[p]);
var int :selected_optional_outputs_amounts = sum (p in optional_outputs where selected_optional_outputs[p] = true) 
											(optional_output_amounts[p]);
var int: count_selected_inputs = sum (p in input_sources where selected_inputs[p] = true) (selected_inputs[p]);
var int: count_selected_optional_outputs = sum (p in optional_outputs where selected_optional_outputs[p] = true) 
										  (selected_optional_outputs[p]);

var int: mining_fee = selected_input_amounts - (mandatory_outputs_sum + selected_optional_outputs_amounts + 
					  (bool2int(change_output) * change_amount));
					  
var int: total_output_count = number_of_mandatory_outputs + count_selected_optional_outputs + bool2int(change_output);
constraint total_output_count >= 0;

var int: transaction_size = (input_size * count_selected_inputs) + fixed_size + (output_size * total_output_count);

var int: needed_fees = transaction_size * minimal_fee_rate;

var int: mining_sacrifice = mining_fee - needed_fees;

constraint mining_fee >= needed_fees;

constraint (change_output \/ (change_amount = 0) );

constraint (change_output ->  (change_amount >= dust_threshold));


var int: cost = input_cost * (count_selected_inputs - 1) + (bool2int(change_output) * change_cost) + mining_sacrifice;

solve minimize cost;

output ["{\n"
,"  \"selectedInputs\": ",show(selected_inputs),",\n"
,"  \"selectedOptionalOutputs\": ",show(selected_optional_outputs), ",\n"
,"  \"changeAmount\": ",show(change_amount),",\n"
,"  \"cost\":", show(cost),",\n"
,"  \"miningSacrifice\": ", show(mining_sacrifice), ",\n"
,"  \"miningFee\": ", show(mining_fee), ",\n"
,"  \"changeCost\": ", show(change_cost), ",\n"
,"  \"inputCost\": ", show(input_cost), ",\n"
,"\n}\n"];