Re: [Taler] optimal coin spending

[Jeff Burdges]

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?

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. 

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

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

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

Jeff

signature.asc
Description: This is a digitally signed message part