Constraint (Logic) Programming

by Roman Barták

Constraint Logic Programming (CLP) is a natural extension of Logic Programming, where unification is generalized to constraint satisfaction. Hence Prolog can be seen as one of the most suitable host languages for constraint programming.

This tutorial explains mainstream constraint satisfaction techniques and shows how they influence problem modeling in the context of logic programming. The core notions of constraint consistency, in particular arc consistency will be explained together with major consistency algorithms. The notion of a global constraint will also be explained and demonstrated with examples. After that we will show how consistency techniques can be integrated with search to obtain a complete constraint solver. In the second part, the tutorial will focus on modeling examples. It will show how to model problems using constraint logic programming. We will discuss some modeling rules and show how to improve efficiency of constraint programs.

The tutorial is targeted mainly to students and researchers interested in declarative programming techniques for solving combinatorial optimization problems such as planning, scheduling, routing, configuration etc. No prior knowledge of constraint programming is required; the tutorial only assumes basic understanding of Prolog programming.

About the Author

Roman Barták is a professor at Charles University, Prague (Czech Republic). He leads Constraint Satisfaction and Optimization Research Group that performs basic and applied research in the areas of satisfiability and discrete optimization problems. His work focuses on techniques of constraint satisfaction and their application to planning and scheduling. The research results are used in products of IBM/ILOG and Entellexi. Prof. Barták is author of On-line Guide to Constraint Programming.

Download slides | Contact author | On-line guide | CP course