loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
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.