Constraint Processing and Programming

You are here

Home » Studies » Masters » Master in Artificial Intelligence » Curriculum » Syllabus » Constraint Processing and Programming
Credits
4.5
Types
Elective
Requirements
This subject has not requirements, but it has got previous capacities
Department
CS
Discrete Optimization Problems appear in a huge number of domains ranging from engineering, logistics, bioinformatics, probabilistic reasoning, resource allocation, scheduling, etc.

In this course we will learn how to identify, model and solve such type of problems. We will use the celebrated declarative approach in which the user models the problem with a generic language and then uses a generic library of solving techniques.

For this course we will use the MiniZinc modeling language and present three solving paradigms that can be used with it: Boolean Satisfiability, Constraint Programming and Integer Linear Programming. For each one we will cover their expressive power and the main intuitions behind their solving techniques.

The course orientation is essentially practical. We will learn mainly through examples, although some theoretical ideas will also be included.

Teachers

Person in charge

  • Francisco Javier Larrosa Bondia ( )

Weekly hours

Theory
1
Problems
1
Laboratory
1
Guided learning
0
Autonomous learning
5.65

Competences

Generic Technical Competences

Generic

  • CG1 - Capability to plan, design and implement products, processes, services and facilities in all areas of Artificial Intelligence.

Technical Competences of each Specialization

Academic

  • CEA1 - Capability to understand the basic principles of the Multiagent Systems operation main techniques , and to know how to use them in the environment of an intelligent service or system.
  • CEA13 - Capability to understand advanced techniques of Modeling , Reasoning and Problem Solving, and to know how to design, implement and apply these techniques in the development of intelligent applications, services or systems.

Transversal Competences

Reasoning

  • CT6 - Capability to evaluate and analyze on a reasoned and critical way about situations, projects, proposals, reports and scientific-technical surveys. Capability to argue the reasons that explain or justify such situations, proposals, etc..

Objectives

  1. Ability to model optimally a discrete optimization problem and solve it using the proper tools.
    Related competences: CEA1, CEA13, CG1, CT6,
    Subcompetences:
    • Translate a real-life optimization problem into a well-defined specification using a formal language
    • Boolean Satisfiability for Discrete Optimization
    • Local Search
    • Integer Linear Programming
    • Constraint Programming

Contents

  1. Modeling combinatorial problems
  2. Solving with Constraint Programming
  3. Solving with Propositional Logic (SAT)
    .
  4. Solving with integer linear programming
    .

Activities

Activity Evaluation act


Modeling


Objectives: 1
Theory
0h
Problems
10h
Laboratory
13h
Guided learning
0h
Autonomous learning
50h

Constraint Programming


Objectives: 1
Theory
4h
Problems
1h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

Boolean Satisfiability



Theory
5h
Problems
1h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

Integer Linear Programming



Theory
4h
Problems
1h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

Teaching methodology

For the modeling part, the "flipped classroom" system will be used where students will have to watch videos and do small projects. Class hours will be used to resolve doubts and consolidate knowledge.

For the part of resolution techniques, the classic master class methodology and some class of problems will be used.

Evaluation methodology

Throughout the course, small projects (around 6) will be carried out with a combined weight of 30% of the final grade. There will also be a quiz at the beginning of the course, a partial exam and a final exam with a total weight of around 70% of the grade

Bibliography

Basic:

Previous capacities

Basic Algorithmics