[go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

A microkernel architecture for constraint programming

  • Published:
Constraints Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

This paper presents a microkernel architecture for constraint programming organized around a small number of core functionalities and minimal interfaces. The architecture contrasts with the monolithic nature of many implementations. With this design, variables, domains and constraints all remain external to the microkernel which isolates the propagation logic and event protocols from the modeling constructions. The Objective-CP search blends the control primitives of the host language with search combinators in a completely transparent and fully compositional way, delivering a natural search procedure in which one can use native constructions and tools such as debuggers. Empirical results indicate that the software engineering benefits are not incompatible with runtime efficiency.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26
Fig. 27
Fig. 28

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. The data reading part of the program is omitted for brevity.

  2. It is given in lambda-calculus notation [2] for simplicity.

  3. An alternative implementation can easily store in Q P objects representing pairs of the form 〈f i , e〉 and delegate to a method of the pair the task to evaluate f i (e) when the pair is dequeued from Q P . To a large extent, this is an implementation detail.

  4. The source code of all the benchmarks –Comet, Choco, and Objective-CP– can be found at http://ash.engr.uconn.edu/~ldm/wordpress/?page_id=8.

  5. Instruments is Apple’s version of the Sun MicroSytem tool DTrace.

  6. There are some minor differences. For instance, in the All-Interval series, Choco encodes the distance between two variables with a global distance constraint whereas Objective-CP uses an arithmetic expression for |x−y| = z and therefore yields two constraints for that encoding.

References

  1. Aggoun, A., & Beldiceanu, N. (1991). An overview of the CHIP compiler. In The 8th International Conference on Logic Programming (ICLP–91). Paris: The MIT Press.

    Google Scholar 

  2. Barendregt, H.P. (1984). The lambda calculus – its syntax and semantics, volume 103 of studies in logic and the foundations of mathematics. North-Holland.

  3. Benhamou, F., Goualard, F., Granvilliers, L., & Puget, J.-F. (1999). Revising hull and box consistency. In ICLP (pp. 230–244).

  4. Boussemart, F., Hemery, F., & Lecoutre, C. (2004). Revision ordering heuristics for the constraint satisfaction problem. In First international workshop: constraint propagation and implementation.

  5. Colmerauer, A. (1990). An introduction to prolog III. Communications of the ACM, 28(4), 412–418.

    Google Scholar 

  6. Dincbas, M., Van Hentenryck, P., Simonis, H., Aggoun, A., Graf, T., & Berthier, F. (1988). The constraint logic programming language CHIP. In Proceedings of the international conference on 5th generation computer systems. Tokyo.

  7. Dincbas, M., Van Hentenryck, P., Simonis, H., Aggoun, A., Graf, T., & Berthier, F. (1988). The constraint logic programming language CHIP. In Proceedings of the international conference on 5th-generation computer systems. Tokyo.

  8. Dooms, G., Hentenryck, P., & Michel, L. (2009). Model-driven visualizations of constraint-based local search. Constraints, 14, 294–324.

    Article  MATH  Google Scholar 

  9. Fontaine, D., Michel, L., & Van Hentenryck, P. (2013). Model combinators for hybrid optimization. In Schulte, C. (Ed.), Proceedings of the 19th international conference on principles and practice of constraint programming (Vol. 8124, pp. 299–314). Springer Berlin Heidelberg.

  10. Fontaine, D., & Michel, L. (2012). A high level language for solver independent model manipulation and heneration of hybrid solvers. In Beldiceanu, N., Jussien, N., & Pinson, E. (Eds.), CPAIOR, volume 7298 of lecture notes in computer science (pp. 180–194). Springer.

  11. Gamma, E., Helm, R., Johnson, R., & John, V. (1994). Design patterns: elements of reusable object-oriented software, 1st Edn. Addison-Wesley Professional.

  12. Gent, I.a.n.P., Jefferson, C., & Miguel, I. (2006). Minion: a fast scalable constraint solver. In Proceedings of ECAI 2006, Riva del Garda (pp. 98–102). IOS Press.

  13. Gent, I.P., Jefferson, C., & Miguel, I. (2006). Watched literals for constraint propagation in Minion. In Benhamou, F. (Ed.), Principles and practice of constraint programming - CP 2006, volume 4204 of lecture notes in computer science (pp. 182–197). Springer Berlin Heidelberg.

  14. Helsgaun, K. (1995). CBack: a simple tool for backtrack programming in C. Software Practice Experimental, 25(8), 905–934.

    Article  Google Scholar 

  15. Hentenryck, P.V., & Michel, L. (2013). The objective-CP optimization system. In Schulte, C. (Ed.), Principles and practice of constraint programming - 19th international conference, CP 2013, Uppsala, Sweden, September 16–20 proceedings, volume 8124 of lecture notes in computer science (pp. 8–29). Springer.

  16. Hooker, J.N. (2000). Logic-based methods for optimization: combining optimization and constraint satisfaction. Wiley.

  17. IBM. Ilog CONCERT technology. http://eaton.math.rpi.edu/cplex90html/refconcert/index.html.

  18. Ilog Solver 4.4 (1998). Reference Manual. Ilog SA, Gentilly, France.

  19. Jaffar, J., Michaylov, S., Stuckey, P.J., & Yap, R. (1992). The CLP (R) language and system. ACM Transactions on Programming Languages and Systems, 14(3), 339–395.

    Article  Google Scholar 

  20. Jussien, N., Rochart, G., & Lorca, X. (2008). The Choco constraint programming solver. In CPAIOR’08 Workshop on Open-Source Software for Integer and Contraint Programming (OSSICP’08). OSSICP.

  21. Kuchcinski, K., & Szymanek, R. (2012). Jacop library user’s guide technical report.

  22. Laburthe, F., & Caseau, Y. (1998). SALSA: a language for search algorithms. In Fourth international conference on the principles and practice of constraint programming (CP’98). Italy.

  23. Lagerkvist, M.Z., & Schulte, C. (2009). Propagator groups. In Gent, I.P. (Ed.), CP, volume 5732 of lecture notes in computer science (pp. 524–538). Springer.

  24. Michel, L., See, A., & Van Hentenryck, P. (2006). High-Level Nondeterministic Abstractions in C++. In 12th International conference on principles and practice of constraint programming. (CP’06), lecture notes in computer science. Nantes.

  25. Michel, L., See, A., & Van Hentenryck, P. (2009). Transparent parallelization of constraint programming. INFORMS Journal on Computing, 21(3), 363–382.

    Article  MATH  Google Scholar 

  26. Michel, L., & Van Hentenryck, P. (2013). Domain views for constraint programming. In TRICS13: Techniques foR Implementing Constraint programming Systems.

  27. Michel, L., See, A., & Hentenryck, P.V. (2009). Parallel and distributed local search in COMET. Computers & Operations Research, 36(8), 2357–2375.

    Article  MATH  Google Scholar 

  28. Michel, L., & Hentenryck, P.V. (2012). Activity-based search for black-box constraint programming solvers. In Beldiceanu, N., Jussien, N., & Pinson, R. (Eds.), Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, volume 7298 of lecture notes in computer science (pp. 228–243). Springer Berlin Heidelberg.

  29. Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., & Chaff, S.M. (2001). Engineering an efficient sat solver. In Proceedings of the 38th annual Design Automation Conference, DAC’01 (pp. 530–535). New York: ACM.

    Google Scholar 

  30. Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., & Tack, G. (2007). Minizinc: towards a standard cp modelling language. In Proceedings of the 13th international conference on principles and practice of constraint programming (pp. 529–543). Springer.

  31. Prud’homme, C., Fages, J.-G., & Lorca, X. (2014). Choco3 Documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S.

  32. Prud’homme, C., Lorca, X., Douence, R., & Jussien, N. (2013). Propagation engine prototyping with a dsl. In COSpeL: The first workshop on domain specific languages in combinatorial optimization.

  33. Refalo, P. (2000). Linear formulation of constraint programming models and hybrid solvers. In Sixth international conference on the principles and practice of constraint programming (CP’00) (pp. 369–383). Singapore.

  34. Refalo, P. (2004). Impact-based search strategies for constraint programming. In Wallace, M. (Ed.), CP, volume 3258 of lecture Notes in computer science (pp. 557–571). Springer.

  35. Schrijvers, T., Tack, G., Wuille, P., Samulowitz, H., & Stuckey, P.J. (2013). Search combinators. Constraints, 18(2), 269–305.

    Article  MathSciNet  MATH  Google Scholar 

  36. Schulte, C., Tack, G., & Lagerkvist, M. (2009). Gecode the generic constraint development environment.

  37. Schulte, C., & Stuckey, P.J. (2008). Efficient constraint propagation engines. ACM Transactions on Programming Languages and Systems, 31(1), 2:1–2:43.

    Article  Google Scholar 

  38. Schulte, C., & Tack, G. (2010). Implementing efficient propagation control. In TRICS 2010, Third workshop on techniques for implementing constraint programming systems.

  39. Schulte, C., & Tack, G. (2013). View-based propagator derivation. Constraints, 18(1), 75–107.

    Article  MathSciNet  MATH  Google Scholar 

  40. Smolka, G. (1995). The Oz programming model. In Leeuwen, J.V. (Ed.), Computer science today (No. 1000, pp. 324–343). LNCS, Springer Verlag.

  41. Van Hentenryck, P. (1989). Constraint satisfaction in logic programming. Cambridge: Logic Programming Series, The MIT Press.

  42. Van Hentenryck, P. (1989). Parallel constraint satisfaction in logic programming: preliminary results of CHIP within PEPSys. In Sixth international conference on logic programming. Lisbon.

  43. Van Hentenryck, P. (1991). The CLP language CHIP: constraint solving and applications. In COMPCON–91. San Francisco.

  44. Van Hentenryck, P. (1999). The OPL optimization programming language. Cambridge, Mass: The MIT Press.

  45. Van Hentenryck, P. (2005). Constraint-based local search. Cambridge, Mass: The MIT Press.

    MATH  Google Scholar 

  46. Van Hentenryck, P., & Michel, L. (2005). Nondeterministic control for hybrid search. In Proceedings of the 2nd international conference on the integration of AI and OR techniques in constraint programming for combinatorial optimisation problems (CP-AI-OR’04). Prague.

  47. Van Hentenryck, P., & Michel, L. (2009). Constraint-based local search. Cambridge, Mass: The MIT Press.

    MATH  Google Scholar 

  48. Van Hentenryck, P., Michel, L., & Deville, Y. (1997). Numerica: a modeling language for global optimization. Cambridge, Mass: The MIT Press.

    Google Scholar 

  49. Van Hentenryck, P., Saraswat, V., & Deville, Y. (1995). The design, implementation, and evaluation of the constraint language cc(FD). In Constraint programming: basics and trends. Springer Verlag.

Download references

Acknowledgments

We would like to express our gratitude to Thibaut Feydy and Peter Stuckey for many interesting discussions. In particular, Thibaut encouraged us to eliminate the explicit handling of failures in propagators. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.

Author information

Authors and Affiliations

  1. University of Connecticut, Storrs, CT, 06269-2155, USA

    L. Michel

  2. University of Michigan, 1205 Beal Avenue, Ann Arbor, MI, 48109-2117, USA

    P. Van Hentenryck

Authors
  1. L. Michel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. Van Hentenryck
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to L. Michel.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Michel, L., Van Hentenryck, P. A microkernel architecture for constraint programming. Constraints 22, 107–151 (2017). https://doi.org/10.1007/s10601-016-9242-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10601-016-9242-1

Keywords