Integrating constraint programming into answer set programming

Abstract

Many declarative problems exploit hard computational nature that need to be evaluated effectively. Examples of such problems are task scheduling, optimization problems, database transaction management. Successful approaches appear when several programming paradigms are combined and state-of-the-art techniques are reused in different combinations. This thesis presents a hybrid constraint answer-set programming solver that provides a modeling language and solving capabilities of Answer-Set Programming (ASP) and special relations over variables called constraints from area of Constraint Programming (CP). This combination can be defined as Constraint Answer-Set Programming (CASP). The proposed framework provides a custom syntax for supporting constraint and answer-set constructions and in addition it provides a support for a special type of global constraints. We then show how such programs can be transformed to HEX programs with external atoms and evaluated. Several formal properties of such transformation are provided. The thesis provides several optimizations for the original approach. The first improvement relies on reducing the size of the transformed program. This is based on the observation of the redundancy in some of the translated rules. This translation reduction does not affect answer sets of the programs. Another optimization is related to the program evaluation. The key idea is to find the small irreducible inconsistent set of constraints and add it as a nogood to the program. This way we will introduce user defined learning for the program. We also show that the learning functions for HEX programs based on these algorithms are correct. This thesis additionally provides the implementation of such approach as a plugin for DLVHEX system. We show the plugin architecture, ideas of the implementation and describe required algorithms. We describe how main components, namely CASP converter, rewriter, external atom evaluation and learning can be implemented. Finally, we provide examples of how the CASP plugin can be used. We study particular instance of scheduling optimization and geometry problem. Additionally we provide comprehensive benchmarking for such problems using different configurations and improvements from the thesis. We also show an example of how the plugin can be used in combination with other source of knowledge in the DLVHEX system.