What are some concrete (near-)"worst-case" examples of subset-sum?

Question

I've written a subset-sum solver. It outputs all subsets that sum to a given value, iteratively.
I'm measuring its performance by the average amount of time taken per subset found.

However, I suspect it may be faster than existing solvers in "near-worst" cases, but I don't know how to check this.
What are some concrete examples of near-worst-case subset-sum problems I can try it on?

Note that I'm looking for reasonable examples here (< 64 bits -- i.e., numbers that actually pop up in the real world), not, for example, an instance with 500 digits. I'm looking for reasonable examples here. The idea is that I'm trying to solve real-world subset-sum problems well in "hard" cases.

Answer 1

The naive dynamic programming complexity is $O(sN)$ where $s$ is the integer bit precision, $N$ is the set cardinality. With some slight tricks in memoization cutting the precision constant in half, an instance with 64 bits precision should be solvable without much optimization in a linearly increasing fashion and as fast as memory access allows.

However, the naive method for small $s$ but large $N$ is dynamic programming which has subjectively large memory requirements. In practice this is the constraint that is prohibative for large instances skewed towards small precision, since many of the non-cryptographic applications I can think of deal with embedded systems having low memory and real-time constraints that limit non-uniform memory access.

At the other end of the spectrum if you have PiB subset-sum instances with small $s$ but very large $N$, the same issues arise as in sorting. These instances are incredibly 'easy' from a theory perspective but the micromanagement constant factor details dominate such as cache usage, memory walls, parallelization, bandwidth saturation, and code/data locality. Many of the techniques for fast solvers become invalidated at that size due to either reliance on a central memoization table or chaotic memory access.

The major applications for subset-sum that I know of are cryptographic in nature, which necessitates that the natural 'real-world' integer precision is far larger than 64 bits. In addition, most of the various manufacturing and finance applications do encounter the need for integer precision much larger than 64 bits as a way to actually encode the problem without blowing up $N$ in a very non-linear manner. This is required even though the original 'real-world' quantities are far less than 64 bits.

So hard subset-sum instances with 64 bit precision don't exist in the manner that I think you want to test. If an analogy helps, this is similar a complexity outcome to finding the prime factorization of a very large number but limited to prime factors with 64 bits of precision rather than the general case.

Answer 2

It's not clear how to formally define worst-case (or near-worst-case) instances, but here is something you could try.

The idea is to combine the following two tidbits:

1. We know some hard instances for 3SAT.
2. There is a reduction from 3SAT to SUBSET-SUM.

The hard instances for 3SAT are random instances at the correct clause density, which is just below the satisfiability threshold (4.2667). Applying the NP-hardness reduction that shows that SUBSET-SUM is NP-hard should result in hard instances for SUBSET-SUM.

Unfortunately, these instances are probably very large, so these instances might be too hard.

Answer 3

Not actually an answer to my own question, but if no one finds one, I think it would support what the author of this paper had to say, especially given that my own code was backtracking-based:

The empirical results in [Figure 4] do not necessarily reflect worst-case analytical results. Backtracking is better than DP for all problem instances, even as the density of the problem instance is increasing. The worst-case analyses lead to the expectation that DP will be better than BT for high-density problem instances. Apparently, the density never gets high enough to give DP the advantage. Of course, we need to keep in mind that the empirical data from randomly generated instances is an illustration of average-case complexity, not worst-case complexity. While it is not known that average time complexity differs from worst-case time complexity for either backtracking or dynamic programming, it is known that many algorithms perform far better than worst-case for instances outside the critical region.

In other words, it seems that it's hard to find hard instances of subset-sum!
And I have no idea whether it's been done at all.

Answer 4

I'll share what I learned after reading many papers about the subset sum problem, I too implemented a solver and was looking time ago to understand what a 'hard instance' really is (in regards to this problem), and what I'm going to describe worked very well as a test bench for my solver, I personally never tackled the backtracking algorithm so you might need to reconcile this information with BT dynamics, but on the other hand, this way to build up instances are effective for both DP and the 'meet-in-the-middle' approach.

In relationship to subset sum problem, the existing literature, defines usually a hard instance as a random set of equally distributed values across the problem space with $density \approx 1$ (I found a paper settling, after some analysis that in fact the hardest instances have a $density \approx 1.03$ but is not a big of a difference form the practical point of view, that is what it looks you are interested)

Assuming $N$ being the number of elements and $P$ the number of bits for encoding the maximum possible value in your set, to achieve a $density \approx 1$ you must set the same value for $N$ and $P$ as $density=N/P$

For example, as you are constraining the integers resolution to no more than 64 bits, then, $N=P=64$.

Now you need to pick 64 uniquely random values equally distributed between $1..2^{64}$, trying to really equally distribute them (not clustering near-values). This will be your input set.

Then, you need to pick the target value, for this, you must select, again, randomly, unique values from your set, and add them until the sum is around the 50% of the problem space (problem space=the sum of all your values).

Why around 50%? Because if you pick a target value over 50% of the problem space, let's say 80%, by using DP, you can just build up the sums for the subsets and check for the 'negative' subset, as probably you can do with BT, so any target value deviating from the middle location is not that harder (because is near the beginning or the end, in the middle is equidistant, thus is the hardest of the locations for the target value)

However, in my opinion, the concept of 'hard instance' for a subset sum solver depends a lot on the solver implementation details, each solver can face problems with different parameters, e.g: DP can't handle a big $P$ because it blows up the memory need to hold the dynamic table in memory, even with very smart optimizations, the DP 'cost' depends on the target value, and in its worst case the target value for DP is a value around $2^{P-1}*N$, so any change on $P$ or $N$ will impact the 'cost'.

If we look to the meet-in-the-middle, $P$ is not that important (if we don't consider memory), and $N$ is the real problem, when you get to larger sets, even with the smart split the 'cost' will increase exponentially.

So the bottom line is to know what variables impact your algorithm performance to be able to create proper hard instances for 'test benching'