# Allocating Values

1. ## Allocating Values

Hello, I have a problem that I would like some help on.
In column "A" I have a list of numbers (Invoices). In Column "B" I have one large number (Lump Sum Payment).
I need to figure out how to split up the number in column "B" so that I can identify what in column "A" has not been paid for.
Is there some sort of an algorithm that can be used to determine all possible combinations that would get as close as possible to be equal to the lump sum?
If it is not exact, I would like to see the difference.

In the attached spreadsheet I have the problem that I am trying to solve on the left, and the expected result on the right.
When adding all the "Paid" numbers, they come out to be 20 cents short of the total sum. (the spreadsheet has a typo)

Thank you

2. ## Re: Allocating Values

This is actually my first venture into the Excel add-in "Solver" so there may be a more efficient approach but this does seem to work for the provided example.
• Add a sum of col-A in A11
• Add col-E to be 1 if this invoice is paid and 0 otherwise. Populate initially with zeros
• Add col-F with the following formula in F3 and copied down:
Formula:
`Please Login or Register  to view this content.`
• This simply gives the invoice value if col-E is 1 (paid) and zero otherwise.
• Add a sum of col-F in F11.
• In G11:
Formula:
`Please Login or Register  to view this content.`

Now in "Solver"
• Set objective: \$G\$11 to "Min"
• Constraints:
\$E\$3 = integer
\$E\$3 <= 1
• Repeat for E4:E10
• Choose solving method: GRG Nonlinear
• Click Solve

You will find that your expected results have been matched.

See the attached workbook.

If you need to load Solver, see: https://support.office.com/en-gb/art...c-e24772f078ca

3. ## Re: Allocating Values

Hi

To see the complexity of your problem see the resolution with all combinations
1. In your example you have 8 invoices, this is 28-1=255 combinations. I listed them in K1:K255 with the following formula
Formula:
`Please Login or Register  to view this content.`

or
Formula:
`Please Login or Register  to view this content.`

2. Convert the binary string to a sum of invoices (L1:L255) with
Formula:
`Please Login or Register  to view this content.`

3. Find the differences in M1:255 with
Formula:
`Please Login or Register  to view this content.`

4. Find minimum difference In N2
Formula:
`Please Login or Register  to view this content.`

5. Covert the value founded to binary string with INDEX or DECABIN or BASE
6. CONVERT the DECABIN to a string 'Paid' or 'Not Paid'

If each combination spends 1 nanosecond, if the number of invoices is 100 and if we ignore the space required to construct the solution we must spend ...
(2^100*1E-9)/60/60/24/365 = 4E22 years to get a probable but not exact solution.
See the file

4. ## Re: Allocating Values

Both methods work. Now I need to figure out how to make this go faster. With 8 it's not bad, but when the numbers get into double digits this process becomes inefficient.

5. ## Re: Allocating Values

Perhaps you could spend some portion of the 4E22 years to persuade your clients to say what invoices they are paying

Seriously, I think you will find José Augusto's solution much more efficient than mine. For 8 invoices his solution is fast enough to not be stopwatch measurable, my "solver" solution takes around 5 seconds.

Thanks anyway for the feedback and rep.

6. ## Re: Allocating Values

Hi GeoffW

For constraints = 1 and integer it's sometimes easier to use the binary constraint i.e

b_solv_setup.jpg

Alf

Ps Not sure if uploaded jpeg shows, have had problems with this before. If so just replace constraints with line "\$E\$3:\$E\$10=binary"

7. ## Re: Allocating Values

@alf - thanks for the hint - that's much easier!

I have had problems with uploading picture files as well. My workaround is to edit the post, delete the picture attachment and then re-upload the picture. This process seems to work reliably, at least for me.

8. ## Re: Allocating Values

You are welcome and thanks for feedback

Alf

There are currently 1 users browsing this thread. (0 members and 1 guests)