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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.