My own accounting python euler problem

[John Machin]

In the accounting department I am working for we are from time to time
confronted to the following problem:

A customer sends us a check for a given amount, but without specifying
what invoices it cancels. It is up to us to find out which ones the
payment corresponds to.

For example, say that the customer has the following outstanding
invoices:  $300, $200, $50; and say that the check is for $250. This
time it is clear, the customer is paying bills $200 and $50.

However, let's now say that the outstanding invoices are $300, $200,
$100 and that the check is for $300. In this case there are already
two possibilities. The customer is paying the $300 invoice or the $200
and $100. In other words, there is more than one solution to the
problem.

The problems that you mention are only a SUBSET of the total problem.
Example: oustanding invoices are for 300, 200, and 100 and the cheque
is for 450 -- in general the total of the cheque amounts does not
equal the total of any possible selection of outstanding invoice
amounts.

I would be very surprised if a real accounting department did not
already have a set of business rules for dealing with a problem that
has existed since invoices and cheques were invented.

I would be extremely surprised if a real accounting department could
be persuaded to imagine a subset of their unpaid/underpaid/overpaid
invoice problem as being an instance of the (extended) knapsack
problem

 

[John Machin]

In the accounting department I am working for we are from time to time
confronted to the following problem: [snip]

My second question is:
2. this time there are also credit notes outstanding, that is,
invoices with negative amounts. For example,  I=[500, 400, -100, 450,
200, 600, -200, 700] and a check Ch=600

How can a credit note be "outstanding"? The accounting department
issues a credit note without recording what invoice it relates to?

 

[Raymond Hettinger]

[vsoler]

In the accounting department I am working for we are from time to time
confronted to the following problem:

A customer sends us a check for a given amount, but without specifying
what invoices it cancels. It is up to us to find out which ones the
payment corresponds to.

For example, say that the customer has the following outstanding
invoices:  $300, $200, $50; and say that the check is for $250. This
time it is clear, the customer is paying bills $200 and $50.

I worked on a similar problem involving frequent bank deposits
(the bank recorded only the amount of the deposit with no other
tracking
information to let us know which store made the deposit) and
reconciling
those deposits to general ledger entries.

As pointed-out by others, the purest statement of the problem is
computationally unfeasible; however, the real-world application
can provide useful heuristics to that limit the search space.

1) Dates can be used to provide some alignment. Customers tend
to pay the oldest invoices first and they don't pay before the first
invoice is sent. Also, there can be a typical time lag that helps
identify where to start a search (i.e. the customer typically takes
45 days to pay an invoice).

2) Search smallest groupings first (eliminate exact matches) then
groupings of two items and groupings of three items.

3) Sometime the values on the list possess properties that make
them stand-out and easier to match-up. Given invoices of
[10, 11, 12, 1000, 13, 14], the 1000 should be easy to match-up
in any grouping of payments. Likewise, when looking for groupings,
start with the most unique values. Given [2, 2, 2, 3, 3, 5, 5, 5,
6.1, 7],
start by trying to match the 6.1 since there is only one occurrence.


Raymond

 

[Steven D'Aprano]

The problems that you mention are only a SUBSET of the total problem.
Example: oustanding invoices are for 300, 200, and 100 and the cheque is
for 450 -- in general the total of the cheque amounts does not equal the
total of any possible selection of outstanding invoice amounts.

I would be very surprised if a real accounting department did not
already have a set of business rules for dealing with a problem that has
existed since invoices and cheques were invented.

As a sometimes accounts department, let me put my hand up for that.

Yes. Generally the rule is, "call the damn customer and ask them what
they're smoking", only more politely.

Usually they'll have some convoluted breakdown of what amount they are
paying off each invoice. Sometimes they will have taken off a settlement
discount for prompt payment (often whether or not they actually paid
promptly). Sometimes they overpay, or underpay, or apply credits to the
wrong invoice, or pay invoices twice, or pay the wrong amount, or just
make up a number from thin air. Sometimes they themselves will have no
idea what the amount represents. And, I can guarantee, they will *ALWAYS*
use a different rounding scheme to whatever accounting software you use,
so there's always odd one or two cents that need to be manually adjusted
somewhere.

I would be extremely surprised if a real accounting department could be
persuaded to imagine a subset of their unpaid/underpaid/overpaid invoice
problem as being an instance of the (extended) knapsack problem

That's because the average accounting department is mathematically
illiterate

Nevertheless, many accounting software packages, like Quickbooks, will
take a wild stab at allocating payments for you, usually using some
variation of "if you can't find an exact match for a single invoice, just
blindly allocate it to the oldest invoices you can". Frankly, I'd much
prefer a knapsack solution.

 

[Steven D'Aprano]

In the accounting department I am working for we are from time to time
confronted to the following problem: [snip]

My second question is:
2. this time there are also credit notes outstanding, that is, invoices
with negative amounts. For example,  I=[500, 400, -100, 450, 200, 600,
-200, 700] and a check Ch=600

How can a credit note be "outstanding"? The accounting department issues
a credit note without recording what invoice it relates to?

Yes, that can happen.

(1) Human error, or laziness, or dumb software that doesn't understand
credits apply to specific invoices.

(2) The credit note represents a settlement discount, rebate,
"advertising allowance" or other kickback, or similar.

(3) An invoice is paid in full, then later the client claims a refund
against it. If granted, the credit can't be applied to the invoice that
is already flagged as paid, so it remains as an "unallocated" credit note.

(4) Or simply that the boss forbids you from allocating credit notes
until payment is received.