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

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

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.