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

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?

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$$.

1. 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.