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:
- Dollar values must be in cents, as the optimization library doesn’t support fractional amounts.
- The optimization library doesn’t support negative values (credits).
- 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:
- Test every invoice and see if it goes with the first check.
- Save matching invoices as belonging to a the first check.
- Remove the matched invoice from the list of all invoices.
- Repeat the above until you have found all matching invoices for the first check.
- Remove the first check from the list of checks.
- 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()