DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación
Artículo científico (JournalArticle)
Complete tableau calculi for Regular MaxSAT and Regular MinSAT
The use of constraint models in symbolic AI has significantly increased during the last decades for their capability of certifying the existence of solutions as well as their optimality. In the latter case, approaches based on the Maximum and Minimum Satisfiability problems, or MaxSAT and MinSAT, have shown to provide state-of-the-art performances in solving many computationally challenging problems of social interest, including scheduling, timetabling and resource allocation. Indeed, the research on new approaches to MaxSAT and MinSAT is a trend still providing cutting-edge advances. In this work, we push in this direction by contributing new tableaux-based calculi for solving the MaxSAT and MinSAT problems of regular propositional logic, referred to as Regular MaxSAT and Regular MinSAT problems, respectively. For these problems, we consider as well the two extensions of the highest practical interest, namely the inclusion of weights to clauses, and the distinction between hard (mandatory) and soft (desirable) constraints. Hence, our methods handle any subclass of the most general variants: Weighted Partial Regular MaxSAT and Weighted Partial Regular MinSAT. We provide a detailed description of the methods and prove that the proposed calculi are sound and complete., This work has been supported by the French Agence Nationale de la Recherche, reference ANR-19-CHIA-0013-01, grant PID2022-139835NB-C21 funded by MICIU/AEI/10.13039/501100011033, and grant PID2021-122274OB-I00 funded by MCIN/AEI/10.13039/501100011033 and by ERDF A way of making Europe. E. Yangin was supported by grant PTA2022-022408-I funded by MICIU/AEI/10.13039/501100011033 and FSE+ . F. Manyà was supported by mobility grant PRX23/00344 of the Ministerio de Ciencia, Innovación y Universidades ., Peer reviewed
Proyecto:
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2022-139835NB-C21
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2021-122274OB-I00
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PTA2022-022408-I
DOI: http://hdl.handle.net/10261/380293, https://api.elsevier.com/content/abstract/scopus_id/85214576967
HANDLE: http://hdl.handle.net/10261/380293, https://api.elsevier.com/content/abstract/scopus_id/85214576967