Looking for Solutions

  • Thread starter Thread starter Tony Johnson
  • Start date Start date
T

Tony Johnson

Thanks for taking the time to read this. Here is my question Lets say I have
a column of numbers to choose from to equal a certian amount. Problem is I
do not know how many of these I need to add together to get the required
number. Here is an example
29.55
26.77
46.94
5.99
16.8
15.93
20.56
13.57
4.44
21.69
97.48
24.15
3.38
133.48
48.82
1.94
24.15
126.1
71.83
32.92
46.57
88.12
132.49
19.66
51.25
11.77
14.31
5.98
9.2
11.37
12.55
3.64
17.01
50.59
14.3
3
109.53
154.88
13.07
22.65
11.37
32.84
42.23
23.6
0.26
1.03
21.75
17.97
22.47

34
120
63.55
3.68
75.46
26.98
15.88
8.86
30.1
25
23.7
19.97
12.67
I have to figure out what combination of those numbers equals 1391.03

Is there a way for excel to choose random combinations till it finds the
answer?

Thanks in advance

(e-mail address removed)
 
I arranged your data like this (A1:B62) (this is actually the solution).
Each number was in column A and column B contained 1's (B1:B62) (I took
out any rows with spaces).

I created defined names

Insert=>Name=>Define

Name: Data
Refers to: =Sheet1!$A$1!$A$62

Name: Flag
Refers to: =Sheet1!$B$1!$B$62


In D1 I put in the formula

=SumProduct(Data,Flag)


I then did Tools=>solver. I selected

Set Target Cell: = *$D$1*

Equal to: Value of *1391.03*

By Changing Cells *Flag*

I clicked Add Constraints

In the first box I put *Flag* and selected *bin* from the dropdown

I then told solver to solve (Clicked the solve button) in the below, the
numbers with a 1 next to them sum up to 1391.03






29.55 1
26.77 1
46.94 0
5.99 1
16.8 1
15.93 1
20.56 1
13.57 1
4.44 1
21.69 1
97.48 0
24.15 1
3.38 1
133.48 0
48.82 1
1.94 0
24.15 1
126.1 1
71.83 1
32.92 1
46.57 1
88.12 1
132.49 0
19.66 1
51.25 1
11.77 1
14.31 1
5.98 1
9.2 1
11.37 1
12.55 1
3.64 1
17.01 1
50.59 1
14.3 1
3 0
109.53 0
154.88 0
13.07 1
22.65 1
11.37 1
32.84 1
42.23 1
23.6 1
0.26 1
1.03 0
21.75 1
17.97 1
22.47 1
34 1
120 0
63.55 1
3.68 1
75.46 1
26.98 1
15.88 1
8.86 1
30.1 1
25 1
23.7 1
19.97 1
12.67 1
 
I love it. Tom, have I been blind and missed this on an earlier post of yours at any time, or is
this a newbie. It works a treat.
 
Tom,

This is fantastic. Though I think you just put a few thousand accounting
clerks who reconcile intercompany accounts out of work.

PC
 
as you point out, this method does not find all solutions - only 1 if one
exists. I assume one could write an algorithm that used it against subsets
of the data to find additional - but to find all possible, I would think one
would need to intelligently enumerate all feasable possibilities and test
them.
 
I have posted it before, but I certainly don't claim to be the inventor.
It is an approach that is fairly common in Linear Programming I believe.
 
Just some additional thoughts if interested. This is how the operations
management types solve these types of problems.
For these types of problems, here are some additional ideas for discussion.
Under Solver Options, select "Assume Linear Model." In some problems, this
can increase the speed. This set of data is fine, but in others, this makes
Solver operate much faster. Although not really necessary, I like to select
"Assume Non-Negative." I did not observe any timing differences for this
problem though.

When solving for an exact number, keep the following in mind. I like to
have an additional Column that Rounds the Binary data as a "Check." Using
Tom's excellent idea, make a third column that Rounds the Binary data.

=ROUND(Flag,0)

This gives an exact 0 / 1.

Now, have an additional formula like the Target Cell.

=SumProduct(Data,RoundedFlag)

Because Excel's Solver does not use exact 0/1, this is a way to check your
answer. As an example, when Solver's Precision option was set to 0.001, I
had a Target Cell of 1391.03, which is good. However, some of the "Flags"
were really 0.99901... etc. However, a final check of the real answer was
off by 0.08.
Increasing the Precision to 0.0001, and both solutions returned 1391.03.

There are multiple solutions in this example. The fact that there are two
11.37 numbers contributes to this. In a VBA routine that looks for multiple
solutions, one usually grabs the solution, and adds this back as a
constraint. For example, suppose that the Flag for B1:B5 (all 1's) was the
exact solution. You would add that B1+B2+B3+B4+B5 <5. (or B1:B5<=4, or
perhaps B1:B5<=4.5 to take care of rounding issues) To find an additional
solution, one (or more) of those solutions would have to leave to make room
for an additional solution.

A dedicated optimization program would recommend scaling all the given
numbers by 100. However, this does not work well for Excel, due to the
nature of a spreadsheet. In other words, one would normally multiply
everything by 100 to get exact integer numbers (not integer data
types ->32,768)

2955 (from 29.55)
2677
4694
599
....etc
and search for a total of 139103.

Other programs would recognize this as integer, and bypass the slower double
precision multiplications. Also, the 0/1 would be exact also, so there
might not be multiplication anyway...it would either return the number when
1, or return zero if 0. Excel has to do the A1*(1 or 0) multiplication
either way.
In Excel however, in some financial modeling, where dollars and cents are
needed, scaling such numbers by 100 are an excellent solution.
 
Back
Top