Course handouts CSC_51055_EP - Constraint-based Modeling and Algorithms for Decision Support (36h)

Modèles et Algorithmes à base de Contraintes pour l'Aide à la Décision

François Fages, Mathieu Hemery, Inria Saclay Ile de France

Ecole Polytechnique

Master Artificial Intelligence & Advanced Visual Computing

Master of Science and Technology

2024-2025

The purpose of this course is to present constraint-based methods for mathematical modeling and computational solving of combinatorial search problems, with applications especially in industry and life sciences.

Each lecture of approximatively 2h will be followed by 2h of practical work for illustrating the taught concepts and manipulating the associated tools.

The logic programming language SWI-Prolog with its constraint solving libraries (clpfd.pl, clpr.pl) and a constraint-based modeling library (modeling.pl inspired by the MiniZinc modeling language) will be used as a unifying framework for both the mathematical modeling of decision making problems and the programming of constraint solvers, and for showing the practical complexity of different models and different solvers on some NP hard problems.

Grades:

• 50% mean of your best 5 over 6 TPs
• 50% final written examination.

Bibliography:

• mini manual of SWI-Prolog including pointers to pack modeling
• The slides of the lectures and solutions to TDs are sufficient to prepare the examination.
• Yet the following lecture notes can be consulted, as well as the Handbook of Constraint Programming for particular questions on the subject.

Schedule 2024-2025

• 25 September Constraint satisfaction problem modeling and solving with general purpose constraint solvers
  • TD Solving puzzles in SWI-Prolog with modeling pack
    
• 2 October The class of constraint programming languages CLP(X)
  • TD Deductive databases, knowledge graphs
    
• 9 October CLP(H) on the Herbrand's domain of first-order logic terms
  • TD symbolic differentiation, list processing, task scheduling
    
• 23 October CLP(Z) domain filtering algorithms
  • TD Programming a constraint solver for task scheduling problems
    
• 6 November Complexity classes, search procedures and heuristics
  • TD Heuristics in the N-queens problem. Solving an NP-hard disjunctive task scheduling problem for building a bridge.
    
• 13 November Symmetry breaking constraints
  • TD Symmetry breaking in the N-queens problem. Automated theorem proving in group theory
    
• 20 November CLP(R) linear programming, Fourier's elimination alg.
  • TD Programming a SAT solver in Prolog
    
• 4 December Boolean modeling, SAT solvers, NP-completeness
  • TD Tracing a SAT solver, observing phase transition in random 3-SAT
    
• 11 December Constraint-based local search algorithms
  • TD Constraint-based hill-climbing, simùulated annealing, tabu search.
    
• 18 December: final examination

Previous written examinations

• 2024 written examination with solution
• 2023 written examination with solution
• In previous years the modeling language MiniZinc and programming language Python were used in place of the single declarative programming/modeling language Prolog for this course:
• 2022 written examination with solution
• 2021 written examination with solution
• 2020 online examination
• 2019 written examination part 1 with solutions, part 2 with solutions
• 2018 written examination part 1 with solutions, part 2 with solutions.

Previous year 2022-2023 based on MiniZInc+Python

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

Schedule 2022-2023 (see Moodle 2022-2023)

• 21 September Constraint satisfaction problems and the constraint-based modelling language MiniZInc
  • TP Puzzle solving in MiniZinc with preliminaries on Python and Jupyter notebooks
    
• 28 September Boolean models and SAT solvers
  • TP SAT models in MiniZinc and SAT solvers in Python
    
• 5 October Computational complexity and phase transition in SAT
  • TP random k-SAT problems and graph coloring problems in Python and MiniZinc
    
• 19 October Constraints over finite domains and domain filtering algorithms
  • TP mini FD constraint solver in Python
    
• 26 October Search trees and search heuristics
  • TP disjunctive scheduling in MiniZinc-FD
    
• 9 November Symmetry breaking constraints
  • TP Symmetry breaking in MIniZinc-FD
    
• 16 November Global constraints and graph theory
  • TP Air Traffic Control in MiniZinc-FD
    
• 23 November Arithmetic constraints and linear programming
  • TP Linear programming for production planning in MIniZinc-LP
    
• 8 December Constraint-based local search allgorithms
  • TP CBLS algorithms in Python
    
• 14 December: final examination
  • The slides of the lectures and the TPs are sufficient to prepare the examination.
  • Yet the following book can be consulted for particular questions on the subject: Handbook of constraint programming