An answer set optimizer based on the implicit hitting set paradigm


ASP-HS [1] instantiates the implicit hitting set approach [2, 3] to optimization for ASP. The approach is based on iterative calls to a core extractor and hitting set optimizer. ASP-HS uses WASP [4, 5] as the ASP core extractor and IBM CPLEX as the optimizer. CPLEX is available under a free academic license. ASP-HS is developed by the Constraint Optimization and Reasoning Group at the Department of Computer Science, University of Helsinki. The system is implemented by Paul Saikko.

ASP-HS extends the plain implicit hitting set approach with core minimization, disjoint cores, reduced-cost fixing, bounds based on Clark's completion, and non-core constraints.


ASP-HS is available in open source under the MIT license at GitHub.


[1] Paul Saikko, Carmine Dodaro, Mario Alviano, Matti Järvisalo: A Hybrid Approach to Optimization in Answer Set Programming. KR 2018: to appear

[2] Erick Moreno-Centeno and Richard M. Karp: The implicit hitting set approach to solve combinatorial optimization problems with an application to multi-genome alignment. Operations Research 61(2) 2013, 453-468.

[3] Paul Saikko, Johannes Peter Wallner, Matti Järvisalo: Implicit Hitting Set Algorithms for Reasoning Beyond NP. KR 2016: 104-113

[4] Mario Alviano, Carmine Dodaro, Wolfgang Faber, Nicola Leone, Francesco Ricca: WASP: A Native ASP Solver Based on Constraint Learning. LPNMR 2013: 54-66

[5] Mario Alviano, Carmine Dodaro, Nicola Leone, Francesco Ricca: Advances in WASP. LPNMR 2015: 40-54