Résumé
Constraint problems with incomplete or erroneous data are often simplified to tractable deterministic models, or modified using error correction methods , with the aim of seeking a solution. However, this can lead us to solve the wrong problem because of the approximations made. Such an outcome is of little help to a user who expects the right problem to be tackled and reliable information returned. The certainty closure framework we present aims to provide the user with reliable insight by: (1) enclosing the uncertainty using what is known for sure about the data, to guarantee that the true problem is contained in the model so described, (2) deriving a closure, a set of possible solutions to the uncertain constraint problem. In this paper we first demonstrate the benefits of reliable constraint reasoning on two different case studies, and then generalise our approaches into a formal framework. 1 Motivation Data uncertainties are inherent in real-world Large Scale Combinatorial Optimisation problems (LSCOs). The uncertainty can be due to the dynamic and unpredictable nature of the commercial world, but also due to the information available to those modelling the problem. In this paper we are concerned with the latter form of uncertainty, which can arise when the data is not fully known or is even erroneous. Our work is motivated by practical issues we faced when addressing two real-world applications: energy trading [11] and network traffic analysis [12]. In both applications the data information is incomplete or erroneous. In the energy trading problem, the demand and cost profiles had evolved due to market privatisation; thus the existing simulation or stochastic models did not help address the actual problem, since no valid data trends were available. Further, the obsolete data was inconsistent with the constraint model. In the network traffic analysis problem, the overwhelming amount of information forced us to use partial data. Further, due to practical measurement difficulties (e.g. unrecorded packet loss), the data acquired in the problem was frequently erroneous. When addressing the energy trading problem, we understood that the customer did not need nor want a solution to an approximation of his problem, but rather a guarantee that the model built was reliable, and that from it informed decisions could be made. Informally, a model and solution are reliable with respect to the state of the world if they accurately reflect the true problem and its possible solutions. The uncertain data is represented using what is known for sure about it, without any approximation, and no potential solutions are excluded. Our goal was to build such a model and to provide