Title: A Hybrid Multistart Heuristic for the Uncapacitated Facility Location Problem


		Mauricio G. C. Resende
	    Algorithms & Optimization Research Department
		       AT&T Labs Research
	       180 Park Avenue, Florham Park, NJ 07932
		      mgcr@research.att.com
	        http://www.research.att.com/~mgcr

	          COAUTHOR: Renato F. Werneck
                 Department of Computer Science
	             Princeton University
	       35 Olden Street, Princeton, NJ 08544.
                   rwerneck@cs.princeton.edu


ABSTRACT:   
We present a multistart heuristic for the uncapacitated facility location 
problem, based on a very successful method we originally developed for the 
P-median problem. We show extensive empirical evidence to the effectiveness 
of our algorithm in practice. For most benchmarks instances in the literature,
we obtain solutions that are either optimal or a fraction of a percentage 
point away from it. Even for pathological instances (created with the sole 
purpose of being hard to tackle), our algorithm can get very close to 
optimality if given enough time. It consistently outperforms other heuristics 
in the literature.