Re: [Taler] optimal coin spending

[Jeff Burdges]

4.  Quasi Dynamic Programming

I've written down an algorithm that's almost dynamic programming, but
achieves running time O(|D|^2) instead of O(price*|D|). It reads
somewhat like the greedy solution, except we keep a collection of
partial spends we've tried thus far, and introduce a new empty spend at
each iteration of the outer loop.

In this, our only real assumption is that we spend as much of x as
possible whenever (f[x]+c)/v[x] < (f[y]+c)/v[y] and x and y are both
spent.  This won't always hold when refresh fees exist though. 

I think one could fix this by continually adjusting the sorting by this
(r[x]+c)/price term as the price declined, but price differs for the
different elements in the trys set, so that is not canonical.  It's
anyways better than the greedy algorithm.  :)

function FindCoinsDynamicly(price0,w,D,v,f,m,r,c) 
  best = ({},None,0)
  trys = {}

  function try_denom(d)
      new := { }
      for (price,t,cost) in trys do
        n = price mod d.value
        if n>w[d] then n=w[d]
        if n>0 then
          cost += (d.deposit_fee + c) * n
          price -= d.value*n
          Add (d,n) to t
          Add (price,t,cost) to new
        if price<d.value and w[d]>n then 
          cost += d.melt_fee + d.deposit_fee + c
          if cost < best.3 then
            best = (t,d,cost)
      return new

  sort D by increasing (f[x]+c)/v[x]
  for d in D so that d.value decreases do 
    Add {(price0,{},0)} to
trys
    trys = try_denom(d)

  return best











