OSB > Neil Yorke-Smith > Research > Publications
Tight and Tractable Reformulations for Uncertain CSPsYorke-Smith, N. and Gervet, C. Tight and Tractable Reformulations for Uncertain CSPs. Proceedings of CP'04 Workshop on Modelling and Reformulating Constraint Satisfaction Problems (Modelling'04). Toronto, Canada, September 2004. 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. |