Introduction pratique à la programmation par contraintes avec CP-SAT et Python

Introduction pratique à la programmation par contraintes : CP-SAT et Python

Paradigme déclaratif

• La programmation par contraintes (CP) est un paradigme déclaratif destiné à résoudre des problèmes d’optimisation discrète
• Contrairement à la programmation impérative, on décrit le résultat souhaité et le programme en déduit lui-même la solution
• Par exemple, l’article explique la différence entre une approche impérative et une approche déclarative pour extraire une liste d’adultes

Bases de la programmation par contraintes (CP)

• Modèle : description du résultat souhaité pour le problème
• Variables : valeurs à trouver, chaque variable ayant un domaine (ensemble de valeurs autorisées)
• Contraintes : description des relations entre les variables
• Solution : affectation de valeurs aux variables de façon à satisfaire les contraintes

Exemple pratique avec Python et CP-SAT

• Problème : générer le planning hebdomadaire de travail d’employés
• Création du modèle : création d’un modèle vide avec CP-SAT
• Données : définition de la liste des employés, des rôles, des jours de travail et des créneaux de service
• Définition des variables : création de variables booléennes indiquant si chaque employé travaille ou non
• Ajout de contraintes : ajout de contraintes aux variables selon la description du problème

Résolution du modèle

• Résolution : résolution du modèle pour produire un résultat
• Contraintes supplémentaires : ajout de contraintes additionnelles pour éviter les heures supplémentaires, limiter le temps de travail de certains employés ou empêcher le chevauchement des horaires entre certains employés

Au milieu : états de résolution

• État de résolution : retour d’états tels que optimal, faisable, infaisable ou inconnu
• Exemple : explication de chaque état à l’aide d’un exemple simple

« Désolé, Emma »

• État infaisable : il est impossible pour Emma d’avoir 5 jours de repos en semaine
• Proposition alternative : il est proposé qu’Emma n’ait que 3 jours de repos en semaine

Objectif : répartir équitablement le temps de travail

• Ajout d’un objectif : ajout d’un objectif afin de répartir équitablement le temps de travail
• Résultat : le temps de travail est réparti de manière équilibrée entre les employés

Conclusion

• Introduction aux concepts de base : présentation des notions fondamentales de la programmation par contraintes et explication au moyen d’un exemple pratique
• Annonce du prochain article : le prochain article expliquera comment utiliser la programmation par contraintes pour le choix d’index dans Postgres

L’avis de GN⁺

• Utilité de la programmation par contraintes : très utile pour résoudre des problèmes d’optimisation complexes
• Forces de CP-SAT : développé dans le cadre du projet OR-Tools de Google, CP-SAT offre de solides performances
• Cas d’usage concrets : applicable à des problèmes réels comme la génération de plannings de travail pour les employés
• Points à considérer pour l’adoption : lors de l’adoption d’une nouvelle technologie, il faut prendre en compte la courbe d’apprentissage et les questions d’intégration avec les systèmes existants
• Projets similaires recommandés : des solveurs commerciaux comme IBM CPLEX ou Gurobi proposent également des fonctionnalités comparables

[GN⁺]

Commentaires Hacker News

• J’ai déjà utilisé des solveurs de contraintes par le passé, et ces outils offrent des performances vraiment remarquables

  • Le problème, c’est qu’il existe très peu de ressources pour les débutants
  • La plupart des ressources expliquent comment résoudre un Sudoku ou sont des documents de recherche très techniques
  • J’aimerais que les outils capables de résoudre davantage de problèmes soient plus accessibles
  • Par accessible, j’entends qu’il faut malgré tout encore un programmeur

• Je suis en train de réécrire dans mon ancien livre un court chapitre qui utilise MiniZinc et Python

  • MiniZinc est un système de programmation par contraintes
  • Il existe un bon cours sur Coursera qui utilise MiniZinc

• Beaucoup de programmes essaient d’avoir une représentation unique des données, mais dans la plupart des cas cela n’est pas rationnel

  • Il faut énormément de contorsions pour faire fonctionner un algorithme sur une nouvelle représentation
  • Je regrette toujours qu’on ne transforme pas plus souvent les représentations
  • Transformer les représentations permet d’obtenir une formulation très concise, ce qui peut permettre une exécution plus rapide

• J’ai un client qui gère des stages sportifs

  • Les enfants peuvent demander les sports qu’ils veulent pratiquer et avec quels amis
  • Cela crée un problème de planification difficile pour un humain
  • J’ai construit un système simple à l’aide d’un outil d’optimisation basé sur OR-Tools
  • Désormais, le planning est terminé en quelques clics

• J’ai beaucoup utilisé des solveurs au début des années 2000

  • Aujourd’hui, je travaille sur des logiciels (web) en Python
  • Je suis heureux de voir une exploration approfondie de ce sujet
  • Convertir les contraintes en modèle représente 90 % du travail, et c’est la partie la plus difficile

• Je me demande s’il existe un CAD paramétrique qui fonctionne principalement avec un solveur de contraintes

  • Au début, il est souvent pénible de devoir estimer des valeurs de paramètres dont on ne se soucie pas
  • À la place, j’aimerais contraindre les paramètres qui m’intéressent et optimiser le reste

• Je me demande comment cela se compare à la programmation linéaire en nombres entiers mixtes