Fall 2005 ISyE Colloquium Series

University of Wisconsin-Madison

Department of Industrial & Systems Engineering

Sheldon H. Jacobson

Professor and Director, Simulation and Optimization Laboratory

Department of Mechanical and Industrial Engineering

University of Illinois at Urbana-Champaign

Sheldon H. Jacobson is a Professor and Director of the Simulation and Optimization Laboratory in the Department of Mechanical and Industrial Engineering at the University of Illinois. He has a B.Sc. and M.Sc. (both in Mathematics) from McGill University, and a M.S. and Ph.D. (both in Operations Research and Industrial Engineering) from Cornell University. His theoretical research interests include the analysis and design of heuristics for intractable discrete optimization problems. His applied research interests address problems in the areas of aviation security and health-care delivery systems. In 1998, he received the Application Award from the IIE Operations Research Division. In 2002, he was awarded the Aviation Security Research Award by Aviation Security International, the International air Transport Association, and the Airports Council International. In 2003, he received the Best Paper Award in IIE Transactions Focused Issue on Operations Engineering and was named a Guggenheim Fellow by the John Simon Guggenheim Memorial Foundation. His research has been published in a wide spectrum of journals, including Operations Research, Mathematical Programming, and INFORMS Journal on Computing. He has received research funding from several government agencies and industrial partners, including NSF and AFOSR.

The Dark Side of Local Search Algorithms
(with Some Light at the End of the Tunnel)

Local search algorithms have proven to be effective in obtaining near-optimal solutions for hard discrete optimization problems. However, they have had limited success in actually finding globally optimal solutions. The key issue that drives the effectiveness of local search algorithms is the size and design of the neighborhood function. Desirable properties of neighborhood functions are identified and discussed. Results are obtained that show that implementations of such neighborhoods are unlikely to exist in practice. Therefore, to overcome the trappings of local optima, smart methods of escaping from local optima must be obtained. One possible approach is a cyclical simulated annealing algorithm that cycles through a set of temperature parameters, and hence, allows for an easier and more intelligent mechanism to escape local optima. To compare the effectiveness of such algorithms, upper and lower bound estimators are obtained for the first hitting time random variable of a solution within a prespecified percentage away from the globally optimal value. Computational results are reported.

2:30PM Friday, September 30, 2005

Room 1045 Engineering Centers Building