THE EXTENDED NEIGHBORHOOD: DEFINITION AND CHARACTERIZATION

James Orlin and Dushyant Sharma

No 4392-02, Working papers from Massachusetts Institute of Technology (MIT), Sloan School of Management

Abstract: We consider neighborhood search defined on combinatorial optimization problems. Suppose that N is a neighborhood for combinatorial optimization problem X. We say that N?Â€Ò is LO-equivalent (locally optimal) to N if for any instance of X, the set of locally optimal solutions with respect to N and N?Â€Ò are the same. The union of two LO-equivalent neighborhoods is itself LO-equivalent to the neighborhoods. The largest neighborhood that is LO-equivalent to N is called the extended neighborhood of N, and denoted as N*. We analyze some basic properties of the extended neighborhood. We provide a geometric characterization of the extended neighborhood N* when the instances have linear costs defined over a cone. For the TSP, we consider 2-opt*, the extended neighborhood for the 2-opt (i.e., 2-exchange) neighborhood structure. We show that number of neighbors of each tour T in 2-opt* is at least (n/2 -2)!. We show that finding the best tour in the 2-opt* neighborhood is NP-hard. We also show that the extended neighborhood for the graph partition problem is the same as the original neighborhood, regardless of the neighborhood defined. This result extends to the quadratic assignment problem as well. This result on extended neighborhoods relies on a proof that the convex hull of solutions for the graph partition problem has a diameter of 1, that is, every two corner points of this polytope are adjacent. dushyant@umich.edu

Keywords: extended neighborhood; Lo-equivalent (search for similar items in EconPapers)
Date: 2003-01-27
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/1721.1/1800 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:mit:sloanp:1800

Ordering information: This working paper can be ordered from
MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA

Access Statistics for this paper

More papers in Working papers from Massachusetts Institute of Technology (MIT), Sloan School of Management MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA. Contact information at EDIRC.
Bibliographic data for series maintained by None ( this e-mail address is bad, please contact ).