Automatic Specialization of Generic Constraint Satisfaction Algorithms

点击翻译按钮获取中文摘要

Multi-TAC is a learning system that automatically synthesizes heuristic programs for combinatorial problems, including resource allocation and scheduling problems. This project investigates fundamental research areas that will enable Multi-TAC to be used for computationally challenging problems. The first goal is to develop fast methods for searching the space of algorithms evaluated by Multi-TAC during the synthesis process. In particular, the research focuses on methods for predicting how well an algorithm will perform based on a quick test on an example problem instance. The second goal is to enable Multi-TAC to automatically synthesize very efficient iterative repair algorithms. This involves the development of generic schemas that capture the structure of wide variety of such algorithms. The last goal is to enable users to easily specify new problem domains for Multi-TAC, without needing to worry about how the details of their specification impacts the synthesis process. In particular, the work focuses on techniques for rewriting constraints so that they can be efficiently evaluated. This research project provides an important step towards problem- solving systems that can automatically configure themselves for a particular application.