Skip to Main content Skip to Navigation
Conference papers

Towards the Characterization of Max-Resolution Transformations of UCSs by UP-Resilience

Mohamed Sami Cherif 1 Djamal Habet 1
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Abstract : The Max-SAT problem consists in finding an assignment maximizing the number of satisfied clauses. Complete methods for this problem include Branch and Bound (BnB) algorithms which use max-resolution, the inference rule for Max-SAT, to ensure that every computed Inconsistent Subset (IS) is counted only once in the lower bound estimation. However, learning max-resolution transformations can be detrimental to their performance so they are usually selectively learned if they respect certain patterns. In this paper, we focus on recently introduced patterns called Unit Clause Subsets (UCSs). We characterize the transformations of certain UCS patterns using the UP-resilience property. Finally, we explain how our result can help extend the current patterns.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-02295154
Contributor : Djamal Habet <>
Submitted on : Tuesday, September 24, 2019 - 8:34:30 AM
Last modification on : Sunday, December 15, 2019 - 3:22:03 PM
Long-term archiving on: : Sunday, February 9, 2020 - 9:53:20 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02295154, version 1

Collections

Citation

Mohamed Sami Cherif, Djamal Habet. Towards the Characterization of Max-Resolution Transformations of UCSs by UP-Resilience. The 25th International Conference on Principles and Practice of Constraint Programming (CP 2019), pp. 91-107, Sep 2019, Stamford, United States. ⟨hal-02295154⟩

Share

Metrics

Record views

242

Files downloads

155