{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:34:56Z","timestamp":1750307696439,"version":"3.41.0"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["GR\/N64373\/01"],"award-info":[{"award-number":["GR\/N64373\/01"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>Constraint Programming (CP) has proved an effective paradigm to model and solve difficult combinatorial satisfaction and optimization problems from disparate domains. Many such problems arising from the commercial world are permeated by data uncertainty. Existing CP approaches that accommodate uncertainty are less suited to uncertainty arising due to incomplete and erroneous data, because they do not build reliable models and solutions guaranteed to address the user's genuine problem as she perceives it. Other fields such as reliable computation offer combinations of models and associated methods to handle these types of uncertain data, but lack an expressive framework characterizing the resolution methodology independently of the model.<\/jats:p><jats:p>We present a unifying framework that extends the CP formalism in both model and solutions, to tackle ill-defined combinatorial problems with incomplete or erroneous data. The<jats:italic>certainty closure framework<\/jats:italic>brings together modeling and solving methodologies from different fields into the CP paradigm to provide reliable and efficient approches for uncertain constraint problems. We demonstrate the applicability of the framework on a case study in network diagnosis. We define resolution forms that give generic templates, and their associated operational semantics, to derive practical solution methods for reliable solutions.<\/jats:p>","DOI":"10.1145\/1459010.1459013","type":"journal-article","created":{"date-parts":[[2009,1,29]],"date-time":"2009-01-29T13:48:36Z","timestamp":1233236916000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Certainty closure"],"prefix":"10.1145","volume":"10","author":[{"given":"Neil","family":"Yorke-Smith","sequence":"first","affiliation":[{"name":"IC--Parc, Imperial College London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmen","family":"Gervet","sequence":"additional","affiliation":[{"name":"IC--Parc, Imperial College London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,1,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(96)00291-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00032-8"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11081-005-1741-7"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(99)00016-4"},{"volume-title":"Constraint Programming: Basics and Trends","series-title":"Lecture Notes in Computer Science","author":"Benhamou F.","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the 6th International Conference on Constraint Programming (CP'00)","author":"Benhamou F.","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the 7th International Conference on Constraint Programming (CP'01)","author":"Benoist T.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the 19th National Conference on Artificial Intelligence (AAAI'04)","author":"Bent R.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Bertsimas D. and Brown D. 2009. Constructing uncertainty sets for robust linear optimization. Oper. Res. To appear Bertsimas D. and Brown D. 2009. Constructing uncertainty sets for robust linear optimization. Oper. Res. To appear","DOI":"10.1287\/opre.1080.0646"},{"volume-title":"Proceedings of the 17th International Workshop on Computer Science Logic (CSL'03)","author":"Boerner F.","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of the 8th International Conference on Constraint Programming (CP'02)","author":"Bordeaux L.","key":"e_1_2_1_11_1"},{"volume-title":"Tech. Rep. IC-Parc-03-1, IC--Parc","year":"2003","author":"Cheadle A. M.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600891"},{"volume-title":"Proceedings of the 8th International Conference on Constraint Programming (CP'02)","author":"Christie M.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","unstructured":"Davenport A. J. and Beck J. C. 2000. A survey of techniques for scheduling with uncertainty. http:\/\/tidel.mie.utoronto.ca\/pubs\/uncertainty-survey.ps.zip. Davenport A. J. and Beck J. C. 2000. A survey of techniques for scheduling with uncertainty. http:\/\/tidel.mie.utoronto.ca\/pubs\/uncertainty-survey.ps.zip."},{"key":"e_1_2_1_16_1","unstructured":"Davie B. and Rekhter Y. 2000. MPLS Technonlogy and Applications. Morgan Kaufmann San Francisco CA. Davie B. and Rekhter Y. 2000. MPLS Technonlogy and Applications. Morgan Kaufmann San Francisco CA."},{"volume-title":"Proceedings of CP'05 Workshop on Interval Analysis and Constraint Propagation for Applications (IntCP","year":"2005","author":"Dovier A.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623496305717"},{"volume-title":"Proceedings of, the International Workshop on Applications of Interval Computations (APIC'95)","year":"1995","author":"Elishakoff I.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/859716.859719"},{"volume-title":"Proceedings of ECAI-94 Workshop on Constraint Satisfaction Issues Raised by Practical Applications.","author":"Fargier H.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the 13th National Conference on Artificial Intelligence (AAAI'96)","author":"Fargier H.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.929850"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.953233"},{"volume-title":"Proceedings of the 6th International Conference on Constraint Programming (CP'00)","author":"Fowler D. W.","key":"e_1_2_1_25_1"},{"volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI'05)","author":"Gent I.","key":"e_1_2_1_26_1"},{"volume":"1644","volume-title":"Proceedings of the 1st International Conference on the Practical Applications of Constraint Technologies and Logic Programming (PACLP'99)","author":"Gervet C.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Gervet C. and Rodo\u0161ek R. 2000. RiskWise-2 problem definition. IC--Parc Internal Report. Gervet C. and Rodo\u0161ek R. 2000. RiskWise-2 problem definition. IC--Parc Internal Report.","DOI":"10.1016\/S0294-3506(00)88149-1"},{"volume-title":"Proceedings of the Internet Statistics and Metrics Analysis","year":"2000","author":"Goldschmidt O.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Grossglauser M. and Rexford J. 2004. Passive traffic measurement for IP operations. In The Internet as a Large-Scale Complex System K. Park and W. Willinger Eds. Oxford University Press Oxford UK. Grossglauser M. and Rexford J. 2004. Passive traffic measurement for IP operations. In The Internet as a Large-Scale Complex System K. Park and W. Willinger Eds. Oxford University Press Oxford UK.","DOI":"10.1093\/oso\/9780195157208.003.0002"},{"key":"e_1_2_1_31_1","unstructured":"Halpern J. Y. 2003. Reasoning About Uncertainty. MIT Press Cambridge MA. Halpern J. Y. 2003. Reasoning About Uncertainty. MIT Press Cambridge MA."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979528977X"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(00)00430-1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11889205_19"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45193-8_76"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45193-8_36"},{"volume-title":"Proceedings of 10th International Conference on Constraint Programming. 752--756","author":"Mamoulis N.","key":"e_1_2_1_37_1"},{"volume-title":"Proceedings of 18th International Joint Conference on Artificial Intelligence (IJCAI'03)","author":"Manandhar S.","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633041"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/11889205_28"},{"volume-title":"Proceedings of ERCIM\/CompulogNet 2000 Workshop on Constraints.","author":"Narin'yani A.","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Neumaier A. 1990. Interval Methods for Systems of Equations. Cambridge University Press Cambridge UK. Neumaier A. 1990. Interval Methods for Systems of Equations. Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511526473"},{"key":"e_1_2_1_44_1","first-page":"115","article-title":"On the solution set of a linear system with inaccurate coefficients. J. SIAM: Series B, Nume","volume":"2","author":"Oettli W.","year":"1965","journal-title":"Anal."},{"key":"e_1_2_1_45_1","unstructured":"Ratschan S. 2000. Approximate quantified constraint solving (AQCS). www.risc.uni-linz.ac.at\/research\/software\/AQCS. Software Package. Ratschan S. 2000. Approximate quantified constraint solving (AQCS). www.risc.uni-linz.ac.at\/research\/software\/AQCS. Software Package."},{"volume-title":"Proceedings of 9th International Conference on Constraint Programming (CP'03)","year":"2003","author":"Ratschan S.","key":"e_1_2_1_46_1"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183278.1183282"},{"key":"e_1_2_1_48_1","unstructured":"Rodo\u0161ek R. and Richards E. B. 2003. Traffic flow optimization system. European Patent No. EP1332583. Rodo\u0161ek R. and Richards E. B. 2003. Traffic flow optimization system. European Patent No. EP1332583."},{"key":"e_1_2_1_49_1","unstructured":"Schnoor H. and Schnoor I. 2006. Enumerating all solutions for constraint satisfaction problems. Technical report Institut f\u00fcr Theoretische Informatik Universit\u00e4t Hannover. Schnoor H. and Schnoor I. 2006. Enumerating all solutions for constraint satisfaction problems. Technical report Institut f\u00fcr Theoretische Informatik Universit\u00e4t Hannover."},{"key":"e_1_2_1_50_1","unstructured":"Schrijver A. 1986. Theory of Linear and Integer Programming. Wiley New York. Schrijver A. 1986. Theory of Linear and Integer Programming. Wiley New York."},{"volume-title":"Proceedings of the 12th International Conference on Constraint Programming (CP'06)","author":"Simonis H.","key":"e_1_2_1_51_1"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.822655"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-006-6849-7"},{"key":"e_1_2_1_54_1","unstructured":"Tsang E. 1993. Foundations of Constraint Satisfaction. Academic Press London UK. Tsang E. 1993. Foundations of Constraint Satisfaction. Academic Press London UK."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/210346.210347"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/5073.001.0001"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(98)10006-7"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-005-2239-9"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1080\/095281399146607"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2006.11.002"},{"key":"e_1_2_1_61_1","doi-asserted-by":"crossref","unstructured":"Wallace M. G. 1996. Practical applications of constraint programming. Constraints 1 1\/2 139--168. Wallace M. G. 1996. Practical applications of constraint programming. Constraints 1 1\/2 139--168.","DOI":"10.1007\/BF00143881"},{"key":"e_1_2_1_62_1","unstructured":"Yorke-Smith N. 2004. Reliable constraint reasoning with uncertain data. Ph.D. dissertation IC-Parc Imperial College London. Yorke-Smith N. 2004. Reliable constraint reasoning with uncertain data. Ph.D. dissertation IC-Parc Imperial College London."},{"volume-title":"Proceedings of CP'05 Workshop on Preferences and Soft Constraints (Soft'05)","author":"Yorke-Smith N.","key":"e_1_2_1_63_1"},{"volume-title":"Proceedings of the 18th IEEE International Symposium on Intelligent Control (ISIC'03)","author":"Yorke-Smith N.","key":"e_1_2_1_64_1"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863990"},{"volume-title":"Proceedings of the 6th International Conference on Constraint Programming (CP'00)","author":"Zhang Y.","key":"e_1_2_1_66_1"},{"key":"e_1_2_1_67_1","unstructured":"Zhou K. Doyle J. C. and Glover K. 1996. Robust and Optimal Control. Prentice-Hall England Cliffs NJ. Zhou K. Doyle J. C. and Glover K. 1996. Robust and Optimal Control. Prentice-Hall England Cliffs NJ."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1459010.1459013","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1459010.1459013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:57Z","timestamp":1750253397000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1459010.1459013"}},"subtitle":["Reliable constraint reasoning with incomplete or erroneous data"],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1459010.1459013"],"URL":"https:\/\/doi.org\/10.1145\/1459010.1459013","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"2006-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}