×

Exploiting functional dependencies in declarative problem specifications. (English) Zbl 1168.68552

Summary: We tackle the issue of the automatic recognition of functional dependencies among guessed predicates in constraint problem specifications. Functional dependencies arise frequently in pure declarative specifications, because of the intermediate results that need to be computed in order to express some of the constraints, or due to precise modeling choices, e.g., to provide multiple viewpoints of the search space in order to increase constraint propagation. In either way, the recognition of dependencies greatly helps solvers, allowing them to avoid spending search on unfruitful branches, while maintaining the highest degree of declarativeness. By modeling constraint problem specifications as second-order formulae, we provide a characterization of functional dependencies in terms of semantic properties of first-order ones, and prove undecidability of the problem of their recognition. Despite such negative result, we advocate the (in many cases effective) possibility of using automated tools to mechanize this task. Additionally, we show how suitable search procedures can be automatically synthesized in order to exploit recognized dependencies. We present OPL examples of various problems, taken from bio-informatics, planning and resource allocation, and show how in many cases OPL greatly benefits from the addition of such search procedures. Moreover, we also give evidence that writing sophisticated ad-hoc search procedures that handle dependencies exploiting the peculiarities of the particular problem is a very difficult and error-prone task which in many cases does not seem to pay-off.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T27 Logic in artificial intelligence

Software:

