Aspartame: Solving Constraint Satisfaction Problems with Answer Set Programming
Authors:
Preprint
Abstract
Encoding finite linear CSPs as Boolean formulas and solving them by using modern SAT solvers has proven to be highly effective, as exemplified by the award-winning sugar system. We here develop an alternative approach based on ASP. This allows us to use first-order encodings providing us with a high degree of flexibility for easy experimentation with different implementations. The resulting system aspartame re-uses parts of sugar for parsing and normalizing CSPs. The obtained set of facts is then combined with an ASP encoding that can be grounded and solved by off-the-shelf ASP systems. We establish the competitiveness of our approach by empirically contrasting aspartame and sugar.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Promoting robust black-box solvers through competitionsConstraints, 2010
- Propagation via lazy clause generationConstraints, 2009
- On the Implementation of Weight Constraint Rules in Conflict-Driven ASP SolversLecture Notes in Computer Science, 2009
- Constraint Answer Set SolvingLecture Notes in Computer Science, 2009
- Compiling finite linear CSP into SATConstraints, 2008
- Another look at graph coloring via propositional satisfiabilityDiscrete Applied Mathematics, 2008
- A competitive and cooperative approach to propositional satisfiabilityDiscrete Applied Mathematics, 2006
- Knowledge Representation, Reasoning and Declarative Problem Solving2003
- Extending and implementing the stable model semanticsArtificial Intelligence, 2002
- On the parallel complexity of discrete relaxation in constraint satisfaction networksArtificial Intelligence, 1990