Course handouts INF555 - Constraint-based Modeling and Algorithms for Decision Making Problems (36h)

Modélisation et Algorithmes à base de Contraintes pour les Problèmes d'Aide à la Décision

Master Artificial Intelligence & Advanced Visual Computing, Ecole Polytechnique

François Fages, Sylvain Soliman, Inria Saclay Ile de France

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 modeling language MiniZinc with its different back end constraint solvers (SAT, FD, LP, CMA-ES) will be used as a unifying framework and as basis for showing the practical complexity of different solvers on some NP hard problems.

See Moodle

  1. Introduction to constraint satisfaction problems and to the Constraint modeling language MiniZinc
    → TP Python/Jupyter preliminaries and puzzle solving in MiniZinc
    docker pull registry.gitlab.inria.fr/soliman/inf555/td1
  2. Boolean satisfiability, SAT solvers
    → TP SAT solver (python)
    docker pull registry.gitlab.inria.fr/soliman/inf555/td2
  3. Constraint-Based Local Search
    → TP simulated annealing
    docker pull registry.gitlab.inria.fr/soliman/inf555/td3
  4. Polynomial complexity classes in SAT, phase transitions in random k-SAT
    → TP random k-SAT problems and graph coloring problems (python and MiniZinc-FD)
    docker pull registry.gitlab.inria.fr/soliman/inf555/td4
  5. Constraint propagation and domain filtering algorithms
    → TP mini constraint solver (python)
    docker pull registry.gitlab.inria.fr/soliman/inf555/td5
  6. Search and heuristics
    → TP MiniZinc-FD on disjunctive scheduling
    docker pull registry.gitlab.inria.fr/soliman/inf555/td6
  7. Global constraints
    → TP MiniZinc-FD on Air Traffic Control
    docker pull registry.gitlab.inria.fr/soliman/inf555/td7
  8. Symmetries
    → TP MiniZinc-FD on symmetry breaking constraints
    docker pull registry.gitlab.inria.fr/soliman/inf555/td8
  9. Arithmetic Constraints
    → TP MiniZinc-LP linear programming for production planning
    docker pull registry.gitlab.inria.fr/soliman/inf555/td9
  10. Written examination: Wednesday December 18th, 2019 14.00-17.00
    1. The slides and TDs are sufficient to prepare the examination.
    2. Yet the following book can be consulted on the subject: Handbook of constraint programming
    3. Previous examinations: 2019 Part 1 Δ, correction Part 2, 2018 Part 1, correction Part 2.