Constraint Programming

--- Results of the CP exam from 3th February ---

The results of the final exam are online. You can see your grade in the LSF system. The exam review will take place in the beginning of the next semester: April 8 from 12:00 to 13:00. Please write an email to the tutor in order to review your exam.

 

 

Constraints are present in many commercial and industry problems, where these restrictions have to be satisfied by possible solutions. Constraint Programming is a problem-solving technique that works by incorporating such restrictions into a programming environment. Constraint Programming draws on methods from artificial intelligence, logic programming and operations research. It has been successfully applied in a number of fields such as planning and scheduling, computational linguistic or game solving (Sudoku, Rubik’s Cube, Crosswords)

 

Over the last decade, constraint programming has additionally been considered for optimization methods, as many of their problems also deal with constraints. Development in optimization which can lead to a better solution of a particular problem is of considerable value to science and industry.

 

This course addresses the basic and advanced topics in the area of constraint programming and contains the following content:

  • Introduction to Constraint Satisfaction Problems (CSP) and modelling combinatorial problems using Constraint Programming (CP)
  • Constraint Domains and Consistency methods (Node Consistency, Arc Consistency, Path Consistency)
  • Generic Architecture for solving CSPs using propagation and search
  • Constraint Solving methods: Backtracking, Backjumping, Forward checking...
  • Local search methods for CSPs
  • Temporal CSPs: Interval algebras
  • Hard and soft constraints, Partial CSPs and Maximal CSPs
  • Constraint handling in Optimization Problems: Constraint Satisfaction Optimization Problem (CSOP): Branch and bound, Russian Doll Search, Constraint Handling Techniques

 

Prerrequisites

You should have background knowledge on fundamentals of programming, such as arrays, enumerated types, loops, ... and fundamentals of computer science, such as algorithms, structures, etc. Also, insights into logic and fundamentals of mathematics are required. During the course, there will be some concepts that are supposed to be known by any student on a computer-related career, and therefore will not be explained, including graph theory (graph structures and algorithms), automata (DFA) or complexity theory (big O, NP-complete), among others.

 

 

Team

 

Lectures 

The lectures take place: Wednesdays 09:00 -11:00 in G29-307. The first lecture will take place on 16th October.

 

In order to attend this lecture, you will need to apply for a spot. This is done via the LSF system from 2nd September to 7th October. Please use this link to see the tutorial information in the LSF system. After you log in with your student account, you can register for the lecture. Important: There is only 30 places for this lecture. Therefore, if there are too many applicants, it might be that not every applicant can attend this lecture and the tutorials. Note that the final assignment of the free spots will be done after the application deadline is over, and you will be informed via email if you can participate in this course or not.

 

Slides

 

Resources

 

 

Tutorials

For the lecture there will be weekly tutorials. In order to write the exam at the end of the lecture, you must attend and actively participate in one of the tutorial groups. New assignments will be published here every week. You are only allowed to attend, if you are accepted in the lectures.

Participation in the tutorials consists of preparing answers to the written assignments at home as well as coming to the tutorials and presenting your solutions to your fellow students. At the beginning of each tutorial, we will ask you to volunteer for those assignments that you prepared. In addition, there will be one programming assignment each week, which must be sent via email the day before the tutorial until 13:00. You pass the tutorial (and are allowed to write the exam) only if you volunteer for at least 2/3 of all written assignments, send at least 3 programming assignments and present a solution at least twice for written assignments or once for programming assignments.

 

The tutorials take place: Thursdays 13:15 - 14:45 at G22A-110. The first tutorial will take place in the fourth week of the semester, on 7th November.

 

Note: Each week, one assignent sheet will be discussed. You only volunteer and present for assignments in the respective week where these assignments are scheduled to be discussed. The submission of assignments via email is not possible. You should notify your TA about your absence beforehand. If you have a certificate of illness from your physician, the respective assignment sheet will not be counted when calculating your percentage of solved assignments in the end.

 

Assignments

 

Programming Assignments Software

During this course, the modelling tool MiniZinc will be employed for the programming assignments. This tool will be used in all the examples in the lectures, and a little introduction will be given in the first lecture. Nevertheless, it is recommended that students take a look at MiniZinc Tutorial and use MiniZinc Handbook as a reference for any doubt that could arise when solving the programming assignments.

 

----- Announcement: -----

The CP lecture is having a very large amount of students applying for the lectures. Unfortunately, we do not have enough resources to provide lectures and tutorials to all of them, but only for a group of 30 students, which will be selected randomly. In order to be able to participate, you must register in the Course Lectures (Vorlesung) via LSF before October 7th. After this deadline, students will be notified either if they are allowed or not into the course via E-mail. After this, if some of the allowed students decide to abandon the course before or during the first lecture, a new selection will be done over the denied students. Because of this, assitance to the first lecture is MANDATORY for both allowed students and denied students that are still interested and want a second chance, in order to know the rules of this course and get a first touch with Constraint Programming, and be able to decide if you want to attend this course or not.


Regarding this situation, please carefully read this webpage and the first slides of the course to be sure that you really want to join this course, as other students that are interested may be left out due to this limitation issue. If you have registered but you finally decide that you are not interested, please write an Email to the lecturers of the course and inform them about this, so they can select other people to take over your spot.

 

 

 

Literature

  •  Rossi, Francesca, et al. Handbook of constraint programming. Elsevier, 2006.
  • Apt, Krzysytof R. Principles of constraint programming. Cambridge University Press, 2003.
  • Dechter, Rina. Constraint processing. Morgan Kaufmann Publishers, 2003.
  • Perke, Justyna. Bridging Constraint Satisfaction and Boolean Satisfiability. Springer International Publishing, 2015.
  • Stuckey, Peter J. et al. MiniZinc Handbook. https://www.minizinc.org/

 

Last Modification: 25.02.2020 - Contact Person: Webmaster