CDS Lecture Series


Sheldon H. Jacobson
Simulation and Optimization Laboratory
Department of Mechanical and Industrial Engineering
University of Illinois at Urbana-Champaign

An Analysis of Finding Near-Optimal Solutions for Hard Discrete Optimization Problems Using Local Search Algorithms

The beta-acceptable (near-optimal) solution probability captures how effectively a local search algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. Estimators for the expected number of iterations for a GHC algorithm to visit a beta-acceptable (near-optimal) solution are obtained. Computational experiments with cyclical simulated annealing applied to a set of traveling salesman problem instances with known optimal solutions are reported to evaluate these estimators.

This research has been support by the Air Force Office of Scientific Research (FA9550-04-1-0110).

Back to CDS Lecture Series
Back to Intelligent Servosystems Laboratory