On Fri, 2015-12-18 at 14:26 +0100, Jeff Burdges wrote:
> 
> Just to answer Marcello's question from this evening about optimal
> coin
> spending.  -Jeff
> 
> 
> 
> We have:
>   a set D of denominations,
>   a value function v : D -> R,
>   a deposit fee function f : D -> R,
>   a maximum deposit fee m>=0,
>   a refresh/melt fee function r : D -> R,
>   a wallet function w : D -> Z,
>   an unknown constant c>0 but very small,
>   and a price>0
> where f, r, and w are non-negative.  And R and Z denote the reals and
> integers, respectively.
> 
> We want to select two functions
>   spend total t : D -> Z, 
>   spend partial p : D -> Z, and
>   partial value v' : D -> R
> so as to minimize the function :
>   max(0, -m + sum_x f[x]*d[x])
>   + sum_x r[x]*p[x]
>   + c * sum_x (d+p)[x]
> subject to the constraints
>   t[x] >= 0
>   p[x] >= 0
>   (t+p)[x] <= w[x]
>   sum_x v[x]*d[x] >= price
>   sum_x (v[x]*t[x] + v'[x]) <= price
>   v'[x] <= v[x]
>   p[x] <= 1
> where d = t+p is a convenient notation.
> 
> We assume these last two because if p[x] > 1 then you could refresh
> one
> less coin.  In fact, you should never refresh more than one coin, so
> that's sum_x p[x] <= 1, but not sure we need that much.
> 
> 
> 1.  Dynamic Programming
> 
> There is a solution using dynamic programming because the problem has
> the optimal substructure property : 
> 
> If the above parameters have an optimal assignment, then replacing 
>   price := price - v[x]*t[x] - v'[x],  
>   t[x] := 0,  
>   p[x] := 0,  and  
>   v'[x] := 0
> gives another optimal solution, as otherwise we'd get a better one
> for
> the first situation.  
> 
> There is however no assurence that t[x] = price mod v[x] for some x
> in
> D, so nievely such solutions give you running times like O(price *
> > D|), which kinda sucks actually.  Just one simplified example :
>  http://www.codeproject.com/Articles/31002/Coin-Change-Problem-Using-
> Dy
> namic-Programming
> 
> 
> 2.  Greedy Algorithm
> 
> There is a greedy algorithm that runs linear time for the usual
> change
> problem, but it assumes a sane coin systems.  I have not read the
> reference 
>  http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5254395
> but presumably it assumes v[x] divides v[y] whenever v[y]>v[x] or
> something similar.
> 
> There are crazy coin systems that violate this assumption, which
> impacts Taler in two ways :
> 
> First, an obnoxious mint could make insane denominations that forced
> customers and merchants to spend slightly more, while nominally
> claiming fees competitive with other mints.  We can ignore this as
> it's
> rather obvious manipulation and an obnoxious mint cannot charge much
> more.  I think an approximation result says the mint cannot even
> double
> the fees.  
> 
> Second, there could be two mints whose denominations together formed
> an
> insane set that caused bad coin usage.  Again the results should not
> be
> too bad, but one could combat this by processing mints individually
> before considering them together.  
> 
> Now there are some additional complexities related to giving change
> and
> not knowing how to order the denominations, so maybe worth a bit more
> formalism first.
> 
> 
> 3.  Integer linear programming
> (It helps with understanding the greedy algorithm too)
> 
> We almost have an integer linear program because all these functions
> parameterized by D are simply vectors.  We just need to eliminate
> that
> annoying max(0, ), which we do by introducing a variable z.  I'm
> going
> to switch from t[x] to d[x] = t[x] + p[x] and surpress the indexes
> [x]
> here since only m, c, and z lack indexes.
> 
> Select d : D -> Z and p : D -> Z so as to minimize the function 
>   z + sum_x ( r*p + c*(d+p) )
> subject to the constraints
>   d <= w  for all x
>   sum_x v*(d-p) <= price
>   sum_x v*d >= price
>   z >= - m + sum_x f*(t+p)
> and
>   z >= 0
>   d >= 0  for all x
>   p >= 0  for all x
> 
> We should introduce slack variables so that row operations cannot
> lose
> information:
> 
> Select d and p so as to minimize the function 
>   z + sum_x ( r*p + c*(d+p) )
> subject to the constraints
>   d(x) = w - w'  for all x
>   sum_x v*(d-p) = price - price1
>   sum_x v*d = price + price2
>   z - sum_x f*d = -m + m'
> and
>   w' >= 0  for all x
>   m' >= 0
>   price1 >= 0
>   price2 >= 0
>   z >= 0
>   d >= 0  for all x
>   p >= 0  for all x
> 
> We can eliminate z with a row operation and then drop -m + m' from
> the
> objective, so that price is the only constraint set by the merchant. 
> 
> Select d and p so as to minimize the function 
>   sum_x ( r*p + c*(d+p) + f*d ) = sum_x ( (r+c)*p + (f+c)*d )
> subject to the constraints
>   d = w-w'  for all x
>   sum_x v*(d-p) = price - price1
>   sum_x v*d = price + price2
> and  ...
> 
> And those constraints could again be written as
>   d <= w
>   sum_x v*(d-p) <= price
>   sum_x v*d >= price
> 
> It's maybe now easier to visualize the greedy algorithm working when
> you think about that sum_x v*d together with this simple objective
> function.  As a bonus, we observe that c got folded into r and f,
> which
> simplifies implementing stuff. 
> 
> 
> 4.  Smarter Greed
> 
> If we're only allowed to spend one denomination at some price, then
> we
> shown the minium is achieved when that denomination x in D is chosen
> to
> minimize 
>       (f[x]+c)/v[x] + (r[x]+c)/(v[x]*d[x])*p[x]
> where p[x] = max(1,price mod v[x]).  We could approximate this by
> (f[x]+c)/v[x] under several reasonable hypotheses, not unfortunately
> r
> > > f, but price >> v[x] still helps.  In any case, there are many
> situations where minimizing (f[x]+c)/v[x] handles this single
> denomination spend.
> 
> We know from our optimal substructure property that, for an optimal
> allocation, there is a denomination x such that zeroing out t[y],
> p[y],
> and v'[y] for y not x, and adjusting the price acordingly, gives an
> optimal allocation.  It follows that a greedy algorithm that uses D
> sorted by increasing (f[x]+c)/v[x] frequently works, although not
> when
> mints charge too much for refreshes
> 
> Roughly this algorithm looks like: 
> 
> FindCoinsGreedily(price,D,v,f,m,r,w,c) 
>   set cost = 0
>       t = empty_array
>       done_cost = infinite
>       done_denom = null
>       done_t = empty_array
>   sort D by increasing (f[x]+c)/v[x]
>   for x in D do
>     let t[x] = price mod v[x]
>     set price = price - v[x]*t[x]
>     set cost = cost + (f[x]+c)*v[x]*t[x]
>     if cost + r[z]+c < done_cost then
>       set done_cost = cost + r[z]+c
>       set done_denom = x
>       set done_t to be a copy of t
>   return (done_t,done_denom)
> 
> 
>

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