Very Large-Scale Neighborhood Search

SA06.1 Very Large-Scale Neighborhood Search

• James B. Orlin; MIT, Sloan Sch. of Mgmt., E40-147, Cambridge, MA 02139; jorlin@mit.edu
• Ravindra K. Ahuja; University of Florida, 303 Well Hall, Dept. of ISE, Gainesville, FL 32611; ahuja@ise.ufl.edu
• Ozlem Ergun; MIT, OR Ctr., 77 Mass Ave., Bldg. E40-130, Cambridge, MA 02139; ozie@mit.edu
• Abraham P. Punnen; University of New Brunswick, Dept. of Math. Stats. & CS, PO Box 5050, Saint John, NB, E2L 4L5 , Canada; punnen@unbsj.ca

In neighborhood search techniques, one searches the 'neighborhood' of a given solution x' and replaces x' by a neighbor that has improved cost. VLSN search refers to neighborhood search techniques in which the number of neighbors of x' may be exponentially large. We briefly survey VLSN search.

SA06.2 Searching Very Large-Scale Neighborhoods using Improvement Graphs

• Ravindra K. Ahuja; University of Florida, 303 Well Hall, Dept. of ISE, Gainesville, FL 32611; ahuja@ise.ufl.edu
• James B. Orlin; MIT, Sloan Sch. of Mgmt., E40-147, Cambridge, MA 02139; jorlin@mit.edu

We review 2 applications of very large-scale neighborhood search in which the key idea is to search neighborhoods using improvement graphs. We illustrate the ideas on partitioning problems, especially to the capacitated minimum spanning tree problem, and on airline fleet assignment.

SA06.3 Large-Scale Neighborhood Search Applied to a Nonbifurcated Network Loading Problem with Multiple Facilities

• Bernard Gendron; Universite de Montreal, DIRO & CRT, CP 7128, succ. Centre-ville, Montreal, Quebec, H3C 3J7 , Canada; bernard@crt.umontreal.ca
• Jean-Yves Potvin; Universite de Montreal, DIRO/CRT, CP 6128, Succ, Centre-Ville, Montreal, Quebec, H3C 3J7 , Canada; potvin@diro.umontreal.ca
• Patrick Soriano; University of Montreal, HEC, CP 6128, succ. Centre-ville, Montreal, Quebec, H3C 3J7 , Canada; partick@crt.umontreal.ca

We study a network design problem that arises in the telecommunications industry. We describe large-scale neighborhood search heuristics, which perform k-opt type exchanges in the space of paths. Numerical results are presented on different types of networks with up to 200 vertices.

SA06.4 Domination Analysis of Some Well-Known Construction Heuristics for the Traveling Salesman Problem

• Abraham P. Punnen; University of New Brunswick, Dept. of Math. Stats. & CS, PO Box 5050, Saint John, NB, E2L 4L5 , Canada; punnen@unbsj.ca

We review domination results on several well known construction heuristics for the TSP including the Christofides heuristic, patching algorithms, nearest neighbor and other greedy type algorithms, node insertion algorithms, etc. Some new results in this area will also be presented.