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).