## Constraint Programming

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

The lecture and tutorial taking place **last week are being swapped**, so last tutorial will take place on Wednesday 29 from 9:00 to 11:00 in room G29-307; and last lecture will take place on Thursday 30 from 13:00 to 15:00 in room G22A-110. Last lecture will consists on a Q&A session, where students can ask their doubts about the course in general, both lecture and tutorials. If this change suppose some struggle for any student taking part in the course, please send an email to the lecturer to inform him about your issue.

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

- Cristian Ramirez Atencia (Lectures and Tutorials)

#### 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

- Chapter 0: Organization
- Chapter 1: Introduction
- Chapter 2: Problem Modelling
- Chapter 3: Solving Techniques
- Chapter 4: Local Search and Heuristics
- Chapter 5: Constraint Satisfaction Optimization Problems
- Chapter 6: Over-constrained problems

#### 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

- Assignments 1 (discussed in tutorials on 7th November) - Minizinc datafile
- Assignments 2 (discussed in tutorials on 14th November) - Minizinc datafile
- Assignments 3 (discussed in tutorials on 21th November) - Minizinc datafile
- Assignments 4 (discussed in tutorials on 28th November) - Minizinc datafile
- Assignments 5 (discussed in tutorials on 5th December) - Minizinc datafile
- Assignments 6 (discussed in tutorials on 12th December) - Minizinc datafile
- Assignments 7 (discussed in tutorials on 19th December) - Minizinc datafile
- Assignments 8 (discussed in tutorials on 9th January)
- Assignments 9 (discussed in tutorials on 16th January) - Minizinc datafile
- Assignments 10 (discussed in tutorials on 23th January)
- Assignments 11 (discussed in tutorials on 29th January) - Minizinc datafile

#### 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/