I need help using the following neighborhood search heuristic on the set S that is partitioned into A and B where A = {1, 2} and B = {3, 4}. This set partition is our initial solution x_0, and the neighborhood of the partition is defined as all partitions that can be obtained by switching an element of A with an element of B.
The Neighborhood Search Heuristic is given as
1: Start with some initial solution x_0
2: Set k=0
3: While There exists x in N(x_k) such that f(x)<= f(x_k) do
4: Set x_(k+1) = argmin {f(x)|x is in N(x_k)
5: Set k=k+1
6: end while
For each iteration, I'd like to show the current solution, the current neighborhood, and the value of each element in the neighborhood. I'd also like to give the value of the result when the heuristic terminates.
However, I have a lot of questions. There is a function f(x) mentioned in the heuristic, but I do not have an f(x) defined. I'm not sure how to proceed in the heuristic with this. Also, if I were to list the neighborhood after each iteration with its value, how would the value change if A and B and those in its neighborhood are still partitions of the set S? I also need to know this before I run the algorithm properly, since I have to choose a minimum.
If I could be walked through one or two iterations of this heuristic, this would be enough for me to understand. Thanks in advance.
Note that in each step of the algorithm, the value of $f(x_k)$ decreases (or in the worst case, stays the same) at each step. This algorithm tries to minimize the value of $f(x)$. So the choice of $f$ depends on what you are searching for.
Example
Let's say you're searching for a partition $x$ of $S=\{1,2,3,4\}$ into two subsets $A$ and $B$ such that the difference between the sums of $A$ and $B$ is minimized. In this case $f$ is simply the absolute value of the difference of the sums.
Initial condition
$$x_0=(\{1,2\},\{3,4\})$$ $$f(x_0)=|(1+2)-(3+4)|=4$$
First step
The neighborhood of $x_0$ consists of four elements, $$(\{3,2\},\{1,4\}), (\{4,2\},\{3,1\}), (\{1,3\},\{2,4\}), (\{1,4\},\{3,2\})$$ with respective scores of 0, 2, 2, and 0. We could select either the first or last element, here I'll take the first: $$x_1=(\{3,2\},\{1,4\})$$
Second step
The neighborhood of $x_1$ consists of four elements, $$(\{1,2\},\{3,4\}), (\{4,2\},\{1,3\}), (\{3,1\},\{2,4\}), (\{3,4\},\{1,2\})$$ with respective scores of 4, 2, 2, and 4. Since none have a score less than or equal to 0, the algorithm terminates.
Note that if you have two neighbors with equal scores, the algorithm above will flip between them endlessly; this can be fixed by changing the $\le$ to a $<$, or by keeping track of $x_{k-1}$ and excluding it from the search.