Looking for Solutions
Tony Johnson
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
ton...@NOSPAMyahoo.com
Tom Ogilvy
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
--
Regards,
Tom Ogilvy
Tony Johnson <tonyj_32@*NOSPAM*hotmail.com> wrote in message
news:#4P4xjhY...@TK2MSFTNGP12.phx.gbl...
Ken Wright
this a newbie. It works a treat.
--
Regards
Ken....................... Microsoft MVP - Excel
Sys Spec - Win XP Pro / XL2K & XLXP
----------------------------------------------------------------------------
Attitude - A little thing that makes a BIG difference
----------------------------------------------------------------------------
"Tom Ogilvy" <twog...@msn.com> wrote in message news:e3iWLUiY...@tk2msftngp13.phx.gbl...
Paul Corrado
This is fantastic. Though I think you just put a few thousand accounting
clerks who reconcile intercompany accounts out of work.
PC
"Tom Ogilvy" <twog...@msn.com> wrote in message
news:e3iWLUiY...@tk2msftngp13.phx.gbl...
Paul Corrado
I did some testing, (picked 12 rows that included 0's and 1's from the first
solution, and deleted them). and found that there is an alternative
solution. So, while this method will return a solution, it is not
necessarily "the" solution. Data below also sums to $1391.03. I guess the
shortcoming results from the sheer number of possible combinations
(4.61169E+18).
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 0
21.69 1
97.48 1
19.66 1
51.25 1
11.77 1
14.31 1
5.98 0
9.2 0
11.37 1
12.55 1
3.64 1
17.01 1
50.59 1
14.3 1
3 1
109.53 1
154.88 1
13.07 1
22.65 1
11.37 1
32.84 1
42.23 1
23.6 1
0.26 0
1.03 1
21.75 1
17.97 1
22.47 1
34 1
120 1
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
PC
"Tom Ogilvy" <twog...@msn.com> wrote in message
news:e3iWLUiY...@tk2msftngp13.phx.gbl...
Tom Ogilvy
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.
--
Regards,
Tom Ogilvy
"Paul Corrado" <pcor...@theavocetgroup.com> wrote in message
news:e1w$OHmYDH...@TK2MSFTNGP10.phx.gbl...
Tom Ogilvy
It is an approach that is fairly common in Linear Programming I believe.
--
Regards,
Tom Ogilvy
"Ken Wright" <ken.w...@NOSPAMntlworld.com> wrote in message
news:uE9LH0jY...@TK2MSFTNGP10.phx.gbl...
Dana DeLouis
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.
--
Dana DeLouis
Using Windows XP & Office XP
= = = = = = = = = = = = = = = = =
"Ken Wright" <ken.w...@NOSPAMntlworld.com> wrote in message
news:uE9LH0jY...@TK2MSFTNGP10.phx.gbl...
Ken Wright
--
Regards
Ken....................... Microsoft MVP - Excel
Sys Spec - Win XP Pro / XL2K & XLXP
----------------------------------------------------------------------------
Attitude - A little thing that makes a BIG difference
----------------------------------------------------------------------------
"Dana DeLouis" <ng_...@hotmail.com> wrote in message
news:#OyI8zmY...@TK2MSFTNGP09.phx.gbl...
EZ Money
what you want:
http://myweb.cableone.net/twodays/
Download the "Find a Numeric..." file
--
Greeting from the Gulf Coast!
http://myweb.cableone.net/twodays
"Tom Ogilvy" <twog...@msn.com> wrote in message
news:Ob3xdwmY...@tk2msftngp13.phx.gbl...
Harlan Grove
..
>I then did Tools=>solver. I selected
For the usual caveats,
http://www.google.com/groups?threadm=euKZN8TMCHA.2436%40tkmsftngp11
along with the link therein.
--
Never attach files.
Snip unnecessary quoted text.
Never multipost (though crossposting is usually OK).
Don't change subject lines because it corrupts Google newsgroup archives.