Search Strategies in Large-Scale Discrete Optimization: A Joint AI/OR Approach

摘要

The aim of this award was to exploit and enhance the differing strengths ofArtificial 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.