AMPL; OTTER
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bacchus, F.; van Run, P., Dynamic variable ordering in CSPs, (Proceedings of the First International Conference on Principles and Practice of Constraint Programming (CP’95). Proceedings of the First International Conference on Principles and Practice of Constraint Programming (CP’95), Cassis, France. Proceedings of the First International Conference on Principles and Practice of Constraint Programming (CP’95). Proceedings of the First International Conference on Principles and Practice of Constraint Programming (CP’95), Cassis, France, Lecture Notes in Computer Science, vol. 976 (1995), Springer), 258-275
[2] Bibel, W., Constraint satisfaction from a deductive viewpoint, Artificial Intelligence, 35, 401-413 (1988) · Zbl 0645.68112
[3] Bistarelli, S.; Codognet, P.; Rossi, F., An abstraction framework for soft constraints and its relationship with constraint propagation, (Proceedings of the Fourth International Symposium on Abstraction, Reformulation and Approximation (SARA 2000). Proceedings of the Fourth International Symposium on Abstraction, Reformulation and Approximation (SARA 2000), Horseshoe Bay, TX, USA. Proceedings of the Fourth International Symposium on Abstraction, Reformulation and Approximation (SARA 2000). Proceedings of the Fourth International Symposium on Abstraction, Reformulation and Approximation (SARA 2000), Horseshoe Bay, TX, USA, Lecture Notes in Computer Science, vol. 1864 (2000), Springer), 71-86 · Zbl 0989.68527
[4] Börger, E.; Gräedel, E.; Gurevich, Y., The Classical Decision Problem, Perspectives in Mathematical Logic (1997), Springer
[5] Brown, C. A.; Finkelstein, L.; Purdom, P. W., Backtrack searching in the presence of symmetry, (Mora, T., Proceedings of the Sixth International Conference on Applied Algebra, Algebraic Algorithms and Error Correcting codes. Proceedings of the Sixth International Conference on Applied Algebra, Algebraic Algorithms and Error Correcting codes, Rome, Italy. Proceedings of the Sixth International Conference on Applied Algebra, Algebraic Algorithms and Error Correcting codes. Proceedings of the Sixth International Conference on Applied Algebra, Algebraic Algorithms and Error Correcting codes, Rome, Italy, Lecture Notes in Computer Science, vol. 357 (1988), Springer), 99-110
[6] Cadoli, M.; Mancini, T., Automated reformulation of specifications by safe delay of constraints, Artificial Intelligence, 170, 8-9, 779-801 (2006) · Zbl 1131.68096
[7] Cadoli, M.; Mancini, T., Using a theorem prover for reasoning on constraint problems, Applied Artificial Intelligence, 21, 3 (2007), Special issue on “Best papers from AI*IA 2005”, in press
[8] Cadoli, M.; Schaerf, A., Compiling problem specifications into SAT, Artificial Intelligence, 162, 89-120 (2005) · Zbl 1132.68693
[9] Calabro, C.; Impagliazzo, R.; Kabanets, V.; Paturi, R., The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs, (Proceedings of the Eighteenth IEEE Conference on Computational Complexity (CCC 2003). Proceedings of the Eighteenth IEEE Conference on Computational Complexity (CCC 2003), Aarhus, Denmark (2003), IEEE Computer Society Press), p. 135 ff · Zbl 1135.68020
[10] Chang, C. C.; Keisler, H. J., Model Theory (1990), North-Holland · Zbl 0697.03022
[11] Cheng, B. M.W.; Choi, K. M.F.; Lee, J. H.-M.; Wu, J. C.K., Increasing constraint propagation by redundant modeling: an experience report, Constraints, 4, 2, 167-192 (1999) · Zbl 0949.68605
[12] Crawford, J. M.; Ginsberg, M. L.; Luks, E. M.; Roy, A., Symmetry-breaking predicates for search problems, (Proceedings of the Fifth International Conference on the Principles of Knowledge Representation and Reasoning (KR’96). Proceedings of the Fifth International Conference on the Principles of Knowledge Representation and Reasoning (KR’96), Cambridge, MA, USA (1996), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 148-159
[13] Crescenzi, P.; Goldman, D.; Papadimitriou, C. H.; Piccolboni, A.; Yannakakis, M., On the complexity of protein folding, Journal of Computational Biology, 5, 3, 423-466 (1998)
[14] Dechter, R., Constraint networks (survey), (Encyclopedia of Artificial Intelligence (1992), John Wiley & Sons), 276-285
[15] Ebbinghaus, H. D.; Flum, J., Finite Model Theory (1999), Springer
[16] Ellman, T., Abstraction via approximate symmetry, (Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI’93). Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI’93), Chambéry, France (1993), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 916-921
[17] Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, (Karp, R. M., Complexity of Computation (1974), American Mathematical Society), 43-74
[18] P. Flener, Towards relational modelling of combinatorial optimisation problems, in: C. Bessière (Ed.), Proceedings of the International Workshop on Modelling and Solving Problems with Constraints, in conjunction with the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI 2001), Seattle, WA, USA, 2001; P. Flener, Towards relational modelling of combinatorial optimisation problems, in: C. Bessière (Ed.), Proceedings of the International Workshop on Modelling and Solving Problems with Constraints, in conjunction with the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI 2001), Seattle, WA, USA, 2001
[19] Fourer, R.; Gay, D. M.; Kernigham, B. W., AMPL: A Modeling Language for Mathematical Programming (1993), International Thomson Publishing
[20] Freuder, E. C., Eliminating interchangeable values in Constraint Satisfaction Problems, (Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI’91). Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI’91), Anaheim, CA, USA (1991), AAAI Press/The MIT Press), 227-233
[21] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco, CA, USA · Zbl 0411.68039
[22] Giunchiglia, E.; Sebastiani, R., Applying the Davis-Putnam procedure to non-clausal formulas, (Proceedings of the Sixth Conference of the Italian Association for Artificial Intelligence (AI*IA’99). Proceedings of the Sixth Conference of the Italian Association for Artificial Intelligence (AI*IA’99), Bologna, Italy. Proceedings of the Sixth Conference of the Italian Association for Artificial Intelligence (AI*IA’99). Proceedings of the Sixth Conference of the Italian Association for Artificial Intelligence (AI*IA’99), Bologna, Italy, Lecture Notes in Artificial Intelligence, vol. 1792 (2000), Springer), 84-94 · Zbl 0961.03014
[23] Giunchiglia, F.; Walsh, T., A theory of abstraction, Artificial Intelligence, 57, 323-389 (1992) · Zbl 0762.68054
[24] Hart, W.; Istrail, S., HP benchmarks, (last accessed: end of 2004)
[25] T. Hnich, T. Walsh, Why Channel? Multiple viewpoints for branching heuristics, in: Proceedings of the Second International Workshop on Modelling and Reformulating CSPs: Towards Systematisation and Automation, in conjunction with the Ninth International Conference on Principles and Practice of Constraint Programming (CP 2003), Kinsale, Ireland, 2003; T. Hnich, T. Walsh, Why Channel? Multiple viewpoints for branching heuristics, in: Proceedings of the Second International Workshop on Modelling and Reformulating CSPs: Towards Systematisation and Automation, in conjunction with the Ninth International Conference on Principles and Practice of Constraint Programming (CP 2003), Kinsale, Ireland, 2003
[26] Kautz, H.; Selman, B., Pushing the envelope: Planning, propositional logic, and stochastic search, (Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI’96). Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI’96), Portland, OR, USA (1996), AAAI Press/The MIT Press), 1194-1201
[27] Kolaitis, P. G., Constraint satisfaction, databases, and logic, (Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI 2003). Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI 2003), Acapulco, Mexico (2003), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 1587-1595 · Zbl 0692.45001
[28] Kumar, V., Algorithms for constraint-satisfaction problems: A survey, AI Magazine, 13, 1, 32-44 (1992)
[29] Lau, K. F.; Dill, K. A., A lattice statistical mechanics model of the conformational and sequence spaces of proteins, Macromolecules, 22, 3986-3997 (1989)
[30] Lenstra, A.; Lenstra, H. W., Algorithms in number theory, (van Leeuwen, J., The Handbook of Theoretical Computer Science, vol. 1, Algorithms and Complexity (1990), The MIT Press) · Zbl 0900.68250
[31] Leone, N.; Pfeifer, G.; Faber, W.; Eiter, T.; Gottlob, G.; Perri, S.; Scarcello, F., The DLV system for knowledge representation and reasoning, ACM Transactions on Computational Logic, 7, 3, 499-562 (2006) · Zbl 1367.68308
[32] C.M. Li, Integrating equivalency reasoning into Davis-Putnam procedure, in: Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI 2000) (1), pp. 291-296; C.M. Li, Integrating equivalency reasoning into Davis-Putnam procedure, in: Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI 2000) (1), pp. 291-296
[33] T. Mancini, Declarative constraint modelling and specification-level reasoning, PhD thesis, Università degli Studi di Roma “La Sapienza”, Roma, Italy, March 2005; T. Mancini, Declarative constraint modelling and specification-level reasoning, PhD thesis, Università degli Studi di Roma “La Sapienza”, Roma, Italy, March 2005
[34] Mancini, T.; Cadoli, M., Detecting and breaking symmetries by reasoning on problem specifications, (Proceedings of the Sixth International Symposium on Abstraction, Reformulation and Approximation (SARA 2005). Proceedings of the Sixth International Symposium on Abstraction, Reformulation and Approximation (SARA 2005), Airth Castle, Scotland, UK. Proceedings of the Sixth International Symposium on Abstraction, Reformulation and Approximation (SARA 2005). Proceedings of the Sixth International Symposium on Abstraction, Reformulation and Approximation (SARA 2005), Airth Castle, Scotland, UK, Lecture Notes in Artificial Intelligence, vol. 3607 (2005), Springer), 165-181
[35] McCune, W., Otter 3.3 reference manual, Technical Report ANL/MCS-TM-263, Argonne National Laboratory, Mathematics and Computer Science Division, August 2003. Available at
[36] Niemelä, I., Logic programs with stable model semantics as a constraint programming paradigm, Annals of Mathematics and Artificial Intelligence, 25, 3-4, 241-273 (1999) · Zbl 0940.68018
[37] Nilsson, N. J., Principles of Artificial Intelligence (1980), Tioga Publishing Co. · Zbl 0422.68039
[38] Papadimitriou, C. H., Computational Complexity (1994), Addison Wesley Publishing Company: Addison Wesley Publishing Company Reading, MA · Zbl 0557.68033
[39] Prosser, P., The dynamics of dynamic variable ordering heuristics, (Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP’98). Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP’98), Pisa, Italy. Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP’98). Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP’98), Pisa, Italy, Lecture Notes in Computer Science, vol. 1520 (1998), Springer), 17-23
[40] T. Pyhälä, Factoring benchmarks for SAT solvers, Technical report, Helsinki University of Technology, 2004; T. Pyhälä, Factoring benchmarks for SAT solvers, Technical report, Helsinki University of Technology, 2004
[41] B.M. Smith, K. Stergiou, T. Walsh, Using auxiliary variables and implied constraints to model non-binary problems, in: Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI 2000) (1), pp. 182-187; B.M. Smith, K. Stergiou, T. Walsh, Using auxiliary variables and implied constraints to model non-binary problems, in: Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI 2000) (1), pp. 182-187
[42] Valiant, L. G.; Vijay, V. V.; Vazirani, V., NP is as easy as detecting unique solutions, Theoretical Computer Science, 47, 3, 85-93 (1986) · Zbl 0621.68030
[43] Van Hentenryck, P., The OPL Optimization Programming Language (1999), The MIT Press
[44] Walsh, T., Permutation problems and channelling constraints, (Nieuwenhuis, R.; Voronkov, A., Proceedings of the Eighth International Conference on Logic for Programming and Automated Reasoning (LPAR 2001). Proceedings of the Eighth International Conference on Logic for Programming and Automated Reasoning (LPAR 2001), Havana, Cuba. Proceedings of the Eighth International Conference on Logic for Programming and Automated Reasoning (LPAR 2001). Proceedings of the Eighth International Conference on Logic for Programming and Automated Reasoning (LPAR 2001), Havana, Cuba, Lecture Notes in Computer Science, vol. 2250 (2001), Springer), 377-391 · Zbl 1273.68365
[45] Warren, D. H.D., Extract from Kluzniak and Szapowicz APIC studies in data processing, no. 24, 1974, (Readings in Planning (1990), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 140-153
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.