Skip to Main content Skip to Navigation
Poster communications

Understanding the power of Max-SAT resolution through UP-resilience

Mohamed Sami Cherif 1 Djamal Habet 1 André Abrame 2 
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Abstract : Input: a formula Φ in Conjunctive Normal Form (CNF) Output: the maximum (resp. minimum) number of satisfied (resp. falsified) clauses in Φ over all possible variable assignments Branch & Bound (BnB) for Max-SAT Binary search algorithm which maintains and constantly updates two values : Upper Bound (UB): value of the best known solution Lower Bound (LB): estimation of the best accessible solution Cut: if LB ≥ UB then backtrack
Document type :
Poster communications
Complete list of metadata

https://hal-amu.archives-ouvertes.fr/hal-03334479
Contributor : Mohamed Sami CHERIF Connect in order to contact the contributor
Submitted on : Friday, September 3, 2021 - 7:13:11 PM
Last modification on : Sunday, June 26, 2022 - 10:18:35 AM
Long-term archiving on: : Saturday, December 4, 2021 - 8:07:28 PM

File

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

Identifiers

  • HAL Id : hal-03334479, version 1

Collections

Citation

Mohamed Sami Cherif, Djamal Habet, André Abrame. Understanding the power of Max-SAT resolution through UP-resilience. Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21), Aug 2021, Montreal-themed Virtual Reality, Canada. ⟨hal-03334479⟩

Share

Metrics

Record views

100

Files downloads

34