Skip to Main content Skip to Navigation
New interface
Conference papers

Certificats d'optimalité pour Max-SAT

Matthieu Py 1 Mohamed Sami Cherif 1 Djamal Habet 1 
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Résumé : 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 papers
Complete list of metadata

https://hal-amu.archives-ouvertes.fr/hal-03737729
Contributor : Matthieu Py Connect in order to contact the contributor
Submitted on : Monday, July 25, 2022 - 1:07:29 PM
Last modification on : Saturday, September 3, 2022 - 3:51:41 AM
Long-term archiving on: : Wednesday, October 26, 2022 - 6:18:54 PM

File

JFPC_2022___Certificats_d_opti...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03737729, version 1

Collections

Citation

Matthieu Py, Mohamed Sami Cherif, Djamal Habet. Certificats d'optimalité pour Max-SAT. JFPC 2022, Jun 2022, Saint-Etienne, France. ⟨hal-03737729⟩

Share

Metrics

Record views

11

Files downloads

5