Very Large Scale Neighborhood Search
James Orlin
Operations Research Center
Massachusetts Institute of Technology
Monday, October 25, 2004
3:00 - 4:00 PM
Terman Engineering Center, Room 453
Abstract:
Many optimization problems of practical interest are computationally
intractable. Therefore, a practical approach for solving such problems
is to employ heuristic (approximation) algorithms that can find nearly
optimal solutions within a reasonable amount of computation time.
An improvement algorithm is a heuristic algorithm that generally starts
with a feasible solution and iteratively tries to obtain a better
solution. Neighborhood search algorithms (alternatively called local
search algorithms) are a wide class of improvement algorithms where at
each iteration an improving solution is found by searching the
"neighborhood" of the current solution.
This talk focuses on neighborhood search algorithms where the size of
the neighborhood is "very large" with respect to the size of the input
data and in which the neighborhood is searched in an efficient manner.
We survey several broad classes of very large-scale neighborhood search
(VLSN) algorithms and give applications to partitioning and to fleet
assignment problems in airline scheduling.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html