Matching Invoices to Payments

Recently one vendor received a set of checks from my business. Each check was supposed to pay for a few invoices. Unfortunately, the amounts on the checks did not match the total of the invoices listed. Worse, one check was missing the invoice numbers entirely!

What to do? Well, I could try to match the invoices to the checks manually somehow. But there were 8 checks and close to 75 invoices. It would take a really long time to figure out which checks matched which invoices.

It was time to use the computer to figure this out. I tracked down the Google Optimization Tools which has knapsack problem solving functions. I’m most experienced in programming with Java, but couldn’t get the Java version of the library working. The Python version of the library seemed to work right away when I followed the instructions.

In the end I got the invoices matched exactly to 6/8 checks. One I got to within 12 cents and the last to within an 0.5% error.

The code I wrote is below. Notes:

  1. Dollar values must be in cents, as the optimization library doesn’t support fractional amounts.
  2. The optimization library doesn’t support negative values (credits).
  3. There’s no simple way to determine which checks go with which invoices. You have to solve the whole problem at once. Then the library will let you test to see if a particular invoice goes with the FIRST check on the list. The solution:
    1. Test every invoice and see if it goes with the first check.
    2. Save matching invoices as belonging to a the first check.
    3. Remove the matched invoice from the list of all invoices.
    4. Repeat the above until you have found all matching invoices for the first check.
    5. Remove the first check from the list of checks.
    6. Repeat the knapsack solve with the newly shortened list of checks and invoices and repeat the process above.
from __future__ import print_function
from ortools.algorithms import pywrapknapsack_solver

def main():
 # Create the solver.
 solver = pywrapknapsack_solver.KnapsackSolver(
 pywrapknapsack_solver.KnapsackSolver.
 KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
 'test')
 invoices = {
# This goes (amount in cents):(invoice number)
 14104:39500,
# the rest goes here...
 15269:39836}


 weights = [[14104,
 # list of  invoice amounts in cents (reduntant with invoices, yeah)... 
 15269
 ]]

 capacities = [219081, 
#check amounts in cents ...
,173393]

 capacitiesOrig = [219081,
#check amounts in cents ...
,173393]

 matched_invoices = []
 values = weights[0]
 solver.Init(values, weights, capacities)
 computed_value = solver.Solve()
 packed_items = [x for x in range(0, len(weights[0]))
 if solver.BestSolutionContains(x)]
 packed_weights = [weights[0][i] for i in packed_items]

print("Packed items: ", packed_items)
 print("Packed weights: ", packed_weights)
 print("Total weight: ", sum(packed_weights))
 print("Current weight: ", capacities)
 print("Current weight - total weight difference: ", capacities[0]-sum(packed_weights))
 print("=====================")
 
 values = weights[0]
 for currentCapacity in capacitiesOrig:
 capacities = [currentCapacity] 
 solver.Init(values, weights, capacities)
 computed_value = solver.Solve()

packed_items = [x for x in range(0, len(weights[0]))
 if solver.BestSolutionContains(x)]
 packed_weights = [weights[0][i] for i in packed_items]
 packed_invoices = [invoices[i] for i in packed_weights] 
 matched_invoices.extend(packed_invoices)

print("Packed items: ", packed_items)
 print("Packed weights: ", packed_weights)
 print("Total weight: ", sum(packed_weights))
 print("Current weight: ", currentCapacity)
 print("Current weight - total weight difference: ", currentCapacity-sum(packed_weights))
 print("Check ", (currentCapacity*1.0/100), "invoices ", packed_invoices)
 print("");
 for delval in packed_weights:
 values.remove(delval)
 matched_invoices.sort()
 print("All matched invoices: ", matched_invoices);
 unmatched_invoices = invoices.values()
 for delval in matched_invoices:
 unmatched_invoices.remove(delval)
 unmatched_invoices.sort()
 print("All unmatched invoices: ", unmatched_invoices);
if __name__ == '__main__':
 main()
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s