Extending the Answer-Set Programming Paradigm to Decomposed Problem Solving

Formalizing and implementing complex reasoning problems not only requires powerful declarative languages but also calls for tailored algorithms that are able to handle instances of large size as they appear in typical emerging real-world settings. Such instances often show structural features, which when handled appropriately, allow for efficient solutions even if the problem at hand is intractable in general. A prominent approach to exploit structure is to employ the concept of tree decompositions, since many problems can be efficiently solved with dynamic programming algorithms on tree decompositions if the structural parameter treewidth is bounded. Roughly speaking, this means that a graph representation of the problem instance resembles a tree to a certain extent. Empirical studies indicate that in many practical applications like bio-informatics or social networks the treewidth is usually indeed small. However, the implementation of suitable efficient algorithms is often done from scratch, since declarative languages so far do not offer features which make them amenable to decomposed instances. All this calls for a suitable combination of declarative approaches and structural methods. In this project, we propose such a combination using the paradigm of Answer-Set Programming (ASP) for problem solving on tree decompositions. ASP is a well established formalism in the AI community and sophisticated systems are available. The rich language of ASP particularly features the so-called Guess & Check methodology, mirroring the inherent nature of NP-hard problems. Thus ASP provides succinct means to specify such problems. The ultimate goal of the project is to establish a new solving paradigm, which we call Decompose, Guess & Check, where ASP is envisaged as a vehicle to declaratively describe and efficiently execute dynamic programming algorithms on tree decompositions. To this end, we will in course of the project (i) show that each problem for which the seminal theorem by Courcelle yields tractability on structures of bounded treewidth can also be solved efficiently in our new approach; (ii) provide an implementation delegating the burden of computation and optimization to existing tools for finding tree decompositions and to ASP solvers; (iii) demonstrate the usability of the method by means of case studies, where we provide realizations along the proposed methodology for a wide range of problems from diverse application areas.

Formalizing and implementing complex reasoning problems not only requires powerful declarative languages but also calls for tailored algorithms that are able to handle instances of large size as they appear in typical emerging real-world settings. Such instances often show structural features, which when handled appropriately, allow for efficient solutions even if the problem at hand is intractable in general. A prominent approach to exploit structure is to employ the concept of tree decompositions since many problems can be efficiently solved with dynamic programming algorithms on tree decompositions if the structural parameter treewidth is bounded. Roughly speaking, this means that a graph representation of the problem instance resembles a tree to a certain extent. Empirical studies indicate that in many practical applications like bio-informatics or social networks the treewidth is usually indeed small. However, the implementation of suitable efficient algorithms is often done from scratch since declarative languages so far do not offer features which make them amenable to decomposed instances.All this calls for a suitable combination of declarative approaches and structural methods. In this project, we proposed such a combination using the paradigm of Answer-Set Programming (ASP) for problem solving on tree decompositions. ASP is a well established formalism in the AI community and sophisticated systems are available. The rich language of ASP particularly features the so-called Guess & Check methodology, mirroring the inherent nature of NP-hard problems. Thus, ASP provides succinct means to specify such problems.The ultimate goal of the project was to establish a new solving paradigm, which we call Decompose, Guess & Check, where ASP is used as a vehicle to declaratively describe and efficiently execute dynamic programming algorithms on tree decompositions. To this end, we developed D-FLAT, a tool for rapid prototyping of such algorithms, where users merely need to specify the computation at each node of the tree decomposition in a declarative way, and the system takes care of problem-independent parts like computing a decomposition and combining partial solutions. We have investigated theoretical properties of our method and demonstrated its efficiency in several problem domains. The insights we have gained in course of the project lead to new successful specialized systems which implement dynamic programming approaches in order to solve hard problems, like quantified Boolean logic. Project webpage: http://dbai.tuwien.ac.at/research/project/dflat/