Optimization Tool Help - Subset Sum Problem

[DanMorton]

Hi all,

I'm hoping someone here might be able to help with a problem we are currently facing with the Optimization tool in Alteryx Designer. We are trying to use the tool to find and flag which subset of transactions make up a specified target (which could be made up from an unknown number of transactions).

However, we are finding that the tool will often specify solutions which are incorrect. In the attached workflow, we are trying to find a specific total, and the tool has claimed to have found a solution which has a different value than the target.

I can see in the D output node that it is in fact trying to find our correct value, and put in a 'Slack' value of 0.13, which we cannot have. In my constraints I have specified using '==' which I would assume would have a slack of 0.

We are okay if the workflow cannot find a solution, but we cannot have these false positives where the target value is 'close enough' as we need exact matches.

Is it possible to manually adjust this Slack value (despite my constraint using ==)? Any ideas as to why this is happening?

Appreciate any insight on this as we are quite confused!

Thanks

[BS_THE_ANALYST]

Hi @DanMorton. I'll have a look into this now. 

You've stated the following:

. We are trying to use the tool to find and flag which subset of 
transactions make up a specified target (which could be made up from an 
unknown number of transactions).

Are you trying to maximise or minimise the number of transactions to hit the target?

I'll see what I can do & feedback the findings

[BS_THE_ANALYST]

It might be worth having a look at some of the example workflows available in Alteryx for the optimisation tool:

In the fantasy sports lineup example, they use lb and ub in the O anchor. This may be messing with something (yours doesn't have it). I guess you've told the model you want to hit some target value but you haven't set constraint on how many of the variables to use? I appreciate this kinda is implicit from supplying the type of binary "b". Wouldn't hurt to look at some examples and copy over their config settings.

I tried changing the solver to "symphony" and it certainly does a lot more processing as it takes longer. I'm also thinking of the computations under the hood and how many different combos you'd have to do with 61 values present. 

I changed the target value to 7 and ran another test. I still recieve the slack output like you recieved (obviously slightly different delta though)

Not ideal but it's done a fantastic job of getting as close as possible. It does seem strange to not just error and say "no solution". For example, if we just reduce the amount of variables coming in:

 These were just some of the observations I noted. With that being said, there's a solution here https://community.alteryx.com/t5/Alteryx-Designer-Desktop-Discussions/Need-help-with-Optimization-To... which seems to have lots more going on and constraints are  still satisfied..

I checked out your optimisation tolls setup and it seems pretty much there: https://community.alteryx.com/t5/Tool-Mastery/Tool-Mastery-Optimization/ta-p/306117 

Not too sure at the moment. Check the usual suspects like variable names and datatypes. Also, try bringing on a new optimisation tool.

Let me know if any of that helps you further along or you spot something.

[BS_THE_ANALYST]

@DanMorton I know it's not as satisfying but you could just include a check to see that the Slack value is in fact 0 by parsing it out with something like text to columns etc. If it's not 0, use a message tool to trigger an error. Effectively, it's providing the same result as the tool erroring itself. 

[DanMorton]

Thanks for taking a look at this one - we have included some checks to verify whether we can get exact matches or not, however that doesnt help us too much unfortunately, particularly if the tool flags a false positive before it finds a genuine solution to the problem.

Also we are typically trying to minimise the number of transactions to match the target.

We have also tried on multiple machines and recreated the same problem, so the issue is not fixed by just replacing the tool and setting up from scratch again.

Thanks,
Dan

[OllieClarke]

Hi @DanMorton I couldn't find the cause of the issue, but these links might be useful: https://github.com/alteryx/AlteryxPrescriptive/tree/master is the source code for the optimisation R tools. /R/solveModel.R seems to be the code used by the optimisation tool. https://rdrr.io/github/alteryx/AlteryxPrescriptive/man/AlteryxSolve.html This is a more interactive (maybe) documentation of the packages. Hope that helps, Ollie