Finding small amounts from a larger total

[Guthro]

A customer pays a cheque of x pounds.
The customer has y number of outstanding invoices.
The whole value of the cheque pays off some of the invoices completely.
The customer is an unhelpful swine and doesn't detail the payments.
Is there some test that can determine which invoices from y that the payment x covers ?

Does that make sense ?

My Feeblegirl.com Forum boards for mmorpgs, sport, fun, politics...

http://www.jediknightsforum.com

 

[ChrisHunt]

It should be possible to try all combinations of the outstanding invoices until one is found which adds up the necessary amount. There's no guarantee that the combination that you find is the one that the customer meant to pay though.

-- Chris Hunt
Webmaster & Tragedian
Extra Connections Ltd

 

[monksnake]

I can only think of using a brute force method on this type of situation.



<.

 

[towerbase]

I think you can do better than brute force.

Something like the following algorithm should work.

Store the invoices in an array called Inv. Sort Inv into ascending order of pounds.

x is the amount of the cheque in pounds.

Locate the highest value in Inv that is less than or equal to x, keep a note of it and subtract that value from x.

Repeat the above until either x is zero (in which case you have found a solution - there may be several solutions) or you have reached the smallest value in Inv and x is not zero (in which case you need to start again (resetting x to its starting value) but this time use the next highest value in Inv as your starting point.

I could code it in Pascal if you really need it.



Andrew
Hampshire, UK

 

[monksnake]

That is a good point towerbase, but that is assuming that the check (cheque?) value is not more than the highest single invoice amount.

<.

 

[towerbase]

I don't think that my algorithm makes any assumptions about the value of x or the values in the Inv array (except perhaps that they should all be positive).

Andrew
Hampshire, UK

 

[ChrisHunt]

I don't think your algorithm will work (though it's probably somewhere in the right direction), towerbase. Consider the case where they've paid £20 and there are invoices for £10, £7, £6 and £4. As I understand you, you'll knock off the £10 and the £7, and never realise that there's a 10+6+4 solution.

I think you're right in implying that proper ordering could ameliorate an otherwise brute-force operation. Clearly any invoice that exceeds the amount of the cheque should be excluded, but I think the invoices should be considered in date order (oldest first) somehow - as they're more likely to be settling an old invoice than a new one.

-- Chris Hunt
Webmaster & Tragedian
Extra Connections Ltd

 

[towerbase]

You're right Chris, it doesn't work all the time. In my defence, I did say

Something like the following algorithm should work

I suspect that a neat recursive algorithm exists which would work and not be as inefficient as brute force. Unfortunately, I don't have the time to investigate further at the moment - but this looks like an interesting little problem.

Perhaps Guthro will indicate whether invoice date should be considered but this might resolve itself to simply paying off the oldest invoices in strict chronological order which is not very interesting ...

Andrew
Hampshire, UK

 

[Glenn9999]

A lot of this depends on how you want to approach it. You'd almost have to make some assumptions to get away with handling things.

1. Do you take the largest always first, or try for a best fit?
2. Smallest first to try to take out the largest # of invoices with the payment (this algorithm would take care of ChrisHunt's hypothetical situation)?
3. Brute force?
4. (another suggestion) test each of your invoices for divisability (is payment amount mod invoice amount = 0?) Actually this might be the ticket for the best way to handle this, test each one for divisability, if total invoice is even, always consider even numbers unless you use two odd numbers (which always add up to even).

