Show simple item record

Extended neighborhood: Definition and characterization

dc.contributor.authorOrlin, James B.en_US
dc.contributor.authorSharma, Dushyanten_US
dc.date.accessioned2006-09-11T19:32:01Z
dc.date.available2006-09-11T19:32:01Z
dc.date.issued2004-12en_US
dc.identifier.citationOrlin, James B.; Sharma, Dushyant; (2004). "Extended neighborhood: Definition and characterization." Mathematical Programming 101(3): 537-559. <http://hdl.handle.net/2027.42/47903>en_US
dc.identifier.issn1436-4646en_US
dc.identifier.issn0025-5610en_US
dc.identifier.urihttps://hdl.handle.net/2027.42/47903
dc.description.abstractWe 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.en_US
dc.format.extent227790 bytes
dc.format.extent3115 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypetext/plain
dc.language.isoen_US
dc.publisherSpringer-Verlag; Springer-Verlag Berlin Heidelbergen_US
dc.subject.otherOperation Research/Decision Theoryen_US
dc.subject.otherMathematicsen_US
dc.subject.otherNumerical and Computational Methodsen_US
dc.subject.otherMathematical Methods in Physicsen_US
dc.subject.otherMathematical and Computational Physicsen_US
dc.subject.otherOptimizationen_US
dc.subject.otherNumerical Analysisen_US
dc.subject.otherCombinatoricsen_US
dc.subject.otherCalculus of Variations and Optimal Controlen_US
dc.subject.otherMathematics of Computingen_US
dc.titleExtended neighborhood: Definition and characterizationen_US
dc.typeArticleen_US
dc.subject.hlbsecondlevelMathematicsen_US
dc.subject.hlbtoplevelScienceen_US
dc.description.peerreviewedPeer Revieweden_US
dc.contributor.affiliationumDepartment of Industrial and Operations Engineering, , University of Michigan, , Ann Arbor, MI, 48105, USAen_US
dc.contributor.affiliationotherMassachusetts Institute of Technology, , Sloan School of Management, , E40-147, Cambridge, MA, 02139, USAen_US
dc.contributor.affiliationumcampusAnn Arboren_US
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/47903/1/10107_2003_Article_497.pdfen_US
dc.identifier.doihttp://dx.doi.org/10.1007/s10107-003-0497-0en_US
dc.identifier.sourceMathematical Programmingen_US
dc.owningcollnameInterdisciplinary and Peer-Reviewed


Files in this item

Show simple item record