Pasar al contenido principal

RAZONAMIENTO Y APRENDIZAJE

PID2021-122274OB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2021
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT DE GIRONA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 3
Encontrada(s) 1 página(s)

DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Complete tableau calculi for Regular MaxSAT and Regular MinSAT

  • Coll, Jordi
  • Li, Chu Min
  • Manyà, Felip
  • Yangin, Elifnaz
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
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación Artículo científico (JournalArticle)

Solving weighted Maximum Satisfiability with Branch and Bound and clause learning

  • Coll, Jordi
  • Li, Chu Min
  • Li, Shuolin
  • Habet, Djamal
  • Manyà, Felip
[Data availability] The provided link contains the software involved in this paper, including the software and the instructions and necessary data to reproduce the experiments. Source code and input parameters (Original data), MaxSAT is a widely studied NP-hard optimization problem due to its broad applicability in modeling and solving diverse real-world optimization problems. Branch-and-Bound (BnB) MaxSAT solvers have proven efficient for solving random and crafted instances but have traditionally struggled to compete with SAT-based MaxSAT solvers on industrial instances. However, this changed with the introduction of the MaxCDCL algorithm, which successfully integrates clause learning into BnB to solve unweighted MaxSAT. Despite this progress, solving Weighted MaxSAT instances remained an open challenge. In this paper, we present WMaxCDCL, the first branch-and-bound (BnB) Weighted Partial MaxSAT solver with clause learning. We describe its algorithm and implementation in detail, experimentally evaluating key aspects that are critical to achieving strong performance. Our results demonstrate that WMaxCDCL can compete with the best state-of-the-art MaxSAT solvers and, more importantly, that this new solving approach complements the existing SAT-based MaxSAT methods, which have dominated the field until now. Notably, the combination of WMaxCDCL with other techniques won the weighted track of the 2023 MaxSAT Evaluation, which is the leading annual competition for MaxSAT solvers, affiliated with the International Conference on Theory and Applications of Satisfiability Testing., This work has been supported by grants PID2022-139835NB-C21 and PID2021-122274OB-I00 funded by MCIN/AEI/10.13039/501100011033 and by ERDF, EU, and by grant ANR-19-CHIA-0013-01 co-funded by the French Agence Nationale de la Recherche and the French electricity distribution network manager Enedis. F. Manyà was supported by mobility grant PRX23/00344 of the Ministerio de Ciencia, Innovación y Universidades, Spain . We thank the Université de Picardie Jules Verne for providing the Matrics Platform., Peer reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Solving weighted Maximum Satisfiability with Branch and Bound and clause learning

  • Coll Caballero, Jordi
  • Li, Chu-Min
  • Li, Shuolin
  • Habet, Djamal
  • Manyà, Felip
MaxSAT is a widely studied NP-hard optimization problem due to its broad applicability in modeling and solving diverse real-world optimization problems. Branch-and-Bound (BnB) MaxSAT solvers have proven efficient for solving random and crafted instances but have traditionally struggled to compete with SAT-based MaxSAT solvers on industrial instances. However, this changed with the introduction of the MaxCDCL algorithm, which successfully integrates clause learning into BnB to solve unweighted MaxSAT. Despite this progress, solving Weighted MaxSAT instances remained an open challenge. In this paper, we present WMaxCDCL, the first branch-and-bound (BnB) Weighted Partial MaxSAT solver with clause learning. We describe its algorithm and implementation in detail, experimentally evaluating key aspects that are critical to achieving strong performance. Our results demonstrate that WMaxCDCL can compete with the best state-of-the-art MaxSAT solvers and, more importantly, that this new solving approach complements the existing SAT-based MaxSAT methods, which have dominated the field until now. Notably, the combination of WMaxCDCL with other techniques won the weighted track of the 2023 MaxSAT Evaluation, which is the leading annual competition for MaxSAT solvers, affiliated with the International Conference on Theory and Applications of Satisfiability Testing, This work has been supported by grants PID2022-139835NB-C21 and PID2021-122274OB-I00 funded by MCIN/AEI/10.13039/501100011033 and by ERDF, EU, and by grant ANR-19-CHIA-0013-01 co-funded by the French Agence Nationale de la Recherche and the French electricity distribution network manager Enedis. F. Manyà was supported by mobility grant PRX23/00344 of the Ministerio de Ciencia, Innovación y Universidades, Spain. Open Access funding provided thanks to the CRUE-CSIC agreement with Elsevier