Advertisement

Compiling High-Level Type Constructors in Constraint Programming

  • Pierre Flener
  • Brahim Hnich
  • Zeynep Kiziltan
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 1990)

Abstract

We propose high-level type constructors for constraint programming languages, so that constraint satisfaction problems can be modelled in very expressive ways. We design a practical set constraint language, called esra, by incorporating these ideas on top of opl. A set of rewrite rules achieves compilation from esra into opl, yielding programs that are often very similar to those that a human opl modeller would (have to) write anyway, so that there is no loss in solving efficiency.

Keywords

Constraint Programming Constraint Satisfaction Problem Supply Cost Optimisation Part Travel Salesperson Problem 
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.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    F. Ambert, B. Legeard, and E. Legros. Programmation en logique avec contraintes sur ensembles et multi-ensembles héréditairement finis. Techniques et Sciences Informatiques 15(3):297–328, 1996.Google Scholar
  2. 2.
    L. Blaine, L. Gilham, J. Liu, D.R. Smith, and S. Westfold. PlanWare: Domainspeci fic synthesis of high-performance schedulers. In Proc. of ASE’98, pp. 270–279. IEEE Computer Society Press, 1998.Google Scholar
  3. 3.
    M. Cadoli, L. Palopoli, A. Schaerf, and D. Vasile. NP-SPEC: An executable specification language for solving all problems in NP. In: G. Gupta (ed), Proc. of PADL’99, pp. 16–30. LNCS 1551. Springer-Verlag, 1999.Google Scholar
  4. 4.
    A. Dovier, C. Piazza, E. Pontelli, and G. Rossi. On the representation and management of finite sets in CLP-languages. In: J. Jaffar (ed), Proc. of JICSLP’98, pp. 40–54. The MIT Press, 1998.Google Scholar
  5. 5.
    P. Flener, H. Zidoum, and B. Hnich. Schema-guided synthesis of constraint logic programs. In Proc. of ASE’98, pp. 168–176. IEEE Computer Society Press, 1998.Google Scholar
  6. 6.
    P. Flener and B. Hnich. The Syntax and Semantics of ESRA. ASTRA Internal Report. Available via http://www.dis.uu.se/~pierref/astra/.
  7. 7.
    P. Flener, B. Hnich, and Z. Kiziltan. A meta-heuristic for subset problems. In: I.V. Ramakrishnan (ed), Proc. of PADL’01. LNCS, this volume. Springer-Verlag, 2001.Google Scholar
  8. 8.
    C. Gervet. Interval propagation to reason about sets: Definition and implementation of a practical language. Constraints 1(3):191–244, 1997.zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    B. Hnich and P. Flener. High-level reformulation of constraint programs. Submitted for review. Available via http://www.dis.uu.se/pierref/astra/.
  10. 10.
    Z. Kiziltan, P. Flener, and B. Hnich. A labelling heuristic for subset problems. Submitted for review. Available via http://www.dis.uu.se/pierref/astra/.
  11. 11.
    T. Müller. Solving set partitioning problems with constraint programming. In Proc. of PAPPACT’98, pp. 313–332. The Practical Application Company, 1998.Google Scholar
  12. 12.
    D.R. Smith. The structure and design of global search algorithms. Tech. Rep. KES.U.87.12, Kestrel Institute, 1988.Google Scholar
  13. 13.
    D.R. Smith. KIDS: A semi-automatic program development system. IEEE Trans. on Software Engineering 16(9):1024–1043, 1990.CrossRefGoogle Scholar
  14. 14.
    D.R. Smith. Toward a classification approach to design. In Proc. of AMAST’96, pp. 62–84. LNCS 1101. Springer-Verlag, 1996.Google Scholar
  15. 15.
    E. Tsang, P. Mills, R. Williams, J. Ford, and J. Borrett. A computer-aided constraint programming system. In: J. Little (ed), Proc. of PACLP’99, pp. 81–93. The Practical Application Company, 1999.Google Scholar
  16. 16.
    P. Van Hentenryck. The opl Optimization Programming Language. The MIT Press, 1999.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2001

Authors and Affiliations

  • Pierre Flener
    • 1
  • Brahim Hnich
    • 1
  • Zeynep Kiziltan
    • 1
  1. 1.Computer Science DivisionDepartment of Information ScienceUppsala UniversityUppsalaSweden

Personalised recommendations