Accession Number:

ADA467897

Title:

A Heuristic Design Information Sharing Framework for Hard Discrete Optimization Problems

Descriptive Note:

Final rept. Mar 2004-Feb 2007

Corporate Author:

ILLINOIS UNIV AT URBANA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2007-03-01

Pagination or Media Count:

48.0

Abstract:

This project studied and developed simultaneous generalized hill climbing SGHC algorithms as an algorithmic framework for information sharing in discrete optimization problems. This framework has been used to gain new insights into neighborhood structure designs that allow different neighborhood functions to share information when using the same heuristic applied to the same problem. The results reported from this project introduce the SGHC algorithm framework for information sharing across sets of related discrete optimization problems, provide guidelines on how to use and to design neighborhood functions that results in effective performance of local search algorithms, and describe how tabu search can be effectively used to improve the performance of generalized hill climbing algorithms. Extensive computationally results are reported on a large variety of test bed, large-scale, real-world discrete optimization problems. The primary application for this research were a military combat search and rescue problems, where several possible search and rescue strategies must be considered to determine the optimal strategy, and a homeland security aviation security baggage screening problems, where several different baggage screening strategies at a set of airports must be considered to determine the optimal strategy for the entire system. Both these problems are intractable due, in part, to the exponentially large number of possible solutions that exist and must be evaluated to identify those that are optimal.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE