Certainty closure: Reliable constraint reasoning with incomplete or erroneous data

ABSTRACT

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.

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 certainty closure framework 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.

REFERENCES

• 1: Aberth, O. 1997. The solution of linear interval equations by a linear programming method. Linear Algebra Appl. 259, 271--279.
• 2: Krzysztof R. Apt, The essence of constraint propagation, Theoretical Computer Science, v.221 n.1-2, p.179-210, June 28, 1999 [doi>10.1016/S0304-3975(99)00032-8]
• 3: Ben-Ameur, W. and Kerivin, H. 2005. Routing of uncertain demands. Optimiz. Engin. 3, 283--313.
• 4: Ben-Tal, A. and Nemirovski, A. 1999. Robust solutions of uncertain linear programs. Oper. Res. Lett. 25, 1--13.
• 5: Frédéric Benhamou, Interval Constraint Logic Programming, Selected Papers from Constraint Programming: Basics and Trends, p.1-21, May 16-20, 1994
• 6: Frédéric Benhamou , Frédéric Goualard, Universally Quantified Interval Constraints, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.67-82, September 18-21, 2000
• 7: Thierry Benoist , Eric Bourreau , Yves Caseau , Benoît Rottembourg, Towards Stochastic Constraint Programming: A Study of Online Multi-choice Knapsack with Deadlines, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.61-76, November 26-December 01, 2001
• 8: Bent, R. and Hentenryck, P. V. 2004. Regrets only! Online stochastic optimization under time constraints. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI'04). Menlo Park, CA, 501--506.
• 9: Bertsimas, D. and Brown, D. 2009. Constructing uncertainty sets for robust linear optimization. Oper. Res., To appear
• 10: Boerner, F., Bulatov, A., Jeavons, P., and Krokhin, A. 2003. Quantified constraints: algorithms and complexity. In Proceedings of the 17th International Workshop on Computer Science Logic (CSL'03). 58--70.
• 11: Lucas Bordeaux , Eric Monfroy, Beyond NP: Arc-Consistency for Quantified Constraints, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.371-386, September 09-13, 2002
• 12: Cheadle, A. M., Harvey, W., Sadler, A. J., Schimpf, J., Shen, K., and Wallace, M. G. 2003. ECLⁱPS^e: An Introduction. Tech. Rep. IC-Parc-03-1, IC--Parc, Imperial College London, London, UK.
• 13: Chinneck, J. W. and Ramadan, K. 2000. Linear programming with interval coefficients. J. Operational Research Society 51, 2, 209--220.
• 14: Marc Christie , Eric Languénou , Laurent Granvilliers, Modeling Camera Control with Constrained Hypertubes, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.618-632, September 09-13, 2002
• 15: 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.
• 16: Bruce Davie , Yakov Rekhter, MPLS: technology and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 17: Dovier, A., Farenzena, M., and Fusiello, A. 2005. Interval modelling with constraint propagation. In Proceedings of CP'05 Workshop on Interval Analysis and Constraint Propagation for Applications (IntCP 2005). 10--19.
• 18: Laurent El Ghaoui , Francois Oustry , Hervé Lebret, Robust Solutions to Uncertain Semidefinite Programs, SIAM Journal on Optimization, v.9 n.1, p.33-52, 1998 [doi>10.1137/S1052623496305717]
• 19: Elishakoff, I. 1995. Convex modeling—A generalization of interval analysis for nonprobabilistic treatment of uncertainty. In Proceedings of, the International Workshop on Applications of Interval Computations (APIC'95). 76--79.
• 20: Cristian Estan , George Varghese, New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.270-313, August 2003 [doi>10.1145/859716.859719]
• 21: Fargier, H., Lang, J., Martin-Clouaire, R., and Rellier, J.-P. 1994. Uncertainty and flexibility in constraint satisfaction: A case study and an application to agricultural planning. In Proceedings of ECAI-94 Workshop on Constraint Satisfaction Issues Raised by Practical Applications.
• 22: Fargier, H., Lang, J., and Schiex, T. 1996. Mixed constraint satisfaction: A framework for decision problems under incomplete knowledge. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI'96), 175--180.
• 23: Anja Feldmann , Albert Greenberg , Carsten Lund , Nick Reingold , Jennifer Rexford , Fred True, Deriving traffic demands for operational IP networks: methodology and experience, IEEE/ACM Transactions on Networking (TON), v.9 n.3, p.265-280, June 2001 [doi>10.1109/90.929850]
• 24: Feldmann, A. and Rexford, J. 2001. IP network configuration for intradomain traffic engineering. IEEE Netw. 15, 5, 46--57.
• 25: David W. Fowler , Kenneth N. Brown, Branching Constraint Satisfaction Problems for Solutions Robust under Likely Changes, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.500-504, September 18-21, 2000
• 26: Gent, I., Nightingale, P., and Stergiou, K. 2005. QCSP-Solve: A solver for quantified constraint satisfaction problems. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI'05), 138--143.
• 27: Gervet, C., Caseau, Y., and Montaut, D. 1999. On refining ill-defined constraint problems: A case study in iterative prototyping. In Proceedings of the 1st International Conference on the Practical Applications of Constraint Technologies and Logic Programming (PACLP'99). Lecture Notes in Computer Science, vol. 1644 Springer-Verlag, Berlin, Germany, 255--275.
• 28: Gervet, C. and Rodošek, R. 2000. RiskWise-2 problem definition. IC--Parc Internal Report.
• 29: Goldschmidt, O. 2000. ISP backbone traffic inference methods to support traffic engineering. In Proceedings of the Internet Statistics and Metrics Analysis Winter 2000 Workshop.
• 30: 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.
• 31: Joseph Y. Halpern, Reasoning about Uncertainty, MIT Press, Cambridge, MA, 2003
• 32: Warwick Harvey, Computing Two-Dimensional Integer Hulls, SIAM Journal on Computing, v.28 n.6, p.2285-2299, Dec. 1999 [doi>10.1137/S009753979528977X]
• 33: Karla L. Hoffman, Combinatorial optimization: current successes and directions for the future, Journal of Computational and Applied Mathematics, v.124 n.1-2, p.341-360, Dec. 2000 [doi>10.1016/S0377-0427(00)00430-1]
• 34: Jaulin, L. 2006. Localization of an underwater robot using interval constraints propagation. In Proceedings of 12th International Conference on Constraint Programming (CP'06). 244--255.
• 35: Lhomme, O. 2003. An efficient filtering algorithm for disjunction of constraints. In Proceedings of 9th International Conference on Constraint Programming (CP'03). 904--908.
• 36: Maher, M. J. 2003. A synthesis of constraint satisfaction and constraint solving. In Proceedings of 10th International Conference on Constraint Programming (CP'03), 525--539.
• 37: Mamoulis, N. and Stergiou, K. 2004. Algorithms for quantified constraint satisfaction problems. In Proceedings of 10th International Conference on Constraint Programming. 752--756.
• 38: Manandhar, S., Tarim, A., and Walsh, T. 2003. Scenario-based stochastic constraint programming. In Proceedings of 18th International Joint Conference on Artificial Intelligence (IJCAI'03), 257--262.
• 39: A. Medina , N. Taft , K. Salamatian , S. Bhattacharyya , C. Diot, Traffic matrix estimation: existing techniques and new directions, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 40: Morris, P. 2006. A structural characterization of temporal dynamic controllability. In Proceedings of 12th International Conference on Constraint Programming (CP'06), 375--389.
• 41: Moy, J. 1998. RFC 2328: OSPF version 2. Tech. Rep. RFC2328.
• 42: Narin'yani, A., Hoffman, J., Inishev, D., and Banasyukevich, D. 2000. Time-EX as an application of constraint programming based on subdefinite models. In Proceedings of ERCIM/CompulogNet 2000 Workshop on Constraints.
• 43: Neumaier, A. 1990. Interval Methods for Systems of Equations. Cambridge University Press, Cambridge, UK.
• 44: Oettli, W. 1965. On the solution set of a linear system with inaccurate coefficients. J. SIAM: Series B, Nume. Anal. 2, 1, 115--118.
• 45: Ratschan, S. 2000. Approximate quantified constraint solving (AQCS). www.risc.uni-linz.ac.at/research/software/AQCS. Software Package.
• 46: Ratschan, S. 2003. Solving existentially quantified constraints with one equality and arbitrary many inequalities. In Proceedings of 9th International Conference on Constraint Programming (CP'03), 615--633.
• 47: Stefan Ratschan, Efficient solving of quantified inequality constraints over the real numbers, ACM Transactions on Computational Logic (TOCL), v.7 n.4, p.723-748, October 2006 [doi>10.1145/1183278.1183282]
• 48: Rodošek, R. and Richards, E. B. 2003. Traffic flow optimization system. European Patent No. EP1332583.
• 49: Schnoor, H. and Schnoor, I. 2006. Enumerating all solutions for constraint satisfaction problems. Technical report, Institut für Theoretische Informatik, Universität Hannover.
• 50: Alexander Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 51: Simonis, H. and Hansen, J. 2006. Constraint-based resilience analysis. In Proceedings of the 12th International Conference on Constraint Programming (CP'06). 16--28
• 52: Neil Spring , Ratul Mahajan , David Wetherall , Thomas Anderson, Measuring ISP topologies with rocketfuel, IEEE/ACM Transactions on Networking (TON), v.12 n.1, p.2-16, February 2004 [doi>10.1109/TNET.2003.822655]
• 53: S. Armagan Tarim , Suresh Manandhar , Toby Walsh, Stochastic Constraint Programming: A Scenario-Based Approach, Constraints, v.11 n.1, p.53-80, January 2006 [doi>10.1007/s10601-006-6849-7]
• 54: Tsang, E. 1993. Foundations of Constraint Satisfaction. Academic Press, London, UK.
• 55: Peter van Beek , Rina Dechter, On the minimality and global consistency of row-convex constraint networks, Journal of the ACM (JACM), v.42 n.3, p.543-561, May 1995 [doi>10.1145/210346.210347]
• 56: Van Hentenryck, P., Michel, L., and Deville, Y. 1997. Numerica: A Modeling Language for Global Optimization. MIT Press, Cambridge, MA.
• 57: Van Hentenryck, P., Saraswat, V. A., and Deville, Y. 1998. Design, implementation, and evaluation of the constraint language cc(FD). J. Logic Progr. 37, 1--3, 139--164.
• 58: Gérard Verfaillie , Narendra Jussien, Constraint Solving in Uncertain and Dynamic Environments: A Survey, Constraints, v.10 n.3, p.253-281, July 2005 [doi>10.1007/s10601-005-2239-9]
• 59: Vidal, T. and Fargier, H. 1999. Handling contingency in temporal constraint networks: From consistency to controllabilities. J. Exper. Theoret. Artif. Intell. 11, 1, 23--45.
• 60: Alfio Vidotto , Kenneth N. Brown , J. Christopher Beck, Managing restaurant tables using constraints, Knowledge-Based Systems, v.20 n.2, p.160-169, March, 2007 [doi>10.1016/j.knosys.2006.11.002]
• 61: Wallace, M. G. 1996. Practical applications of constraint programming. Constraints 1, 1/2, 139--168.
• 62: Yorke-Smith, N. 2004. Reliable constraint reasoning with uncertain data. Ph.D. dissertation, IC-Parc, Imperial College London.
• 63: Yorke-Smith, N. and Gervet, C. 2005. Uncertain constraint optimization problems. In Proceedings of CP'05 Workshop on Preferences and Soft Constraints (Soft'05). 147--161.
• 64: Yorke-Smith, N. and Guettier, C. 2003. Towards automatic robust planning for the discrete commanding of aerospace equipment. In Proceedings of the 18th IEEE International Symposium on Intelligent Control (ISIC'03). 328--333.
• 65: Yin Zhang , Matthew Roughan , Carsten Lund , David Donoho, An information-theoretic approach to traffic matrix estimation, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863990]
• 66: Yuanlin Zhang , Roland H. C. Yap, Arc Consistency on n-ary Monotonic and Linear Constraints, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.470-483, September 18-21, 2000
• 67: Kemin Zhou , John C. Doyle , Keith Glover, Robust and optimal control, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Algorithms, Reliability

Keywords:
Incomplete and erroneous data, closure, reliable solutions, uncertain constraint satisfaction problem