OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Maintaining Alternative Values in Constraint-Based Configuration

Becker, Caroline and Fargier, Hélène Maintaining Alternative Values in Constraint-Based Configuration. (2013) In: International Joint Conference on Artificial Intelligence - IJCAI 2013, 3 September 2013 - 9 September 2013 (Beijing, China).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


Constraint programming techniques are widely used to model and solve interactive decision problems, and especially configuration problems. In this type of application, the configurable product is described by means of a set of constraints bearing on the configuration variables. The user interactively solves the CSP by assigning the variables according to her preferences. The system then has to keep the domains of the other variables consistent with these choices. Since maintaining the global inverse consistency of the domains is not tractable, the domains are instead filtered according to some level of local consistency, e.g. arc-consistency. The present paper aims at offering a more convenient interaction by providing the user with possible alternative values for the already assigned variables, i.e. values that could replace the current ones without leading to a constraint violation. We thus present the new concept of alternative domains in a (possibly) partially assigned CSP. We propose a propagation algorithm that computes all the alternative domains in a single step. Its worst case complexity is comparable to the one of the naive algorithm that would run a full propagation for each variable, but its experimental efficiency is better.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to ACM editor. The definitive version is available at http://dl.acm.org/citation.cfm?id=2540195
HAL Id:hal-04082824
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
ANR-11- BS02-008
Deposited On:08 Apr 2015 14:15

Repository Staff Only: item control page