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