Show The Graduate Center Menu

Constraint Programming



Many complex systems, ranging from social, industrial, economics, financial, educational, to military, require that we obtain high-quality solutions to combinatorial problems. Linear programming and its extensions developed in operations research once formed the primary paradigm for solving combinatorial problems. During the last three decades, a plethora of paradigms have been developed for combinatorial problems, including constraint programming (CP), propositional satisfiability testing (SAT), satisfiability modulo theories (SMT), answer set programming (ASP), tabled logic programming, and heuristic search planners. 


Course Description

Constraint programming is a powerful paradigm for solving combinatorial search problems, which draws on a wide range of techniques from artificial intelligence, computer science, databases, programming languages, and operations research. Constraint programming is currently applied with success to many domains, such as scheduling, planning, vehicle routing, configuration, networks, and bioinformatics. This course covers the algorithms, language systems and tools, and application examples of constraint programming. It also covers related problem domains, including dynamic programming, planning, and operations research.


Topic List


1. An overview of constraint programming


2. Constraint solving, linear programming, dynamic programming, and planning in Picat


3. Consistency and propagation algorithms (AC-3, AC-4, AC-5 and other algorithms)


4. The Simplex algorithm and integer programming algorithms


5. SAT solving techniques and SMT


6. Application examples 


7. Constraint programming systems (Picat, Google or-tools, MiniZinc, etc.)




Handbook of Constraint Programming, eds. Francesca Rossi, Peter van Beek, and Toby Walsh, 2006


Handbook of Satisfiability, eds. Armin Biere, Marijn Heule, Hans van Maaren and Toby Walsh, 2009.


Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, 2009.


Constraint Solving and Planning with Picat, Neng-Fa Zhou, Hakan Kjellerstrand, and Jonathan Fruhman, 2015.