definition of "exact neighborhood" [optimization] - MathOverflow most recent 30 from http://mathoverflow.net2013-05-21T09:05:18Zhttp://mathoverflow.net/feeds/question/52544http://www.creativecommons.org/licenses/by-nc/2.5/rdfhttp://mathoverflow.net/questions/52544/definition-of-exact-neighborhood-optimizationdefinition of "exact neighborhood" [optimization]Andrei2011-01-19T19:06:00Z2011-01-20T00:27:22Z
<p>I find a definition of "exact neighborhood" (the book is online (*1) Definition 1.5 on p.10) confusing.</p>
<p>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 ?</p>
<p>Is this terminology accepted anywhere, or just in this book ?</p>
<p>(*1)
<a href="http://books.google.com/books?id=u1RmDoJqkF4C&pg=PA10&lr=&hl=iw&source=gbs_toc_r&cad=4#v=onepage&q&f=false" rel="nofollow">http://books.google.com/books?id=u1RmDoJqkF4C&pg=PA10&lr=&hl=iw&source=gbs_toc_r&cad=4#v=onepage&q&f=false</a>
Papadimitriou Steiglitz‏ Combinatorial optimization </p>
<p>search in the book: definition 1.5 exact</p>
http://mathoverflow.net/questions/52544/definition-of-exact-neighborhood-optimization/52566#52566Answer by Brian Borchers for definition of "exact neighborhood" [optimization]Brian Borchers2011-01-20T00:27:22Z2011-01-20T00:27:22Z<p>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. </p>
<p>Your question makes it clear that you don't understand this definition, since you imply that $N$ is a set of solutions. </p>
<p>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. </p>
<p>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</p>
<p>$s^{n+1}=\arg \min N(s^{n})$</p>
<p>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. </p>