I have often wondered whether there is an optimal way to spend cash denominations. For example: Suppose that Bob needs to pay Jill \$5, Jane \$10, Billy \$3.50 and John \$45.75. Furthermore suppose that Bob currently has in his position a single $100 dollar bill. Assuming that any one of the payees can give Bob change in any combination of denomination he wants, what is the optimal "path of payment" to take?

Granted in the example given above, the solution can be achieved by inspection very quickly but what if we take that example, scale it up massively and introduce some restrictions? Suppose Bob needs to pay thousands of payees, what is the optimal order of payees to pay for Bob and what form of change denominations should he request from the first person he is paying, to maximise the number of people he could pay in the second round? Given that he is only allowed to pay a fixed number of people at a time.

In some of the discussions I have had with people, dynamic programming seems to be the best place to start. This could lead to Reinforcement Learning as a possible approach (because this problem probably will be solved heuristically). My thought is that there could possibly be an algorithmic way to approach this which is simpler than the two methods above.

However, I am also pretty confident that others have also thought of this problem. My question then is, is this a solved problem?

P.S.: I am a grad student in my last semester of IE. I need to make up a couple of credits and instead of taking some kind of TE, my advisor has given allowed me to replace the coursework with an independent study. His words to me were; "Think of a weird nuanced problem in OR that's probably not too difficult to solve, have fun with it and give me a term paper on what you have done". So I figured it would be a perfect time to attempt the "Cash spending problem".

  • 4
    $\begingroup$ Well, if we assume that Bob has enough money to pay the payees and that the payees can give back any change Bob wants, then the safest option is to pick one payee at random (or for ex. the payee with the highest amount) and have the payee return all pennies (if payee with max amount chosen will result in least amount of pennies), then Bob will have enough granularity to pay everyone else. $\endgroup$ Commented Sep 29, 2022 at 5:56
  • $\begingroup$ If there is a restriction on periodic budget (e.g. 100 each month) and payments are scheduled to be finished as early as possible (e.g. minimize latest payment period) then we can talk about a "dynamic knapsack" (not sure if it is the correct term) problem. $\endgroup$
    – berkorbay
    Commented Sep 29, 2022 at 6:41
  • $\begingroup$ @user2974951 I would call that more of a workaround than a solution, albeit a safe one at that. If one introduces a granularity cost function such that a cost is incurred every time a payee receives money in smaller denominations than the amount they should receive, then that would likely be the least optimal solution. $\endgroup$ Commented Sep 29, 2022 at 16:48
  • $\begingroup$ @berkorbay Interesting! One of the suggestions I got from a colleague of mine was to look at variations of the knapsack problem as they could hold an answer. $\endgroup$ Commented Sep 29, 2022 at 16:50
  • $\begingroup$ Knapsack problem? $\endgroup$
    – Dave
    Commented Jan 5 at 2:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.