v2.2.12 (2462)

PA - C4B - INF555 : Constraint-based Modeling and Algorithms for Decision-making

Domaine > Informatique.


The purpose of this course is to present constraint-based methods used in automated reasoning and search problems. Each lecture of approximatively 2h will be followed by 2h of practical work for illustrating the taught concepts and manipulating the associated tools on decision making applications. The constraint modelling language MiniZinc with its different back end constraint solvers (SAT, FD, LP, etc.) will be used as unifying framework and as basis for showing the practical complexity of different solvers on some NP hard problems.

  1. Introduction to decision, optimization and constraint satisfaction problems and to the Constraint modeling language MiniZinc
    • TP Python/Jupyter preliminaries and puzzle solving in MiniZinc
  2. Boolean satisfiability, SAT solvers
    • TP SAT-solver (python)
  3. Polynomial complexity classes in SAT, phase transitions in random k-SAT
    • TP random k-SAT problems and graph coloring problems (python and MiniZinc-FD)
  4. Constraint propagation and domain filtering algorithms 
    • TP mini constraint solver (python)
  5. Search and heuristics
    • TP MiniZinc-FD on disjunctive scheduling
  6. Global constraints
    • TP MiniZinc-FD on Air Traffic Control
  7. Symmetries
    • TP MiniZinc-FD on symmetry breaking constraints
  8. Arithmetic constraints
    • TP MiniZinc-LP Linear Programming for production planning
  9. Constraint-based local search and black box continuous optimization
    • TP simulated annealing

Modalités d'évaluation : TDs + écrit final

Langue du cours : Anglais & Français

Credits ECTS : 4

Format des notes

Numérique sur 20

Littérale/grade réduit

Pour les étudiants du diplôme Diplôme d'ingénieur de l'Ecole polytechnique

Le rattrapage est autorisé
    L'UE est acquise si note finale transposée >= C
    • Crédits ECTS acquis : 5 ECTS

    La note obtenue rentre dans le calcul de votre GPA.

    Pour les étudiants du diplôme Artificial Intelligence and Advanced Visual Computing

    Le rattrapage est autorisé
      L'UE est acquise si note finale transposée >= C
      • Crédits ECTS acquis : 4 ECTS
      Veuillez patienter