Name
Abstract | ||
|---|---|---|
MaxSAT solvers have made tremendous progress in terms of performance in recent years. However, there has not been parallel progress in the generation of challenging benchmarks for studying the scaling behavior of solvers, and comparing their performance. Most experimental investigations only include, besides the standard MaxkSAT instances, the sets of individual instances submitted to the MaxSAT evaluations held so far. The problem with many of the latter instances is that they are becoming easy for modern solvers, and do not allow to analyse the scaling behavior. To cope with that problem, we propose several newgenerators of MaxSAT instances, which produce pure random instances as well as more realistic, structured instances.Moreover, we report on an experimental investigation with the aim of analysing the behavior of some of the fastest MaxSAT solvers when solving instances produced with the new generators. Our empirical results provide a new testbed of challenging benchmarks, as well as insights into the hardness nature of MaxSAT. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/ISMVL.2009.58 | ISMVL |
Keywords | Field | DocType |
modern solvers,fastest maxsat solvers,experimental investigation,generating hard instances,tremendous progress,parallel progress,scaling behavior,new generator,maxsat instance,maxsat solvers,maxsat evaluation,data mining,computability,maxsat,probability density function,benchmark testing,benchmark | Maximum satisfiability problem,Computer science,Testbed,Electronic engineering,Theoretical computer science,Computability,Artificial intelligence,Probability density function,Scaling,Machine learning,Benchmark (computing) | Conference |
Citations | PageRank | References |
1 | 0.36 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ramón Béjar | 1 | 305 | 36.72 |
| Alba Cabiscol | 2 | 31 | 3.86 |
| Felip Manyà | 3 | 787 | 59.52 |
| Jordi Planes | 4 | 486 | 31.38 |