0
$\begingroup$

I find a definition of "exact neighborhood" (the book is online (*1) Definition 1.5 on p.10) confusing.

Do I understand it right that neighborhood that contains the global optimum and no other local optimums/ma is what they call "exact neighborhood" in this book ?

Is this terminology accepted anywhere, or just in this book ?

(*1) http://books.google.com/books?id=u1RmDoJqkF4C&pg=PA10&lr=&hl=iw&source=gbs_toc_r&cad=4#v=onepage&q&f=false Papadimitriou Steiglitz‏ Combinatorial optimization

search in the book: definition 1.5 exact

$\endgroup$
2
  • $\begingroup$ I'm not familiar with the terminology but it's not really my area of expertise. It certainly seems like a strange choice of words, given how analogous it is to convexity. $\endgroup$ Jan 19, 2011 at 19:45
  • 1
    $\begingroup$ All that definition is saying is: Say you have some neighborhood $N$. If every point that is locally optimal for $N$ (i.e., the objective function value at this point is the lowest in the entire neighborhood $N$), is also globally optimal, then the neighborhood $N$ is called exact. For example, if $N$ were the whole space, it would always be exact (because afaik, locally optimal wrt $N$ means, best over entire $N$) $\endgroup$
    – Suvrit
    Jan 19, 2011 at 20:06

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Let me just add that I have seen this term used elsewhere within the literature on local search algorithms, although I don't have any references handy. $\endgroup$ Jan 20, 2011 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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