# Ant Colony optimisation for finding subsets with ~0 sum

I have a set A = [x1, x2...xn] where xi in R (real). I need to find all non intersecting subsets with subset sum ~0 (approximately equal to zero).

Since the set can have non zero real numbers, I have opted to use Ant Colony Optimisation for this problem. I have implemented this in python and the program tends to be a bit slow (python dictionaries for the graph). It takes around 60 seconds for 100 ants for single iteration. The algorithm goes like this:

• Create a graph with the whole list of real numbers (fully connected)
• Initialise the graph edges with w0
• Each vertex has an associated value
• Initialise the position of ants at random nodes
• Ants select next nodes based on edge weights
• Once an ant completes tour - the sum of all vertex values > threshold 1 (1000000) or < threshold 2 (~0.1), the path weights are updated based on path sum and global path updates (pheromone evaporation) after this

The questions I have:

1. Is the usage of ACO relevant here?
2. How can I improve the speed of the implementation?
• I don't understand what you want the output to be. If the input is the set $\{-3,-2,-1,1,2,3\}$, what should the output be? Is $\{-3,3\},\{-2,2\},\{-1,1\}$ a valid output? Is $\{-3,-2,-1,1,2,3\}$ a valid output? Is $\{-3,1,2\},\{-2,-1,3\}$ a valid output? – D.W. Mar 2 '19 at 4:33
• @D.W. Valid outputs would be : {-3,3}, {-2,2},{-1,1} or {−3,−2,−1,1,2,3} or {−3,1,2},{−2,−1,3} – Jijo Mar 2 '19 at 9:18
• In short: (1) yes, ACO is potentially relevant for any hard problem and (2) implementation details in concrete languages (like Python) are off-topic for the site, unfortunately. If you have a working program, you could try your luck on Code Review SE. – Juho Mar 2 '19 at 11:17
• I don't think this is a good fit for this site. "Is ACO appropriate?" is basically a matter of personal opinion, which is off-topic everywhere on Stack Exchange. How you can improve the speed of your implementation is a programming question, which is off-topic here. Or are you actually looking for algorithmic improvements? – David Richerby Mar 3 '19 at 13:51

Your problem is no harder and no easier than the approximate subset-sum problem. There is a natural approach for your problem:

1. Find any subset that sums to something close to zero, and output it. Remove those numbers from the set $$A$$.

2. Go back to step 1 and repeat, until the set $$A$$ is empty.

This requires a way to find a subset that sums to approximately zero, i.e., an approximation algorithm for the subset-sum problem. That problem is well-studied and can be solved in polynomial time using an approach based on rounding and dynamic programming.

I don't see any reason to expect ant colony programming to be better than the standard approaches; and I wouldn't be surprised if it is worse.

• the subset that needs to be found should be approximately equal to 0 (~0), apologies if the example confused you. – Jijo Mar 3 '19 at 4:05
• @JijoJose, ahh, I did indeed miss that. If you mean "approximately equal to 0" as opposed to "exactly equal to 0", could you edit the question to state that a bit more explicitly? Also, there are standard algorithms for finding approximate solutions to the subset sum problem, so you can use them (see the Wikipedia article I linked to for one such algorithm). – D.W. Mar 3 '19 at 4:57
• I believed the subset sum problem required the sum to be know in advance but in this case, the sum cannot be defined in advance. I think its more like a problem to find subsets which has minimum sum. – Jijo Mar 3 '19 at 13:04
• @JijoJose, I think you probably have a misunderstanding somewhere. The algorithms require the target to be known, not the exact sum. In your case the target is 0, so it is known. See, e.g., en.wikipedia.org/wiki/…. – D.W. Mar 3 '19 at 18:51
• @JijoJose, see updated answer; it is corrected to deal with the fact that you want the sum to be approximately 0, and I've updated the link to the algorithm. – D.W. Mar 3 '19 at 18:54