| Title: |
Certificats d'optimalité pour Max-SAT |
| Authors: |
Py, Matthieu; Cherif, Mohamed Sami; Habet, Djamal |
| Contributors: |
COntraintes, ALgorithmes et Applications (COALA); Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon) (LIS); Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS) |
| Source: |
JFPC 2022 ; https://amu.hal.science/hal-03737729 ; JFPC 2022, Jun 2022, Saint-Etienne, France |
| Publisher Information: |
CCSD |
| Publication Year: |
2022 |
| Collection: |
Université de Toulon: HAL |
| Subject Terms: |
Optimisation Combinatoire; Problème Max-SAT; Problème SAT; Certificats d'Optimalité; [INFO]Computer Science [cs] |
| Subject Geographic: |
Saint-Etienne; France |
| Description: |
International audience ; Dans ce papier, on présente un outil, MS-Builder, qui génère des certificats pour le problème Max-SAT, en appelant itérativement un oracle SAT pour générer une réfutation par résolution de la formule qui est ensuite rendue valide pour Max-SAT et appliquée sur la formule. Ce procédé est répété jusqu'à ce que la formule restante devienne satisfiable. On propose également un outil, MS-Checker, capable de vérifier les certificats Max-SAT basés sur l'application de règles d'inférence Max-SAT. Cet article résume les travaux publiés à la conférence SAT 2021 [4]. |
| Document Type: |
conference object |
| Language: |
French |
| Availability: |
https://amu.hal.science/hal-03737729; https://amu.hal.science/hal-03737729v1/document; https://amu.hal.science/hal-03737729v1/file/JFPC_2022___Certificats_d_optimalite_pour_Max_SAT.pdf |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.B6D4E5C2 |
| Database: |
BASE |