Deducing item cost from totals?

Question

This can be broken down into a simple trio of equations:

a + b = 3
b + c = 5
a + c = 4

How can I best approximate the values? Note, I'll have many more such totals and variables in real applications. Particularly, I want to find if its possible to usefully approximate the cost of food by item lists and totals from grocery receipts. I assume if I can figure out costs, there will be varying ranges of accuracy I can expect, so an extra would be knowing how likely the approximation is to be correct and within what range the price must be.

EDIT: I just don't see this getting an answer I'm comfortable with, because I failed to properly frame the question in the first place.

Answer 1

You are dealing with a system of linear equations, to solve it:

http://www.codeproject.com/KB/cs/LinearEquationsSystemSoln.aspx

The basic idea is to build a matrix of coefficient in the equations and use LU decomposition or Gaussian Elimination to deduce the values of variables. LAPACK can help.

Follow up: LAPACK is a full featured library for dealing with all kind of linear algebra stuff (and it's damn efficient at this, there are also GPU based libraries, such as CUBLAS which runs on NVIDIA GPUs using CUDA).

If you are dealing with same number of equations than unknowns, you'll be dealing with simple equation solving solution.

Basically, if you have more unknowns than equations, you'll be dealing with something called underdetermined system. Similarly, you might be dealing with systems with more equations than unknowns (overdetermined systems). If you have an underdetermined system, you probably want to look for a minimum norm solution (there can be infinite number of solutions to a single underdetermined system). For overdetermined systems, we might be looking for so called least squares solution. For more info about these solutions, look at this: http://www.netlib.org/lapack/lug/node27.html. These concepts are from linear algebra.

Answer 2

If you're using .NET, check out Microsoft Solver Foundation. This post provides a sample of how to use it to solve linear equations.

Answer 3

A more general solution to this problem where you could have more equations than unknowns would be to find the Linear Regression/Least Squares solution. The regression statistics will give you the information you need about the accuracy of the results.

Answer 4

For Fun:

a+b=3 | a=3-b | a=3-(5-c) | a=c-2 | a=(4-a)-2 | 2a=2  | a=1   |       |
b+c=5 | b=5-c | b=5-c     | b=5-c | b=5-c     | b=5-c | b=5-c | b=5-3 | b=2
a+c=4 | c=4-a | c=4-a     | c=4-a | c=4-a     | c=4-a | c=4-1 | c=3   |

Answer 5

If you have more variables than equations there will be an infinite number of exact solutions, and the possible values will be all over the place, not a useful approximation.

You need at least as many equations as variables, and substantially different ones (just copying one equation a few times won't help). So if you have fewer equations than variables it won't work, otherwise look for a statistics or linear algebra library.

Answer 6

For a square system like this, you can solve the matrix equation

| 1 1 0 ||a| |3|
| 0 1 1 ||b|=|5|
| 1 0 1 ||c| |4|

providing the matrix on the left is invertible, as this on is.

Generally, though, you will either have too many variables, or two few variables. Two many equations is better, since the Least-Squares approximation is available. To find the least squares solution, solve the normal equations A^TA x = A^Tb for x, where x = (a, b,c), b = (3,5,4), and A is the coefficient matrix. Note that the superscript T refers to the transpose of the matrix.

I'm sure there is some code out there that accomplishes this.

When the system is underdetermined, though, you will have infinitely many solutions, even assuming a, b, and c are positive.

Answer 7

For the range in which a price must be, use a Linear Programming solver in your favorite numerical algebra system. Your equality constraints are the individual equations from the receipts; in addition you will want to add inequality constraints to guarantee that each price is nonnegative. To find the possible price range of item X, set your objective function to the price of X, and solve for the minimum and maximum separately.

This approach may fail if an item can have different prices on different receipts; the linear program may become infeasible, or there might be more subtle effects.