Constraint Processing and Programming

Credits
4.5
Types
  • MAI: Elective
  • MEI: 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

Weekly hours

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

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
    • Constraint Programming
    • Integer Linear Programming
    • Local Search
    • Translate a real-life optimization problem into a well-defined specification using a formal language
    • Boolean Satisfiability for Discrete Optimization
    • Constraint Programming
    • Integer Linear Programming
    • Local Search

Contents

  1. Modeling combinatorial problems
    We will use the modeling language MiniZinc to model a wide variety o problems. We will cover topics such as modeling linear problems, sets, functions, and how to deal with symmetries, common sub-expressions, etc
  2. Solving with Constraint Programming
    We will cover issues such as Look-ahead, heuristics, local consistency and global constraints
  3. Solving with Propositional Logic (SAT)
    We will cover topics such as Conjunctive Normal Form (CNF), resolution, unit propagation, clause learning.
  4. Solving with integer linear programming
    We will overview the SIMPLEX algorithm and Branch and Bound

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 will be carried out with a combined weight of 20% 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 80% of the grade

Bibliography

Basic

Web links

  • MiniZinc is a high-level constraint modelling language that allows you to easily express and solve discrete optimisation problems. https://www.minizinc.org/

Previous capacities

Basic Algorithmics