Home |
Search |
Today's Posts |
#1
Posted to microsoft.public.excel.worksheet.functions,microsoft.public.excel.misc,microsoft.public.excel.programming
|
|||
|
|||
Looking for Solutions
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 |
#2
Posted to microsoft.public.excel.worksheet.functions,microsoft.public.excel.misc,microsoft.public.excel.programming
|
|||
|
|||
Looking for Solutions
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 -- Regards, Tom Ogilvy Tony Johnson wrote in message ... 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 |
#3
Posted to microsoft.public.excel.worksheet.functions,microsoft.public.excel.misc,microsoft.public.excel.programming
|
|||
|
|||
Looking for Solutions
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. -- Regards Ken....................... Microsoft MVP - Excel Sys Spec - Win XP Pro / XL2K & XLXP ---------------------------------------------------------------------------- Attitude - A little thing that makes a BIG difference ---------------------------------------------------------------------------- "Tom Ogilvy" wrote in message ... 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 -- Regards, Tom Ogilvy Tony Johnson wrote in message ... 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 |
#4
Posted to microsoft.public.excel.worksheet.functions,microsoft.public.excel.misc,microsoft.public.excel.programming
|
|||
|
|||
Looking for Solutions
Tom,
This is fantastic. Though I think you just put a few thousand accounting clerks who reconcile intercompany accounts out of work. PC "Tom Ogilvy" wrote in message ... 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 -- Regards, Tom Ogilvy Tony Johnson wrote in message ... 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 |
#5
Posted to microsoft.public.excel.worksheet.functions,microsoft.public.excel.misc,microsoft.public.excel.programming
|
|||
|
|||
Looking for Solutions
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. -- Regards, Tom Ogilvy "Paul Corrado" wrote in message ... 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" wrote in message ... 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 -- Regards, Tom Ogilvy Tony Johnson wrote in message ... 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 |
#6
Posted to microsoft.public.excel.worksheet.functions,microsoft.public.excel.misc,microsoft.public.excel.programming
|
|||
|
|||
Looking for Solutions
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. -- Regards, Tom Ogilvy "Ken Wright" wrote in message ... 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. -- Regards Ken....................... Microsoft MVP - Excel Sys Spec - Win XP Pro / XL2K & XLXP -------------------------------------------------------------------------- -- Attitude - A little thing that makes a BIG difference -------------------------------------------------------------------------- -- "Tom Ogilvy" wrote in message ... 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 -- Regards, Tom Ogilvy Tony Johnson wrote in message ... 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 |
#7
Posted to microsoft.public.excel.worksheet.functions,microsoft.public.excel.misc,microsoft.public.excel.programming
|
|||
|
|||
Looking for Solutions
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. -- Dana DeLouis Using Windows XP & Office XP = = = = = = = = = = = = = = = = = "Ken Wright" wrote in message ... 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. -- Regards Ken....................... Microsoft MVP - Excel Sys Spec - Win XP Pro / XL2K & XLXP -------------------------------------------------------------------------- -- Attitude - A little thing that makes a BIG difference -------------------------------------------------------------------------- -- "Tom Ogilvy" wrote in message ... 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 -- Regards, Tom Ogilvy Tony Johnson wrote in message ... 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 |
Reply |
Thread Tools | Search this Thread |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Forum | |||
formula copy or alternative solutions | Excel Discussion (Misc queries) | |||
Count Weekend Days solutions thank you very much to both of you | Excel Worksheet Functions | |||
Solver giving solutions with decimals | Excel Worksheet Functions | |||
IF formula with many solutions. | New Users to Excel | |||
lookup & match solutions | Excel Worksheet Functions |