On the Performance of MaxSAT and MinSAT Solvers on 2SAT-MaxOnes
MetadataShow full item record
We analyze and compare two solvers for Boolean optimization problems: WMaxSatz, a solver for Partial MaxSAT, and MinSatz, a solver for Partial MinSAT. Both MaxSAT and MinSAT are similar, but previous results indicate that when solving optimization problems using both solvers, the performance is quite different on some cases. For getting insights about the differences in the performance of the two solvers, we analyze their behaviour when solving 2SAT-MaxOnes problem instances, given that 2SAT-MaxOnes is probably the most simple, but NP-hard, optimization problem we can solve with them. The analysis is based first on the study of the bounds computed by both algorithms on some particular 2SAT-MaxOnes instances, characterized by the presence of certain particular structures. We find that the fraction of positive literals in the clauses is an important factor regarding the quality of the bounds computed by the algorithms. Then, we also study the importance of this factor on the typical case complexity of Random-p 2SAT-MaxOnes, a variant of the problem where instances are randomly generated with a probability p of having positive literals in the clauses. For the case p=0, the performance results indicate a clear advantage of MinSatz with respect to WMaxSatz, but as we consider positive values of p WMaxSatz starts to show a better performance, although at the same time the typical complexity of Random-p 2SAT-MaxOnes decreases as p increases. We also study the typical value of the bound computed by the two algorithms on these sets of instances, showing that the behaviour is consistent with our analysis of the bounds computed on the particular instances we studied first.
Is part ofAnnals of Mathematics and Artificial Intelligence, 2016, vol. 77, núm. 1, p. 43-66
European research projects
Showing items related by title, author, creator and subject.
Alsinet, Teresa; Argelich Romà, Josep; Béjar Torres, Ramón; Fernàndez Camon, César; Mateu Piñol, Carles; Planes Cid, Jordi (Elsevier, 2017-03-01)Twitter has become a widely used social network to discuss ideas about many domains. This leads to a growing interest in understanding what are the major accepted or rejected opinions in different domains by social network ...
An argumentative approach for discovering relevant opinions in Twitter with probabilistic valued relationships Alsinet, Teresa; Argelich Romà, Josep; Béjar Torres, Ramón; Fernàndez Camon, César; Mateu Piñol, Carles; Planes Cid, Jordi (Elsevier, 2017-07-08)Twitter is one of the most widely used social networks when it comes to sharing and criticizing relevant news and events. In order to understand the major opinions accepted and rejected in different domains by Twitter ...
Béjar Torres, Ramón; Mateu Piñol, Carles; Fernàndez Camon, César; Guitart Bravo, Francesc (IOS Press, 2015)The Routing and Wavelength Assignment (RWA) problem is an optical networking problem that aims to improve data transmission by eliminating optoelectronic conversions through the network. The RWA problem is in the set of ...