Publication Details

Tight and Tractable Reformulations for Uncertain CSPs

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

in Proceedings of CP'04 Workshop on Modelling and Reformulating Constraint Satisfaction Problems pp. 142-158,

Abstract

Various extensions of the CSP framework exist to address ill-defined, real-world optimisation problems. One extension, the uncertain CSP (UCSP) tackles the aspect of data errors and incompleteness by ensuring that the problem is faithfully represented with what is known for sure about the data, and by seeking reliable solutions that do not approximate such uncertainties. The extended model has a great impact on the solving complexity. For instance, by introducing bounded interval coefficients, the default representation of an arithmetic linear constraint is of degree two. A challenge lies in determining constraint classes that allow one to reformulate the UCSP model such that polynomial algorithms exist. In this paper we present two novel sufficient conditions, built on algebraic properties of constraints, that ensure a tractable reformulation exists. We give an algorithm to test for the conditions for binary constraints, and demonstrate as instances some previously identified practical UCSP reformulations.

Electronic Copies

Adobe PDF

BibTeX

EndNote

AIC Personnel

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