Constraint Processing:
From Algorithms to Applications

by Roman Barták

Constraint Programming (CP) is a technology for solving combinatorial optimisation problems in areas such as planning, scheduling, and assignment problems, circuit design, network management and configuration, interactive graphics, molecular biology etc. A user specifies the problem in a declarative way by using decision variables and constraints restricting allowed combinations of values to be assigned to the variables. Then, the underlying general solving mechanism will find an instantiation of variables satisfying the constraints.

Constraint Programming is a powerful problem-solving technology but it is also hard to use; it requires deeper knowledge of how constraint satisfaction works and how the problem should be modelled to be solvable efficiently. The tutorial focuses on these two aspects of CP. First, the tutorial will clarify the traditional misunderstanding that CP is equivalent to enumeration and it will present CP as a technology integrating search and inference. Second, the tutorial will explain why different models of the same problem may lead to dramatically different performance and it will give the audience some guidelines how to design efficiently solvable models.

The tutorial is targeted to a broad research and development community, in particular to those who solve problems of combinatorial nature (scheduling, configuration, assignment, routing etc.). The audience will take away a basic understanding of how constraints work, tips and tricks for efficient constraint modelling, and practical information about writing “constraint-based programs”. No specific prior knowledge is required beyond the basic understanding of logic and algorithms.

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