Name
Abstract | ||
|---|---|---|
We define a number of original encodings, called regular encodings, that map Max-CSP instances into Partial Max-SAT instances. First, we obtain new direct and (minimal)support encodings by modelling the at-least-one and at-most-one conditions using a regular signed encoding. This way, we obtain encodings in which the hard part is more compact. Second, even when we need to introduce auxiliary variables in the regular encodings, we prove that it is sufficient to limit branching to non-auxiliary variables. Third, we report on an experimental investigation which provides evidence that the minimal support encoding is well-suited on more structured, realistic instances (the experiments performed so far were limited to randomly generated binary CSPs), and that the regular encodings defined here have a very competitive performance profile when branching is limited to non-auxiliary variables. We show that regular encodings allow to solve more instances and more efficiently than using the existing encodings from Max-CSP into Partial Max-SAT. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/ISMVL.2009.23 | ISMVL |
Keywords | Field | DocType |
original encodings,partial max-sat,existing encodings,regular encodings,minimal support encoding,partial max-sat instance,map max-csp instance,regular signed encoding,at-most-one condition,support encodings,encoding,programming,gain,computability,logic,data mining,probability density function | Maximum satisfiability problem,Discrete mathematics,Computer science,Constraint theory,Computability,Auxiliary variables,Probability density function,Binary number,Encoding (memory),Branching (version control) | Conference |
Citations | PageRank | References |
2 | 0.42 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Argelich | 1 | 190 | 18.95 |
| Alba Cabiscol | 2 | 31 | 3.86 |
| Inês Lynce | 3 | 889 | 58.30 |
| Felip Manyà | 4 | 787 | 59.52 |