Publication Details

Uncertain Constraint Optimisation Problems

by Yorke-Smith, N. and Gervet, C.

in Proceedings of CP'05 Workshop on Preferences and Soft Constraints pp. 147-161,

Abstract

Data uncertainties are inherent in the real world. The uncertain CSP (UCSP) is an extension of classical CSP that models incomplete and erroneous data by coefficients in the constraints whose values are unknown but bounded, for instance by an interval. It resolution is a closure, a set of potential solutions. This paper extends the UCSP model to account for optimisation criteria, by defining the uncertain CSOP. The challenge is to combine optimisation (preferences over individual solutions) with a closure of a certain type (preference over sets of solutions) to a UCSOP. Unlike traditional CSOPs we need to compare closures (i.e. families of solutions) rather than just single solutions. We address this problem in a two stage process. First, non-dominated closures present the choice of solutions to a UCSOP; once one is chosen, second, its refinement to a redundancy-free or optimal closure balances reliability and optimality as the user specifies. We describe means to effectively perform these derivations by leveraging decision analysis under uncertainty and multi-criteria optimisation theory.

Electronic Copies

Adobe PDF

BibTeX

EndNote

AIC Personnel

	Name	Title	E-mail
	Yorke-Smith, Neil	Computer Scientist