definition of "exact neighborhood" [optimization] - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T09:05:18Z http://mathoverflow.net/feeds/question/52544 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52544/definition-of-exact-neighborhood-optimization definition of "exact neighborhood" [optimization] Andrei 2011-01-19T19:06:00Z 2011-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&amp;pg=PA10&amp;lr=&amp;hl=iw&amp;source=gbs_toc_r&amp;cad=4#v=onepage&amp;q&amp;f=false" rel="nofollow">http://books.google.com/books?id=u1RmDoJqkF4C&amp;pg=PA10&amp;lr=&amp;hl=iw&amp;source=gbs_toc_r&amp;cad=4#v=onepage&amp;q&amp;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#52566 Answer by Brian Borchers for definition of "exact neighborhood" [optimization] Brian Borchers 2011-01-20T00:27:22Z 2011-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>