Constraint programming

5.00 credits

30.0 h + 15.0 h

> Schedule

Teacher(s)

Schaus Pierre;

Language

English
> French-friendly

Main themes

Constraints and domains
Practical aspects of constraint solvers
Constraint Satisfaction Problems (CSP)
Models and languages for constraint programming
Methods and techniques for constraint solving (consistency, relaxation, optimization, search, linear programming, global constraints, ...)
Search techniques and strategies
Problem modelling and resolution
Applications to differents problem classes (e.g. planification, scheduling, ressource allocation, economics, robotics)

Learning outcomes

At the end of this learning unit, the student is able to :

With regard to the AA reference framework of the “Master in Civil Engineering in Computer Science” program, this course contributes to the development, acquisition, and assessment of the following learning outcomes:

AA1.1. When faced with a computing problem, the student identifies the applicable concepts, algorithms, and data structures to solve it; they leverage these to break down the problem into subproblems and develop computational methods to solve them.
AA1.3. When confronted with results obtained through reasoning and the implementation of tools and concepts, the student takes the necessary step back to verify their relevance in terms of functionality and quality of the intended solution. In this context, they will develop relevant tests and verifications to ensure the quality of the developed solution.
AA2.4. During the implementation phase of the solution, the student demonstrates mastery of the principles, techniques, and development tools at their disposal. They create a software prototype to verify that it meets client expectations. They set up a testing environment and a suite of tests to ensure the developed solution meets the functional requirements. By applying validation and verification techniques, they identify, locate, and fix bugs.
AA5.4. The student is proficient in using reference books or manuals related to programming languages or software, both in English and French. They understand technical presentations given in English.
AA5.5. During the development of a software application, the student ensures traceability and documentation in a concise and precise manner, covering specifications, software and data structures, and operational procedures. They also apply this approach when writing a summary report explaining and justifying design and technology choices in project development.

With regard to the AA reference framework of the “Master [120] in Computer Science” program, this course contributes to the development, acquisition, and assessment of the following learning outcomes:

AA1. Demonstrate mastery of a solid body of knowledge in computer science, enabling the resolution of problems within the discipline.
AA2.1. Analyze the problem to be solved or the functional requirements to be met and formulate the corresponding specifications.
AA2.2. Model the problem and design one or more original technical solutions that meet these specifications.
AA2.4. Implement and test the selected solution.
AA3.2. Propose a model and/or an experimental framework to simulate and test hypotheses related to the problem in all its complexity.
AA6.5. Self-evaluate and independently develop the knowledge necessary to remain competent in the field.
Understand a set of computer techniques for solving a constraint satisfaction problem.
Develop and extend a constraint programming solver.
Solve a simple application implementing the studied techniques.
Explain the foundations of constraint programming models and languages.
Identify classes of applications where constraint programming can be effectively used.
Model a simple problem as constraints and express this model in a constraint programming language, including the definition of search strategies.

Content

Constraint Programming : a Declarative Programming paradigm
Architecture of a constraint programming solver
Global contraints and implementation techniques (incrementality, etc)
Search techniques and strategies
Combinatorial optimization problem modeling and solving
Modeling and solving combinatorial optimization problems using constraint programming
Applications to different problem classes (e.g. planification, scheduling, resource allocation, economics, robotics)

Teaching methods

The presentation of concepts will be delivered either through lectures, videos, or readings, and will be accompanied by practical work (assignments/micro-projects) requiring the application of these concepts.

Evaluation methods

June — First Session

The June grade consists of two independent parts worth 10 points each, for a total of 20 points:

10 points for practical work;
10 points for theory.

Practical Part — 10 points

The 10 practical points can be obtained in one of two ways:

either by passing the practical exam on INGInious, organized at the end of the quadrimester and lasting two hours;
or by passing the practical programming section on paper during the June exam.

The INGInious exam covers the programming projects completed during the quadrimester.
Failing the INGInious exam therefore does not mean losing the 10 practical points: the student can still obtain these points during the practical programming section on paper in the June exam.
Nevertheless, it is in the student’s interest to participate in the INGInious exam and attempt to pass it. If successful, the 10 practical points are secured before the June exam, allowing the student to focus on the theoretical part during the written exam and thereby reduce the amount of programming material that needs to be prepared.

Theoretical Part — 10 points

The 10 theory points are assessed during the written June exam.
The exam may include questions concerning the projects completed during the quadrimester and their source code.

August — Second Session

In the second session, the exam is entirely conducted on paper and remains divided into two parts worth 10 points each:

10 points for theory;
10 points for practical work, in the form of programming on paper.

The practical part of the August exam corresponds to the 10 points that were initially assessed through the INGInious exam.
However, the 10 practical points corresponding to the programming-on-paper section of the June exam cannot be carried over separately to August.

	Theory	Practical	Total
June	10 pts on paper	10 pts via INGInious or programming on paper	20 pts
August	10 pts on paper	10 pts of programming on paper (carried over from the INGInious section)	20 pts

Exam Conditions

All exams are individual. No collaboration, communication, or outside assistance is permitted during the exams.
The use of generative AI is strictly prohibited during the INGInious exam as well as during the written exams, both in June and in August.
Students must therefore complete the exams individually and without using any generative AI tools.
The INGInious exam is therefore a risk-free opportunity in June: if the student fails, they can still obtain their 10 practical points through the programming-on-paper section of the June exam. If they pass, they validate this part directly and benefit from a reduced amount of programming material to prepare for the June exam.

Other information

A good background in data-structure and algorithms is required to follow this course and a good knowledge of Java language

Online resources

https://moodle.uclouvain.be/course/view.php?id=2009
www.minicp.org

Bibliography

Le site www.minicp.org + lectures suggérées pendant le semestre

Faculty or entity

> INFO

Programmes / formations proposant cette unité d'enseignement (UE)

Title of the programme

Sigle

Credits

Prerequisites

Learning outcomes

Master [120] in Computer Science and Engineering

INFO2M

Master [120] in Computer Science

SINF2M

Master [120] in Data Science Engineering

DATE2M

Master [120] in Data Science: Information Technology

DATI2M