Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T10:19:10.188Z Has data issue: false hasContentIssue false
  • English
  • Français

The P-Box CDF-Intervals: A Reliable Constraint Reasoning with Quantifiable Information

Published online by Cambridge University Press:  21 July 2014

AYA SAAD ,
THOM FRÜHWIRTH  and
CARMEN GERVET
AYA SAAD
Affiliation:
Universität Ulm, Germany (e-mail: [email protected], [email protected])
THOM FRÜHWIRTH
Affiliation:
Universität Ulm, Germany (e-mail: [email protected], [email protected])
CARMEN GERVET
Affiliation:
Université de Savoie, France (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper introduces a new constraint domain for reasoning about data with uncertainty. It extends convex modeling with the notion of p-box to gain additional quantifiable information on the data whereabouts. Unlike existing approaches, the p-box envelops an unknown probability instead of approximating its representation. The p-box bounds are uniform cumulative distribution functions (cdf) in order to employ linear computations in the probabilistic domain. The reasoning by means of p-box cdf-intervals is an interval computation which is exerted on the real domain then it is projected onto the cdf domain. This operation conveys additional knowledge represented by the obtained probabilistic bounds. The empirical evaluation of our implementation shows that, with minimal overhead, the output solution set realizes a full enclosure of the data along with tighter bounds on its probabilistic distributions.

Keywords

convex structuresreliable constraint reasoningprobability boxcdf intervalconstraint satisfaction problemconstraint programmingconstraint reasoninguncertainty
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Special Issue 4-5: 30th International Conference on Logic Programming , July 2014 , pp. 461 - 475
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Benhamou, F. and Older, W. J. 1997. Applying interval arithmetic to real, integer, and boolean constraints. The Journal of Logic Programming 32, 1, 1–24.Google Scholar
Bistarelli, S., Frühwirth, T., and Marte, M. 2002. Soft constraint propagation and solving in chrs. In Proceedings of the 2002 ACM symposium on Applied computing. ACM, 1–5.Google Scholar
Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., and Fargier, H. 1999. Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison. Constraints 4, 3, 199–240.Google Scholar
Climent, L., Wallace, R. J., Salido, M. A., and Barber, F. 2014. Robustness and stability in constraint programming under dynamism and uncertainty. Journal of Artificial Intelligence Research 49, 49–78.CrossRefGoogle Scholar
Dubois, D., Fargier, H., and Prade, H. 1996. Possibility theory in constraint satisfaction problems: Handling priority, preference and uncertainty. Applied Intelligence 6, 4, 287–309.Google Scholar
Dutta, P., Chakraborty, D., and Roy, A. 2005. A single-period inventory model with fuzzy random variable demand. Mathematical and Computer Modelling 41, 8, 915–922.CrossRefGoogle Scholar
ECRC. 1994. Eclipse (a) user manual, (b) extensions of the user manual. Tech. rep., ECRC.Google Scholar
Fargier, H., Lang, J., and Schiex, T. 1996. Mixed constraint satisfaction: A framework for decision problems under incomplete knowledge. In Proceedings of the National Conference on Artificial Intelligence. 175–180.Google Scholar
Ferson, S., Kreinovich, V., Ginzburg, L., Myers, D., and Sentz, K. 2003. Constructing Probability Boxes and Dempster-Shafer structures, Sandia National Laboratories. Tech. rep., SANDD2002-4015.Google Scholar
Glen, A., Leemis, L., and Drew, J. 2004. Computing the distribution of the product of two continuous random variables. Computational statistics & data analysis 44, 3, 451–464.CrossRefGoogle Scholar
Gum, I. 1995. Guide to the expression of uncertainty in measurement. BIPM, IEC, IFCC, ISO, IUPAP, IUPAC, OIML.Google Scholar
Halpern, J. 2003. Reasoning about uncertainty.Google Scholar
Holzbaur, C. 1992. Metastructures vs. attributed variables in the context of extensible unification - applied for the implementation of clp languages. In In 1992 International Symposium on Programming Language Implementation and Logic Programming. Springer Verlag, 260–268.Google Scholar
Jaffar, J. and Lassez, J.-L. 1987. Constraint logic programming. In Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. ACM, 111–119.Google Scholar
Le Huitouze, S. 1990. A new data structure for implementing extensions to Prolog. In Programming Language Implementation and Logic Programming. Springer, 136–150.Google Scholar
Petrović, D., Petrović, R., and Vujošević, M. 1996. Fuzzy models for the newsboy problem. International Journal of Production Economics 45, 1, 435–441.CrossRefGoogle Scholar
Saad, A., Gervet, C., and Abdennadher, S. 2010. Constraint Reasoning with Uncertain Data Using CDF-Intervals. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 292–306.Google Scholar
Saad, A., Gervet, C., and Fruehwirth, T. 2012. CDF-Intervals Revisited. The Eleventh International Workshop on Constraint Modelling and Reformulation - ModRef2012.Google Scholar
Schiex, T., Fargier, H., and Verfaillie, G. 1995. Valued constraint satisfaction problems: Hard and easy problems. In International Joint Conference on Artificial Intelligence. Vol. 14. 631–639.Google Scholar
Smith, W. and La Poutre, H. 1992. Approximation of staircases by staircases. Tech. rep., 92-109-3-0058-8 NEC Research Institute Inc., New Jersey.Google Scholar
Tarim, S. and Kingsman, B. 2004. The stochastic dynamic production/inventory lot-sizing problem with service-level constraints. International Journal of Production Economics 88, 105–119.Google Scholar
Tarim, S. A., Manandhar, S., and Walsh, T. 2006. Stochastic constraint programming: A scenario-based approach. Constraints 11, 1, 53–80.Google Scholar
Walsh, T. 2002. Stochastic constraint programming. Proceedings of the 15th Eureopean Conference on Artificial Intelligence, 111–115.Google Scholar
Yorke-Smith, N. and Gervet, C. 2009. Certainty closure: Reliable constraint reasoning with incomplete or erroneous data. ACM Transactions on Computational Logic (TOCL) 10, 1, 3.Google Scholar