loading...
All Different: Softening AllDifferent in Weighted CSPs
Paris, France October 29-October 31
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICTAI.2007.8219th IEEE International Conference on ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
A soft version of the well-known global constraint AllDifferent has been recently introduced for the Max-CSP framework ([9, 15, 16]). In this paper, we pro- pose to soften AllDifferent in the Weighted CSP framework that is more general. We extend the two seman- tics of violation proposed in [9]: the first one is based on variables and the second one on the decomposition into a set of binary constraints of difference. For the first semantic, we propose a polynomial algorithm which maintains hyper- arc consistency. For the second one, we prove that checking hyper-arc consistency is an NP-Hard problem. So, we pro- pose to maintain a local consistency using a filtering based on lower bounds computation. Finally, we present some ex- perimental results and draw a few perspectives.
Citation:
Jean-Philippe M?tivier, Patrice Boizumault, Samir Loudni, "All Different: Softening AllDifferent in Weighted CSPs," ictai, vol. 1, pp.223-230, 19th IEEE International Conference on Tools with Artificial Intelligence - Vol.1 (ICTAI 2007), 2007
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions