Combinatorial problem solving over relational databases: View synthesis through constraint-based local search

Solving combinatorial problems is increasingly crucial in business applications, in order to cope with hard problems of practical relevance. In these settings, data typically reside on centralised information systems, in form of possibly large relational databases, serving multiple concurrent transactions run by different applications. We argue that the use of current solvers in these scenarios may not be a viable option, and study the applicability of extending information systems (in particular database management systems) to offer combinatorial problem solving facilities. In particular we present a declarative language based on sql for modelling combinatorial problems as second-order views of the data and study the applicability of constraint-based local search for computing such views, presenting novel techniques for local search algorithms explicitly designed to work directly on relational databases, also addressing the different cost model of querying data in the new framework. We also describe and experiment with a proof-of-concept implementation. © 2012 ACM.