Uncertain Constraint Optimisation Problems

Yorke-Smith, N. and Gervet, C. Uncertain Constraint Optimisation Problems. Proceedings of CP'05 Workshop on Preferences and Soft Constraints, Sitges, Spain, October 2005.

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.

PDF (130K) | Bibtex entry

Workshop homepage