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 \(\varDelta _{n+1}^P\) . 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

  • Damiano Azzolini,
  • Nicola Leone,
  • Giuseppe Mazzotta,
  • Francesco Ricca

摘要

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 \(\varDelta _{n+1}^P\) . 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.