Re: [Taler] optimal coin spending

[Christian Grothoff]

On 12/20/2015 12:00 AM, Jeff Burdges wrote:
> On Sat, 2015-12-19 at 10:12 +0100, Christian Grothoff wrote:
>> The real question is if we need the power of LP, or if a linear
>> heuristic is not more appropriate for the Wallet.  
> 
> What do you mean by linear heuristic?

Linear-time / greedy.

> As I mention in my first mail, if we use a greedy algorithm, then we
> should run it separately for each mint's denomination set.  It's easy
> to lose the property of being well suited for the greedy algorithm by
> taking the union of two mint's denomination sets. 

Sure, I was expecting us to run the algo for each withdraw operation anyway.

> It's true that LP algorithms can be unpredictable, but if that can be
> resolved, then LP gives you flexibility in tweaking the business logic.

Indeed.

>  Is there an argument that say merchants should not be covering the
> melt fee too?  Maybe we should try to burn off coins with high melt
> fees?  etc. 

That's something we could consider, but the logic implemented in the
merchant right now does not consider discounting the total to cover melt
fees.

>> I'd be worried about both the code size increase and the possible
>> increase in worst-case execution time (LP solvers
>> can be a bit unpredictable).
> 
> After skimming the code, I'm more worried about the lack of references
> to specific algorithms, papers, etc. 

I figured we'd first implement a crude heuristic and then, once the
protocol part is working, we can deal with this "local" issue.

> We're dealing with a variation of a minimum-cost flow problem with
> multiple sources, each coin, and non-scaling costs, and the melt
> strangeness.
> https://en.wikipedia.org/wiki/Minimum-cost_flow_problem
> 
> There is an unsupported claim on wikipedia that minimum-cost flow
> problems are totally unimodular, which lets the simplex algorithm give
> integer solutions.  It's not really clear though since the linear
> program I wrote down did not look totally unimodular where I tried that
> before.
> 
> After glancing at some minimum-cost flow solvers, I felt our graph was
> so trivial that there should be a simpler solution, probably based on
> the dynamic programming one.  I took a stab a writing down the
> algorithm (see next email).

The other question is if we can maybe state some properties that the fee
structure needs/should have to enable a particularly fast way to solve
the problem. We could then either check if the fee structure satisfies
that property and only then run the fast alg instead of LP, or even
require that the fee structure has that property.

signature.asc
Description: OpenPGP digital signature