Answer Set Programming with Quantifiers (ASP(Q)) extends classical ASP to naturally capture problems within the polynomial hierarchy (PH). Recently, the formalism has been enriched with weak constraints to express both local and global optimization criteria, enabling the modeling of problems in Δn+1P. In this paper, we present the first implementation of ASP(Q) with global weak constraints, built on top of the state-of-the-art ASP(Q) system PyQASP, based on an upper-bound improving strategy that effectively guides the search toward optimal solutions. Experiments demonstrate that our approach can be effectively applied to solve hard optimization problems.
Solving Hard Combinatorial Optimization Problems with PyQASP
Azzolini D.
;
2026
Abstract
Answer Set Programming with Quantifiers (ASP(Q)) extends classical ASP to naturally capture problems within the polynomial hierarchy (PH). Recently, the formalism has been enriched with weak constraints to express both local and global optimization criteria, enabling the modeling of problems in Δn+1P. In this paper, we present the first implementation of ASP(Q) with global weak constraints, built on top of the state-of-the-art ASP(Q) system PyQASP, based on an upper-bound improving strategy that effectively guides the search toward optimal solutions. Experiments demonstrate that our approach can be effectively applied to solve hard optimization problems.I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
