Abstract
To use constraint technology to solve a problem, the solutions to the problem must first be characterised, or modelled, by a set of constraints that they must satisfy. A significant part of the modelling process can be characterised as refinement, the process of generating a concrete model from an abstract specification of the problem. Expert modellers also identify and perform transformations that can dramatically reduce the effort needed to solve the problem by systematic search. Through a case study of modelling a simplified version of the SONET fibre-optic communication problem, this paper examines the processes of refinement and transformation, and especially the interaction between the two.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abbas, A., Tsang, E.P.K.: Toward a general language for the specification of constraint satisfaction problems. In: Proc. Constraint Programming, Artificial Intelligence and Operations Research (CP-AI-OR) Wshop (2001)
Borrett, J.E.: Formulation selection for constraint satisfaction problem: a heuristic approach. PhD Thesis, Dept. of Computer Science, University of Essex, UK (1998)
Borrett, J.E., Tsang, E.P.K.: A context for constraint satisfaction problem formulation selection. Constraints 6(4), 299–327 (2001)
Bradwell, R., Ford, J., Mills, P., Tsang, E.P.K., Williams, R.: An overview of the CACP project: modelling and solving constraint satisfaction/optimisation problems with minimal expert intervention. In: Proc. Wshop. on Analysis and Visualization of Constraint Programs & Solvers (2000)
Bundy, A.: A Science of Reasoning. In: Lassez, J.-L., Plotkin, G. (eds.) Computational Logic: Essays in Honor of Alan Robinson, pp. 178–198 (1991)
Cadoli, M., Schaerf, A.: Compiling program specifications into SAT. In: Sands, D. (ed.) ESOP 2001. LNCS, vol. 2028, p. 387. Springer, Heidelberg (2001)
Cadoli, M., Palopoli, L., Schaerf, A., Vasile, D.: NP-SPEC: An executable specification language for solving all problems in NP. In: Gupta, G. (ed.) PADL 1999. LNCS, vol. 1551, pp. 16–30. Springer, Heidelberg (1999)
Flener, P., Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Matrix Modelling: Exploiting Common Patterns in Constraint Programming. In: Proc. Int. Wshop on Reformulating CSPs (2002)
Flener, P., Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Pearson, J., Walsh, T.: Breaking Row and Column Symmetries in Matrix Models. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, p. 462. Springer, Heidelberg (2002)
Flener, P., Pearson, J., Agren, M.: Introducing ESRA, a relational language for modelling combinatorial problems. In: Bruynooghe, M. (ed.) LOPSTR 2004. LNCS, vol. 3018, pp. 214–232. Springer, Heidelberg (2004)
Frisch, A.M., Hnich, B., Kiziltan, Z., Miguel, I., Walsh, T.: Global Constraints for Lexicographic Orderings. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, p. 93. Springer, Heidelberg (2002)
Frisch, A.M., Jefferson, C., MartÃnez-Hernández, B., Miguel, I.: The Rules of Constraint Modelling. In: Proc. 19th Int. Joint Conf. on AI (2005)
Frisch, A.M., Jefferson, C., Miguel, I.: Symmetry Breaking as a Prelude to Implied Constraints: A Constraint Modelling Pattern. In: Proc. 16th Euro. Conf. on AI, pp. 171–175 (2004)
Frisch, A.M., Miguel, I., Walsh, T.: Cgrass: A System for Transforming Constraint Satisfaction Problems. In: O’Sullivan, B. (ed.) CologNet 2002. LNCS (LNAI), vol. 2627, pp. 23–26. Springer, Heidelberg (2003)
Gent, I.P., Smith, B.M.: Symmetry Breaking During Search in Constraint Programming. In: Proc. European Conf. on AI, pp. 599–603 (2000)
Giunchiglia, F., Walsh, T.: A Theory of Abstraction. Artificial Intelligence 56(2–3), 323–390 (1992)
Hnich, B.: Function Variables for Constraint Programming. PhD Thesis, University of Uppsala (2003)
Hnich, B., Smith, B.M., Walsh, T.: Models of Permutation and Injection Problems. Journal of Artificial Intelligence Research 21 (2004)
Lauriere, J.-L.: A language and a program for stating and solving combinatorial problems. Artificial Intelligence 10(1), 29–127 (1978)
Mackworth, A.K.: Constraint Satisfaction Problems. In: Encyclopedia of AI, pp. 285–293 (1992)
Mills, P., Tsang, E.P.K., Williams, R., Ford, J., Borrett, J.: EaCL 1.5: An Easy abstract Constraint optimisation Programming Language. TR CSM-324, University of Essex (1999)
Sherali, H.D., Smith, J.C.: Improving Discrete Model Representations via Symmetry Considerations. Management Science 47, 1396–1407 (2001)
Smith, B.M.: Symmetry and Search in a Network Design Problem. In: Barták, R., Milano, M. (eds.) CPAIOR 2005. LNCS, vol. 3524, pp. 336–350. Springer, Heidelberg (2005)
Smith, D.R.: The structure and design of global search algorithms. TR KES.U.87.12, Kestrel Institute (1988)
Smith, B.M., Stergiou, K., Walsh, T.: Modelling the Golomb Ruler Problem. In: Proc. IJCAI 1999 Wshop on Non-Binary Constraints. Int. Joint Conf. on AI (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Frisch, A.M., Hnich, B., Miguel, I., Smith, B.M., Walsh, T. (2005). Transforming and Refining Abstract Constraint Specifications. In: Zucker, JD., Saitta, L. (eds) Abstraction, Reformulation and Approximation. SARA 2005. Lecture Notes in Computer Science(), vol 3607. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11527862_6
Download citation
DOI: https://doi.org/10.1007/11527862_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27872-6
Online ISBN: 978-3-540-31882-8
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.