(I did a floppy disk fill program a long time ago which involves the same problem (a best-fit algorithm), roughly. It's an interesting one.)

 

[Olaf Doschke]

Hi,

like Chris suggested it's a good assumtion the user has paid the oldest invoices. So a good start would be add up all invoices and subtract the newest one(s) to see if that matches.

Another reason why the paid amount does not fit would be a typo in the paid amount vs. sum of invoices.

Bye, Olaf.

 

[monksnake]

I would assume along with oldest invoices paid that they tried to pay off as many as they could in one payment, hence, start with all the lower amounts that are older invoices.

It's a mental thing to pay off as many invoices as you can, so you have the least amount of invoices left, regardless of the amounts of those invoices.

<.

 

[TheRambler]

Here's how to do it using Excel solver.

faq68-4742

 

[chrissie1]

Oh my, Excel solved it. The world is coming to an end.

Christiaan Baes
Belgium

"My old site" - Me

 

[Rofeu]

Hi,

although the solver works a treat if you just need one random combination that adds up, it might result in something very unlikely and possible combination can be so numerous that you can't get all.

(we've customers with over 1200 open invoices of which various with identical value)


I've tried once to create an algorhitm for this very issue.

I did manage to get something that would give me a series of likely results if there were any.

Points that can help to optimize are:

Credit notes are likely to be included. So one option is to add all the negatives to the paid amount.

Invoices that are disputed will not be included in the payment, so those can be taken out.

Customers are likely to pay the invoices according to due date.
So start with the oldest and then start adding the values of the consecutive invoices.

I don't have the actual code anymore, but if I remember correctly, I started at invoice 1, then incremented the range until it started exceeding the paid amount, read in all of the credit notes and tested if I could get to the amount by reducing the amount with those, until I got below again and then started incrementing again, etc. etc. I also built in 3 wildcards values that could be either taken out of the current range or added from outside of that range. Once I'd run out of options for the current series, I started decreasing the range from the bottom until I got below the amount again at which point the range started incrementing from the top again and so on.

Unfortunately, the number of permutations made it a rather lenghty process, i.e. 100 Invoices would take over 2.5 hours, but I did get a 75% hitrate and I wasn't that proficient in VBA at the time, so I'm sure that the code could have been tuned quite a bit.

Hope this helps you somewhat.

Cheers,

Roel

 

[Guthro]

Some useful thoughts there guys.

Invoices are mostly paid oldest first yes, but the whole problem arises when the customer misses one and it tends to be one of the oldest. There's no way of knowing this until their payment is resolved to various invoices, which brings us back to the original problem.
Maybe if there are duplicate values to unpaid invoices, the oldest would be set as paid first, just to clear that from the total.

My Feeblegirl.com Forum boards for mmorpgs, sport, fun, politics...

http://www.jediknightsforum.com

 

[maxhugen]

It may be a matter of the philosophy of the Accounts department... one I know of applied any payment where the Invoices weren't specified to 'oldest first'. This regularly meant that some Inv ended up with a 'part' payment.

In the case I mention, they were in the building industry, and tradesmen (who were the client's customers) often paid whatever was 90 or 60 days overdue on their monthly statements! Or, they just paid 'something' towards their total liability.

Max Hugen
Australia

 

[cjelec]

I don't know if this thread is still relevant? But,

From what I know, accountants work this by:

1) Sort the invoices ascending by the Due Date*.
2) Starting from the top, pay off as much as the payment allows.
3) On the final one if there isn't enough money to pay it in full, put the remaining money down as Amount Paid** against the invoice.

* Due Date gives the customer a time period to pay the invoice. It is usually 30 days but can be different depending on the t&c of that transaction. It is sorted by Due Date because for example:
Invoice 1 might be on 01/07 (US 07/01) and invoice 2 on 10/07 (US 07/10), but invoice 1 has a 30 day due date and invoice 2 has a 14 day due date. So invoice 2 is due first and should be paid first.

** The Amount paid field allows multiple payment to be made on an invoice. It gives you a balance if you subtract it from the Total.

 

[ESquared]

I suspect that a neat recursive algorithm exists which would work and not be as inefficient as brute force./quote]
I am sure there are algorithms which give reasonable results, but I don't believe there is one which can truly do the job exhaustively, without some form of brute force involved.

In mathematics this type of problem is called "packing."

[COLOR=black #d0d0d0]When I walk, I sometimes bump into things. I am closing my eyes so that the room will be empty.[/color]

 

[Olaf Doschke]

The only thing I can think of, that optimizes it relative to brute force is, to only try to compose X pounds out of those Y number of outstanding invoices, which amounts are lower than or equal to X.

So sorting the outstanding invoices by their amount helps.

That can be done recursively and even if X is greater than all Yi amounts, you will not try every combination of Yi to match to X.

Bye, Olaf.