Model expansion as a framework for representing and solving search and optimization problems

计算困难的搜索和优化问题在科学、工程和商业中无处不在。例如药物设计、蛋白质折叠、遗传学重建、硬件和软件设计、测试生成和验证、规划、制造、调度等。在极少数情况下，存在实际的应用特定软件，但大多数成功方法的开发需要雇用专家，并且通常需要大量的时间和费用，以应用一种或多种计算方法。该项目的目标是开发解决搜索和优化问题的各种方法的正式基础和统一原则。该研究将有助于开发一种方法，该方法对用户的专业知识要求相当低，从而使解决此类问题的技术可供更广泛的用户使用。在这种方法中，用户以声明性建模语言给出其搜索（或优化）问题的精确规范，例如经典一阶逻辑的扩展或类似于众所周知的数据库查询语言SQL的语言。然后，求解器将此规范与问题的实例（即，存储在数据库中的数据），并产生问题的解决方案（如果存在的话）。我们通过系统开发进行理论开发和实践可行性论证的研究计划。

Computationally hard search and optimization problems are ubiquitous in science, engineering and business. Examples include drug design, protein folding, phylogeny reconstruction, hardware and software design, test generation and verification, planning, timetabling, scheduling and so on. In rare cases, practical application-specific software exists, but most often development of successful methods requires hiring specialists, and often significant time and expense, to apply one or more computational approaches. The goal of this project is to develop formal foundations and unifying principles of various methods of solving search and optimization problems.The research will help developing an approach which would require considerably less specialized expertise on the part of the user, thus making technology for solving such problems accessible to a wider variety of users. In this approach, the user gives a precise specification of their search (or optimization) problem in a declarative modelling language, for example an extension of classical first-order logic or a language similar to the well-known database query language SQL. A solver then takes this specification, together with an instance of the problem (i.e., data stored in a database), and produces a solution to the problem (if there is one). We undertake a research program of both theoretical development and demonstrating practical feasibility through system development.