Σ-All Different: Softening AllDifferent in Weighted CSPs

Author

Métivier, Jean-Philippe ; Boizumault, Patrice ; Loudni, Samir

Author_Institution

Univ. de Caen, Caen

Volume

1

fYear

2007

fDate

29-31 Oct. 2007

Firstpage

223

Lastpage

230

Abstract

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 propose to soften AllDifferent in the Weighted CSP framework that is more general. We extend the two semantics 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 propose to maintain a local consistency using a filtering based on lower bounds computation. Finally, we present some experimental results and draw a few perspectives.

Keywords

operations research; optimisation; polynomials; Max-CSP framework; NP-hard problem; Sigma-alldifferent; binary constraints; filtering; global constraint; hyper-arc consistency; lower bounds computation; maximal constraint satisfaction problem; polynomial algorithm; weighted CSP framework; Artificial intelligence; Costs; Filtering algorithms; NP-hard problem; Polynomials; Softening; Tellurium;

fLanguage

English

Publisher

ieee

Conference_Titel

Tools with Artificial Intelligence, 2007. ICTAI 2007. 19th IEEE International Conference on

Conference_Location

Patras

ISSN

1082-3409

Print_ISBN

978-0-7695-3015-4

Type

conf

DOI

10.1109/ICTAI.2007.82

Filename

4410287