License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAT.2023.19
URN: urn:nbn:de:0030-drops-184819
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18481/
Orvalho, Pedro ;
Manquinho, Vasco ;
Martins, Ruben
UpMax: User Partitioning for MaxSAT
Abstract
It has been shown that Maximum Satisfiability (MaxSAT) problem instances can be effectively solved by partitioning the set of soft clauses into several disjoint sets. The partitioning methods can be based on clause weights (e.g., stratification) or based on graph representations of the formula. Afterwards, a merge procedure is applied to guarantee that an optimal solution is found.
This paper proposes a new framework called UpMax that decouples the partitioning procedure from the MaxSAT solving algorithms. As a result, new partitioning procedures can be defined independently of the MaxSAT algorithm to be used. Moreover, this decoupling also allows users that build new MaxSAT formulas to propose partition schemes based on knowledge of the problem to be solved. We illustrate this approach using several problems and show that partitioning has a large impact on the performance of unsatisfiability-based MaxSAT algorithms.
BibTeX - Entry
@InProceedings{orvalho_et_al:LIPIcs.SAT.2023.19,
author = {Orvalho, Pedro and Manquinho, Vasco and Martins, Ruben},
title = {{UpMax: User Partitioning for MaxSAT}},
booktitle = {26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023)},
pages = {19:1--19:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-286-0},
ISSN = {1868-8969},
year = {2023},
volume = {271},
editor = {Mahajan, Meena and Slivovsky, Friedrich},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18481},
URN = {urn:nbn:de:0030-drops-184819},
doi = {10.4230/LIPIcs.SAT.2023.19},
annote = {Keywords: Maximum Satisfiability, Formula partitioning, Graph-based methods}
}
