Clausal Forms in MaxSAT and MinSAT - Université de Picardie Jules Verne Accéder directement au contenu
Article Dans Une Revue International Journal of Computational Intelligence Systems Année : 2022

Clausal Forms in MaxSAT and MinSAT

Joan Ramon Soler
  • Fonction : Auteur
Amanda Vidal


Abstract We tackle the problem of reducing non-clausal MaxSAT and MinSAT to clausal MaxSAT and MinSAT. Our motivation is twofold: (i) the clausal form transformations used in SAT are unsound for MaxSAT and MinSAT, because they do not preserve the minimum or maximum number of unsatisfied clauses, and (ii) the state-of-the-art MaxSAT and MinSAT solvers require as input a multiset of clauses. The main contribution of this paper is the definition of three different cost-preserving transformations. Two transformations extend the usual equivalence preserving transformation used in SAT to MaxSAT and MinSAT. The third one extends the well-known Tseitin transformation. Furthermore, we report on an empirical comparison of the performance of the proposed transformations when solved with a state-of-the-art MaxSAT solver.

Dates et versions

hal-03869414 , version 1 (24-11-2022)



Chu Min Li, Felip Manyà, Joan Ramon Soler, Amanda Vidal. Clausal Forms in MaxSAT and MinSAT. International Journal of Computational Intelligence Systems, 2022, 15 (1), pp.97. ⟨10.1007/s44196-022-00143-z⟩. ⟨hal-03869414⟩


10 Consultations
0 Téléchargements



Gmail Facebook Twitter LinkedIn More