How can I solve the zero subset sum problem with hill climbing?

Question

I want to solve the zero subset sum problem with the hill-climbing algorithm, but I am not sure I found a good state space for this.

Here is the problem: consider we have a set of numbers and we want to find a subset of this set such that the sum of the elements in this subset is zero.

My own idea to solve this by hill-climbing is that in the first step, we can choose a random subset of the set (for example, the main set is $X= \{X_1,\dots,X_n\}$ and we chose $X'=\{X_{i_1},\dots,X_{i_k}\}$ randomly), then the children of this state can be built by adding an element from $X-X'$ to $X'$ or deleting an element from $X'$ itself. This means that each state has $n$ children. and the objective function could be the sum of the elements in $X'$ that we want to minimize.

Is this a good modeling? Are there better modelings or objective functions that can work more intelligently?

Answer 1

The hill-climbing algorithm to implement is as follows:

1. The algorithm should take four inputs: as always, there will be a multiset S and integer k, which are the Subset and Sum for the Subset Sum problem; in addition, there will be two integers q and r, with roles defined below.
2. Do the following q times:

(a) Choose a random subset (multiset) $S_0$ of S as the current subset.

(b) Do the following (hill climbing) r times:

i. Find a random neighbor T (see definition of neighbor below) of the current subset.

ii. If neighbor T has smaller residue, then make T the current subset.

(c) Keep track of the residue of the final current subset when starting with subset $S_0$.

3. Return the smallest residue of the q subsets tested by the algorithm.

Definition: Subset (multiset) B ⊆ S is a neighbor of a subset A of S if you can transform A into B by moving one or two integers from A to B, or by moving one or two integers from B to A, or by swapping one integer in A with one integer in B. An easy way to generate a random neighbor B of a subset A of S is as follows:

1. Order the elements of S as $x_1, x_2, ..., x_n$.
2. Initialize B to be a clone of A.
3. Choose two distinct random indices i and j, where $1 ≤ i; j ≤ n$.
4. if $x_i$ is in A, remove it from B. Otherwise, add xi to B.
5. if $x_j$ is in A, then with probability 0.5, remove it from B. If $x_j$ is not in A, then with probability 0.5, add $x_j$ to B.

Answer 2

The state space itself seems OK but your approach has some disadvantages. First, you need to pick an initial state of size $n$. What if the optimal solution is of size $\frac{n}{4}$ or $10n$? Then the search could take a long time using this approach because you are starting far away. If there are multiple solutions, do you care which one you find or is the smallest zero subset preferred? I'm going to assume that the empty set $X'=\{\}$ is not a solution and that solutions with smaller cardinality are preferred.

I would suggest using a generative heuristic to construct the initial state and then running your hill climbing procedure from that state. For example, a generative heuristic could be something like: "pick the pair of elements ($x_1$,$x_2$) from $X$ such that $x_1 + x_2$ is as close to zero as possible, and set $X' =\{x_1, x_2\}$ as the initial state". To apply this heuristic you will need to initially check $n(n-1)$ subsets of pairs. If this is not a solution, it will hopefully be very close to the solution in the state space and therefore a good place to start.

Another problem is the hill climbing does not remember previously visited states, and you could end up infinitely looping when you allow moves to both add and delete elements from $X'$. For example, suppose $X'=\{1\},X=\{-3,-50,-50,100\}$. Clearly the optimal solution is $X''=\{-50,-50,100\}$ but your method will add element $-3$ to $X'$ first, then remove $-3$, then pick $-3$ again etc, because these states have a lower objective value than any state with one of $-50$ or $100$ in it. So I think you need to use a more sophisticated approach that prevents visiting the same state twice.