2010 40th IEEE International Symposium on Multiple-Valued Logic New Insights into Encodings from MaxCSP into Partial MaxSAT Barcelona, Spain May 26-May 28 ISBN: 978-0-7695-4024-5
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISMVL.2010.17
We analyze the existing encodings from MaxCSP into Partial MaxSAT, and report on a number of new insights that we have gained from our analysis, which can be summarized as follows: (i) the at-most-one (AMO) condition can be omitted in direct encodings from MaxCSP into Partial MaxSAT, and auxiliary variables are not needed; (ii) the sequential encoding of the cardinality constraint is, in fact, a reformulation of a regular encoding; (iii) the All Different constraint based on regular literals may be simplified; (iv) if we represent, in support encodings, the supporting values of a variable using intervals, then we can derive a genuine regular support encoding without exponential blowup; and (v) the Equal constraint admits a concise representation with regular signs.
Index Terms:
Encodings, MaxCSP, Partial MaxSAT
Citation:
Josep Argelich, Alba Cabiscol, Inês Lynce, Felip Manyà, "New Insights into Encodings from MaxCSP into Partial MaxSAT," ismvl, pp.46-52, 2010 40th IEEE International Symposium on Multiple-Valued Logic, 2010 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||