Teaching Archives Home Contact





Summer 2006

Constraint Programming and Applications



Find out more about the class here








Constraints? Content Assignments Exams/Quizzes Top

Constraints? Constraint programming?      back to menu      back to top

A constraint is simply a relation between variables. Each variable has a corresponding domain of possible values. The constraint restricts the possible (allowed) values the variables can take. Constraint programming is a tool (paradigm) for declarative description and effective solving of combinatorial optimization problems. Constraint programming is actually the study of computational systems based on constraints.
It was recently recognized by the Association for Computing Machinery as one of the strategic directions in computer research.

Why constraints?

Because constraints arise in most areas of human endeavor (such as the sum of the angles of a triangle is 180 degrees), and have been successfully applied to numerous domains (computer graphics, natural language processing, database systems, operations research problems, business applications, electrical engineering, circuit design, bio-informatics, etc.).
Constraint technology is more and more used in companies such as: British Airways, HongKong International Terminals, Ericsson, etc.

The range of possible applications is very wide, and encompasses:
  • time-tabling: s.a. workforce management, course scheduling
  • planning and scheduling: s.a. transport planning
  • resource allocation: s.a. forest treatment scheduling, airport counter allocation
  • analysis and synthesis of analogue and digital circuit
  • option trading analysis
  • DNA sequencing
  • chemical hypothetical reasoning
  • network configuration

    Early during the spring semester, I will make a presentation of the course content. But in any case, would you have any question, please feel free to send me an email, or stop by my office (202C in the Computer Science Building).
    Example of need for technology as a bias for computational power

    Most problems that constraint programming tackle belong to the group that conventional programming techniques find the hardest. Time needed to solve such problems using unconstrained search increases exponentially with the problem size.

    Consider the simple problem of harbour which needs to schedule the loading and unloading of 10 ships unsing only 5 berths. You can solve this problem by trying all permutations of ships in berths, calculating the cost of each alternative and selecting the optimal schedule. This means exploring 5^{10} (about 10 million) alternatives in the worst case. Assuming that your computer can try an alternative every millisecond, then the whole problem is solved in about 3 hours.

    A decade later, the business has been good and the harbour has expanded to 10 berths and 20 ships. Now, finding the optimal schedule using the same method means trying 10^{20} alternatives, which will take more than 3000 million years on the same computer. Even a thousand times faster accelerator card does not help there.

    Fortunately, one does not need to explore all alternatives. There are many criteria for choosing the berth for a particular ship: for example, some berths are too small for some ships and it is not possible to load or unload two ships in the same berth at the same time, etc. By embracing these constraints, the search space reduces dramatically and it makes the problem tractable.

    Also, in many real-life problems, the optimal solution is not necessarily required and a near to optimal solution is enough in many cases. For example, it is possible to break up the harbour into two parts: each with 5 berths and 10 ships, and solve this split problem in 6 hours using the above "brute force" method.
    Content of the course      back to menu      back to top

    The course will be a ?-week course, meeting every ??. The topics covered in the class include:

  • Introduction to constraints: definition, use, history
  • Two kinds of constraints: discrete and continuous. Why? What are their special features and special needs?
  • Constraint Satisfaction
  • Constraint Solving
  • How to solve constraints? search methods, constraint consistency techniques, constraint propagation, pruning the search space, etc.
  • Optimization
  • Soft constraints: when requirements are no longer strict.
  • Applications

    A lot of emphasis will be put on applications, practical use of constraints in real-life applications.
    Assignments      back to menu      back to top

  • Projects: all students have to work on a project related to constraint programming.
         They have to turn in a report by July, 21st, and to do an in-class presentation during the last week of classes.

  • Mid-term exam: test a real solver, due on July, 18th
         archive of the solver here, readme file here, directions for the midterm here

  • Homework assignments:










    ** Fragments of the tutorial of Roman Bartak on Constraint Propagation and Backtracking-based Search have been used to document this page.
    Martine Ceberio
    Last modified: Wed Jul 5 23:56:21 MDT 2006