Help navigating SQL Server 2008 database?

95 pts.
Tags:
SQL Server 2008
SQL Server 2008 administration
SQL Server database
SQL Server tables
VB.NET
Hi all,

I'm facing an interesting challenge...

Lets say: I have a payment coming in and of course my client has not specified which of the 45 open invoices he is paying. The amount does not match any single invoice so it has to be a combined payment for 2 or more invoices. Now, I can get my calculator out and try my hand at finding the combination of amount that total up to my payment amount... but uhm... that just sucks! So, being a 'gifted' programmer I set to work... but end asking the question here...

Could anyone guide me in a direction that would help me find the right combination of numbers that add up to a certain other number? bare in mind: 1) the numbers I'm looking through to get to the right amount might be positive, negative or mixed 2) the payment may be a combination of anything up to X amounts (lets say...? 10...?) 3) I'm running SQL Server 2008, all the numbers are neatly stored in tables 4) I could step out of my database and do the logic somewhere else (VB, .Net, Javascript, ....)

Help.... ;)

Answer Wiki

Thanks. We'll let you know when a new response is added.

Fascinating problem…

This can be solved by applying some simple rules and a recursive stored procedure.

First, I would decide to apply a rule that says we will apply the payments to the oldest invoices first. That means that to solve this, I would retrieve the account records for all open invoices into an internal temporary table in date order. This temporary table will be visible to the recursive procedure, and should contain (at least) a rownumber (e.g., 1..45), the invoice key (back to the main tables), the invoice amount (+ or -), and a “flag” column as to whether it is “involved” in the current solution attempt.

Unfortunately, if you have to allow for open invoices with negative (credit) amounts, that makes the recursion inefficient, as you essentially need to evaluate EVERY combination of open invoices, instead of stopping when the payment is less than the sum of the current set of invoices being evaluated.

*** NOTE *** in actually testing the following, realized a couple of important points:
1. SQL Server only allows 32 levels of recursion – ergo, if you have more than 31 open invoices for an account, this will fail. This probably isn’t a limiter, because of the next point.
2. Because of the need to evaluate ANY combination of open invoice amounts, the recursive approach below is an N-factorial solution. If you have 10 open invoices, this could require 3.6 Million evaluations, 20 open invoices and you are looking at 2 Quintillion evaluations. Effectively, any more than 10-11 open invoices will take too much time to evaluate.
3. If the payment was for a single invoice that was NOT the oldest, the recursive approach will unfortunately evaluate all combinations with the oldest invoice first. If you had 10 open invoices and the payment was for the second oldest, you will evaluate 9-factorial combinations before finding that it matches invoice #2′s amount.
4. If all else fails, consider implementing some form of partial payment processing – clear the oldest invoices forward until you run out of payment and stop, leaving the last one with a partial pay (or partial owe).

So – while the code below will work, a more efficient, but more complicated approach would be:
1. Try to match the payment against any single invoice amount. (Probably wins most of the time.)
2. Try to match the payment against any pair of invoices. This is much less than N-factorial. (Algorithm not provided – left as an exercise for the student!)
3. At this point, do the full recursive evaluation, BUT recognize that it will probably never finish if there are more than 10 open invoices. In this case, I would probably try getting the oldest 10 and giving up if it didn’t satisfy any combination of those.

<pre>create table #invoices (
ix int, — a local 1..n index for accessing records in this table
invoicepk int , — or whatever your primary key to your invoice table is
amt decimal(18,2), — to hold the invoice amount
isused bit — true if this invoice is “participating” in the solution, else false
);</pre>

The main procedure would take at least two arguments – Account number for the payor, and the payment amount. Depending on what else your system needs to do, it could either directly mark the records as paid, or be a table-returning function that returns the invoices to be cleared by the payment.

The procedure would retrieve all open invoices into the internal table, setting the “ix” field to 1..<count of record>, and resetting the “isused” bit to false.

Then, the body of the main procedure is as follows:
<pre>declare @i int;
declare @maxrow int;
declare @remamt decimal(18,2);
set @i = 1;
select @maxrow = max(ix) from #invoices;
set @remamt = <payment amount>
exec @result = myRecursiveProc( 1, @remamt, @maxrow );
if @result = 0
– then we found a solution
– at this point, the set of #invoices records with isused=1 is the answer
– return the list of invoice keys
select invoicepk from #invoices where isused = 1;
else
– oops – payment doesn’t match any combination of open invoices
select null;
end;</pre>

The recursive procedure is as follows:

<pre>create procedure myRecursiveProc (
@row int,
@remamt decimal(18,2),
@maxrow int
)
as
begin
declare @invamt decimal(18,2);
declare @locremamt decimal(18,2);
declare @nextrow int;
declare @result int;
— note – bail if the answer is ALREADY 0 here
if @remamt = 0
return 0;
update #invoices set isused = 1 where ix = @row;
select @invamt = amt from #invoices where ix = @row;
set @locremamt = @remamt – @invamt;
— now – three possibilities
— = 0, done, we found a solution
— <> 0 and @row < max(ix), not done, try the next invoice
— <> 0 and @row = max(ix), this solution cannot work, pop up and try a different combination
if @locremamt = 0
return 0; — yeeha! solved – done
if @row = @maxrow
begin
update #invoices set isused = 0 where ix = @row;
return -1; — nogo, pop-up and try another combination
end;
— call us to try with the remaining invoices
set @nextrow = @row + 1;
exec @result = myRecursiveProc @nextrow, @locremamt, @maxrow ;
if @result <> 0
begin
— unmark this record, try again
update #invoices set isused = 0 where ix = @row;
— try with remaining invoices, but with *original* remaining amount
exec @result = myRecursiveProc @nextrow, @remamt, @maxrow ;
end;
return @result; — doesn’t matter what result here, pop up and let next level deal
end;</pre>

