Finding the combination that adds up to a certain value

[kpmg_lc_analyst]

Is there a function in Alteryx similar to Excel Solver that would allow me to find the combination of values that sum up to a certain value?  I have about 250 values and I need to see what combination equals a certain value.  Thanks in advance. 

[JohnJPS]

I don't know of a solver; a similar question was asked a while back, here:

https://community.alteryx.com/t5/Advanced-Analytics/Replicating-quot-Goal-Seek-quot-functionality-fr...

For that, solutions specific to that question were provided in R or as an Iterative Macro; these would need to be modified to apply to your problem.

[RodL]

I haven't had a chance to do much with them yet, but you might want to explore the latest tool set in the Prescriptive category (in 10.6).

There is an Optimization tool there along with Simulation tools.

[jdunkerley79]

Mostly for fun, as an exponential complexity problem, tried to do the brute force method using simple tools:

Takes < 2 minutes at 22 numbers. 

Also did one using @AdamR_AYX dynamic formula tool. Takes 11s - but will scale exponentially and max out at 63 values at the moment (as I used Int64)

Will probably try and improve...

[JohnJPS]

Could we interpret this as more of a look-up?  To assess the sum for every possible combination will require some brute force (in either time or space)... but if we can stop when we find a combination that works, that makes the problem much friendlier.

I wrote a recursive R script that will return the first combination it finds that sums to the required target.  It checks to ensure that the target is not larger than the sum of the entire list prior to searching.

For a list of n integers (1 to 250), this was able to process every integer up to the sum of the entire list (31,375) in about 28 seconds.

Hopefully that might translate to something useful for @kpmg_lc_analyst.

EDIT: may have spoken too soon: bug fixed and the 28 seconds is pure hogwash, and then some; the stopping condition does help, but it's still slow going.

[jdunkerley79]

definitely can do some stopping conditions. How long did r take for 250?

Partitioning seems to be a good approach. Splitting the set into two equal size block and then combining looked like good for reasonable set size.

How to do a recursive call within alteryx without R is beyond me at the moment.

[JohnJPS]

With 250 in the list, it assessed all numbers from...

1 to 2,500 in 27 seconds

1 to 5,000 in 82 seconds

1 to 10,000 in 317 seconds

1 to 20,000... turned off after an hour!

PS... also unsure of how to do recursion in Alteryx.  There is the beginnings of a dynamic programming solution to this very problem, given here: http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/... it won't return the actual combination though, only a True or False.  I got it working in R, and used the set of number 2 to 500 by 2, which cannot generate an odd number.  I looked for 62748 and 62749 using the dynamic programming approach, which should be worst-case scenarios.  They took 100 and 110 seconds respectively.... which is frankly still pretty slow: processing a large data set of such numbers could take hours if not days.  There may be tricks to speed up the loops in R though, which are interpreted and a lot slower than C++ or even VB/C#.

[Jérémie]

Hello @jdunkerley79 !

I just read your answer 5 years later :) and I'm really interested in solving this subset sum problem using alteryx

-> I was wondering if you came up with an optimized solution ?

-> also, I looked into your first proposal and I have difficulties to figure out what the following filter purpose is:
    BinaryAnd(Pow(2,[RecordID]-1),ScenarioID) != 0

Hope this message finds you well :)

Best regards,

Jérémie

[Jérémie]

Hey @VojtechT !

Would there be a person at Alteryx's that could have an hint how to solve this famous problem using Alteryx ?

Have a great WE,

Jérémie