Abstract
In this paper 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 modelling choices, e.g., to provide multiple viewpoints of the search space in order to increase propagation. In either way, the recognition of dependencies greatly helps solvers, letting them avoid spending search on unfruitful branches, while maintaining the highest degree of declarativeness. By modelling constraint problem specifications as second-order formulae, we provide a characterization of functional dependencies in terms of semantic properties of first-order ones. Additionally, we show how suitable search procedures can be automatically synthesized in order to exploit recognized dependencies. We present opl examples of various problems, from bio-informatics, planning and resource allocation fields, and show how in many cases opl greatly benefits from the addition of such search procedures.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brown, C.A., Finkelstein, L., Purdom, P.W.: Backtrack searching in the presence of symmetry. In: Mora, T. (ed.) AAECC 1988. LNCS, vol. 357, pp. 99–110. Springer, Heidelberg (1989)
Cadoli, M., Mancini, T.: Detecting and breaking symmetries on specifications. In: Proc. of the CP 2003 Int. Workshop on Symmetry in CSPs, pp. 13–26 (2003)
Cadoli, M., Mancini, T.: Automated reformulation of specifications by safe delay of constraints. In: Proc. of KR 2004, pp. 388–398. AAAI Press, Menlo Park (2004)
Cadoli, M., Mancini, T.: Using a theorem prover for reasoning on constraint problems. In: Proc. of the ETAPS 2004 CP+CV Int. Workshop, pp. 17–31 (2004)
Cadoli, M., Schaerf, A.: Compiling problem specifications into SAT. In: Sands, D. (ed.) ESOP 2001. LNCS, vol. 2028, pp. 387–401. Springer, Heidelberg (2001)
Chang, C.C., Keisler, H.J.: Model Theory, 3rd edn. North-Holland, Amsterdam (1990)
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)
Crawford, J.M., Ginsberg, M.L., Luks, E.M., Roy, A.: Symmetry-breaking predicates for search problems. In: Proc. of KR 1996, pp. 148–159 (1996)
Crescenzi, P., Goldman, D., Papadimitriou, C.H., Piccolboni, A., Yannakakis, M.: On the complexity of protein folding. J. of Comp. Biology 5(3), 423–466 (1998)
Dechter, R.: Constraint networks (survey). In: Encyclopedia of Artificial Intelligence, 2nd edn., pp. 276–285. John Wiley & Sons, Inc., Chichester (1992)
Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Springer, Heidelberg (1999)
Eiter, T., Leone, N., Mateis, C., Pfeifer, G., Scarcello, F.: The KR system dlv: Progress report, Comparisons and Benchmarks. In: Proc. of KR 1998, pp. 406–417 (1998)
Fagin, R.: Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. In: Karp, R.M. (ed.) Complexity of Computation, pp. 43–74. AMS (1974)
Fourer, R., Gay, D.M., Kernigham, B.W.: AMPL: A Modeling Language for Mathematical Programming. International Thomson Publishing (1993)
Garey, M.R., Johnson, D.S.: Computers and Intractability—A guide to NPcompleteness. W.H. Freeman and Company, San Francisco (1979)
Giunchiglia, E., Sebastiani, R.: Applying the davis-putnam procedure to non-clausal formulas. In: Lamma, E., Mello, P. (eds.) AI*IA 1999. LNCS (LNAI), vol. 1792, pp. 84–94. Springer, Heidelberg (2000)
Hart, W., Istrail, S.: HP Benchmarks, Available at http://www.cs.sandia.gov/tech_reports/compbio/tortilla-hp-benchmarks.html
Hnich, T., Walsh, T.: Why Channel? Multiple viewpoints for branching heuristics. In: Proc. of the CP 2003 Int. Workshop on Modelling and Reformulating CSPs: Towards Systematisation and Automation (2003)
Kautz, H., Selman, B.: Pushing the envelope: Planning, propositional logic, and stochastic search. In: Proc. of AAAI 1996, pp. 1194–1201 (1996)
Lau, K.F., Dill, K.A.: A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules 22, 3986–3997 (1989)
Li, C.M.: Integrating equivalency reasoning into Davis-Putnam procedure. In: Proc. of AAAI 2000, AAAI/MIT Press (2000)
Niemelä, I.: Logic programs with stable model semantics as a constraint programming paradigm. Ann. of Mathematics and Artificial Intelligence 25(3,4), 241–273 (1999)
Nilsson, N.J.: Principles of Artificial Intelligence. Tioga Publishing Co. (1980)
Smith, B.M., Stergiou, K., Walsh, T.: Using auxiliary variables and implied constraints to model non-binary problems. In: Proc. of AAAI 2000, pp. 182–187 (2000)
Van Hentenryck, P.: The OPL Optimization Programming Language. The MIT Press, Cambridge (1999)
Walsh, T.: Permutation Problems and Channelling Constraints. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS (LNAI), vol. 2250, pp. 377–391. Springer, Heidelberg (2001)
Warren, D.H.D.: Extract from Kluzniak and Szapowicz APIC studies in data processing, no. 24, 1974. In: Readings in Planning, pp. 140–153. Morgan Kaufman, San Francisco (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cadoli, M., Mancini, T. (2004). Exploiting Functional Dependencies in Declarative Problem Specifications. In: Alferes, J.J., Leite, J. (eds) Logics in Artificial Intelligence. JELIA 2004. Lecture Notes in Computer Science(), vol 3229. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30227-8_52
Download citation
DOI: https://doi.org/10.1007/978-3-540-30227-8_52
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23242-1
Online ISBN: 978-3-540-30227-8
eBook Packages: Springer Book Archive