There are more elegant ways to code this, but the logic above should be easy to follow.

Discuss This Question: 7  Replies

 
There was an error processing your information. Please try again later.
Thanks. We'll let you know when a new response is added.
Send me notifications when members answer or reply to this question.

REGISTER or login:

Forgot Password?
By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy
  • carlosdl
    I don't think you are going to find an efficient way to do that, and I don't think you should rely on such a method if you find it. Say you have 5 invoices: 1) $100, 2) $100, 3) $50, 4)$50, 5) $150 If you want to apply a $200 payment, are you going to apply it to invoices 1 and 2, or 1 and 3 and 4, or 3 and 5, or 4 and 5, etc ? I think some policy should be defined, so you don't have to guess what invoices you have to apply the payment to.
    69,045 pointsBadges:
    report
  • Palloquin
    Hey Carlos, Thanks for your input! I agree with you that this is not a desired *first* way to do things. But, when all automatic fail-save options fail, I need to let someone book the invoices manually, and I would like to make this manual booking easier by being able to suggest possible combinations that will match up to the desired amount. Obviously, I will only be searching through invoices that have passed the 'do they belong to this client' check. Usually, our invoices will not be neatly rounded to $50 amounts (that would make matching them by hand very doable), but they will be amounts like $79.32 and $182.14 etc... I'm curious to hear if there are any mathematical or programming algorithms that would be able to help me solve this...
    95 pointsBadges:
    report
  • Palloquin
    Hey Kccrosser, Wow... that is some answer, and some code for me to try and comprehend! It's close to midnight here, will spend tomorrow trying to get this to work for me. Thank you so much!
    95 pointsBadges:
    report
  • Palloquin
    Reading your solution, without having tried it yet, I'm thinking about how the process could be speeded up. some of our clients might have 20, 30 or even more open invoices... Here's my first notion. What if I do a pre-check on all the available invoices. should there not be any negative ones (no credit invoices, which will be the case most of the time), I could perhaps choose to order the invoices from high to low and stop recursion as soon as I would exceed the total of the payment... The might be some other tricks to speed things up be using some kind of prediction.... let me sleep on it ;)
    95 pointsBadges:
    report
  • carlosdl
    If business rules allow it, I think the partial payment would be the best option (using some prioritisation criteria, which is usually the invoice date). If not, you might want to think of way to let the client specify the invoices he/she is paying.
    69,045 pointsBadges:
    report
  • Kccrosser
    Hi Palloquin, Yes, as I noted above, if there were no credit invoices, you could have the algorithm stop whenever it exceeds the sum of the evaluated invoices. That will significantly reduce the number of evaluations. (More like order N^2 instead of N-factorial.) There are a couple of reasons I suggested processing oldest invoice first: 1. Usually there are additional fees associated with late/overdue invoices. If you start clearing invoices on a LIFO basis, customers might get cranky when you charge them fees on older invoices. 2. Customers tend to pay invoices in time received order - chances are that a payment was for the earliest outstanding billings rather than the latest. Good cash flow management usually means you don't pay your bills any earlier than is required to avoid paying late fees. I thought about also rolling up all the credit invoices first and "adding" that amount to the payment, then only evaluating the invoices with amounts due (so you can stop evaluating when the sum of the invoices exceeds the payment+credit amount), but that will fail if one or more of the credit amounts was NOT taken into account in the payment. A more complex algorithm may be best, like (all comparisons are done in oldest-first order): 1. Try to apply the payment to a single invoice - this requires only N comparisons. 2. If there are any outstanding credit invoices, add the sum of the outstanding credit invoices to the payment and try to apply the payment to a single invoice - another N comparisons. 3. If there are multiple credit invoices outstanding, try For i = 1 to num_credit_invoices credit_sum = sum(credit_invoice1..credit_invoicei) payment_sum = payment + credit_sum run recursive algorithm on amount due invoices - stopping the recursion whenever the sum of the invoices exceeds the payment_sum (order N^2 evaluations) 4. Run the full recursive algorithm on the first X (10-12?) invoices. 5. Give up (or do a partial payment).
    3,830 pointsBadges:
    report
  • Palloquin
    Hey guys... This one will take me a while. The client has chosen to not have a procedure that helps in suggesting, but will to it all by hand, since they expect it will be not that often that real difficult problems arise... I will try to built this in my spare time though... It sounds like an interesting problem that should be solvable, My basic idea: If I can solve it manually, all I need to do is analyse what I do, and explain that to the stupid computer ;) The 'basic' code by Kccrosser is a great start, and recursion is the only viable option here I suppose... Thank you, and I'll return here when I've had time to complete this (or need help ;) )
    95 pointsBadges:
    report

Forgot Password

No problem! Submit your e-mail address below. We'll send you an e-mail containing your password.

Your password has been sent to:

To follow this tag...

There was an error processing your information. Please try again later.

REGISTER or login:

Forgot Password?
By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy

Thanks! We'll email you when relevant content is added and updated.

Following