Search Strategies in Large-Scale Discrete Optimization: A Joint AI/OR Approach
Final rept. 1 Jul 96-31 Dec 97
GEORGIA INST OF TECH ATLANTA SCHOOL OFINDUSTRIAL AND SYSTEMS ENGINEERING
Pagination or Media Count:
The aim of this award was to exploit and enhance the differing strengths of Artificial Intelligence AI and Operations Research OR in solving hard combinatorial optimization problems, discover synergies, and so develop better solution techniques. By studying the strengths and weaknesses of the various approaches in the context of a large scale manufacturing problem, a new AI solution approach capable of producing better solutions than traditional heuristic methods and handling larger problems than exact techniques was developed. This new approach generalizes a number of seemingly divergent existing techniques and seems to be widely applicable. In addition, it was discovered that OR techniques can be used to augment the new AI solver, resulting in significant improvements in both solution time and quality. This hybridized approach has also led to a new understanding of the OR technique known as column generation, and these insights promise improvements in solution quality and time for a variety of OR problems.
- Operations Research