Technion, IEM faculty - Operations Research seminar
 
Speaker: Uri Yovel, Technion
 
Title: Worst case analysis of local search based heuristics
 
Date: 11/06/2012
 
Time: 12:30
 
Place: Bloomfield-527
 
Abstract:  <http://ie.technion.ac.il/seminar_files/1337072859_seminarOR_Uri.doc>
 
Or read it here, more or less:
 
The traveling salesman problem (TSP) and the vehicle routing problem
(VRP) are classical NP-hard problems in combinatorial optimization. The
k-opt heuristics are among the most common techniques for approaching
TSP. They are used either directly or as subroutines in more
sophisticated heuristics, such as the celebrated Lin-Kernighan
heuristic. The value of k is typically 2 or 3. In this paper, we modify
the 2-opt heuristic to be based on a  function  f  of the distances
rather than the distances solely. This may be viewed as modifying the
local search with the 2-change neighborhood to be non-oblivious. We
denote the corresponding heuristic by (2,f)-opt. We provide theoretical
performance guarantees for it: both lower and upper bounds based on the
ones given by Chandra, Karloff, and Tovey (1999), obtained originally
for the standard 2-opt heuristic; the upper bound is improved by a
factor of v2 with respect to the known upper bound of the standard
2-opt. We then provide experimental evidence based on TSPLIB benchmark
problems, showing that (2,f)-opt with  f(x) = x^r < 1 significantly
outperforms 2-opt.
 
We then briefly discuss a local search algorithm for the VRP; in
particular, we show that the k-opt heuristic is not strong enough to
guarantee a constant approximation ratio, and we present a different
(non-oblivious) local search whose approximation ratio is 2. To the best
of our knowledge, this is the first local search algorithm for this
problem with proved performance guarantee.
 
Uri Yovel  PhD candidate
 
Advisor: Asaf Levin
 
Faculty of Industrial Engineering and Management, Technion
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from:  <ehazan@ie.technion.ac.il>