It's important that you understand the definition of a neighborhood used in this book. This is definition 1.3 on page 7. $N$ is not a set but rather a function that maps a solution to the problem to a subset of the entire set of solutions. You can also speak of the neighborhood of a particular solution, s, with respect to $N$, which would be denoted $N(s)$. $N(s)$ is a subset of the set of all solutions.

Your question makes it clear that you don't understand this definition, since you imply that $N$ is a set of solutions.

An example might help. If you're familiar with the 2-opt heuristic for the traveling salesman problem, then "the 2-opt neighborhood" is an example of N, while "the set of tours that can be obtained from the tour T by two-opt moves" is N(T) with respect to the two-opt neighborhood.

This definition makes sense in the context of a local search algorithm. Given a neighborhood N, and an initial solution $s^{0}$, the local search algorithm constructs a sequence of solutions $s^{1}$, $s^{2}$, $\ldots$, by iterating

$s^{n+1}=\arg \min N(s^{n})$

If the neighborhood $N$ is exact, and if the iteration eventually converges to a solution where $s^{n+1}=s^{n}$, then that solution will be globally optimal.

exact. For example, if $N$ were the whole space, it would always beexact(because afaik, locally optimal wrt $N$ means, best over entire $N$) – Suvrit Jan 19 '11 at 20:06