Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I will give a simple example of my question then the full one. Let's say I am trying to reconcile my bank account, and have no statement. I opened it with $0 exactly, and a small number of transactions later, I have a balance. The problem is, I have no receipts, just scraps of paper, each with an amount which either could have been deposited or withdrawn, or irrelevant. How can I use matrix solving to setup and solve this problem?

Easy example: The list of papers read (in ascending order):

$$2.05, 6.32, 8.96, 19.37, \textrm{and } 25.00$$

The current account balance is 7.68.

I started to set this up into a simple matrix/vector problem, ${\mathbf{A} x = \mathbf{B}}$, where

$$\mathbf{A}=[2.05, 6.32, 8.96, 19.37, 25.00]$$ $$\mathbf{B}=7.68$$ and $$x=\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix}$$

The problem only really requires $x_i \in \{-1, 0, 1\}$. This kind of constraint confuses me. I was able to solve this problem using Excel, and the SUMPRODUCT function with the Solver Tool, and it took about 10 minutes, and came up with the solution of $$x=[1,0,0,-1,1]$$ Mathematica took 30 minutes for a similar item list (although I used a For construct because I didn't know how to constrain the values of the coefficients).

I remember my college math teacher saying things about unique solutions, etc. It's possible that you could have multiple solutions to the problem I just posed, but because of the constraint on the coefficients, the possibility is extremely low and depends on the transaction amounts.

When this is extended to say 20 "transactions", that leaves the CAS or person to $3^{20}$ calculations. I know there are matrix algorithms, and especially special forms of working with matrices especially in Excel and Mathematica (both of which I have and use regularly).

Is there a way to define this problem in Mathematica so that its awesome Matrix manipulating powers can be put to good use? And an answer produced much more quickly than this recursive brute force method?

share|improve this question

1 Answer 1

up vote 0 down vote accepted

This is essentially the "subset sum" problem, which is an example of an NP-complete problem. This means that nobody knows a good algorithm for solving large instances of it, and most experts don't expect a good algorithm will ever be found. Still, 20-transaction problems are probably not out of range of good software. Do a search for "subset sum".

share|improve this answer
    
Thanks, you helped set me in the right direction. –  tralston Mar 8 '12 at 1:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.