OSB > Neil Yorke-Smith > Research > Publications

Data Uncertainty in Constraint Programming: A Non-Probabilistic Approach

Yorke-Smith, N. and Gervet, C., Data Uncertainty in Constraint Programming: A Non-Probabilistic Approach. Proceedings of the AAAI 2001 Fall Symposium on Using Uncertainty within Computation, Cape Cod, MA, November 2001.

Abstract: The constraint programming paradigm has proved to have the flexibility and efficiency necessary to treat well-defined large-scale optimisation (LSCO) problems. Many real world problems, however, are ill-defined, incomplete, or have uncertain data. Research on ill-defined LSCO problems has centred on modelling the uncertainties by approximating the state of the real world, with no guarantee as a result that the actual problem is being solved. We focus here on ill-defined data, motivated by problems from energy trading and computer network optimisation, where no probability distribution is known or can be usefully obtained. We suggest a non-probabilistic certainty closure approach to model the data uncertainty, discuss the formalism and semantics required to build a constraint solving system based on such a computation domain, and give examples in the case of linear systems.

Postscript (56K) | PDF (96K) | Bibtex entry

Symposium homepage



Research | Home