Contraintes Dures vs Souples dans CP-SAT

La distinction : interdit vs coûteux

Chaque règle dans un modèle de planification CP-SAT appartient à l'une de deux catégories. Une contrainte dure doit être satisfaite. Si le solveur ne peut pas trouver de solution qui respecte toutes les contraintes dures simultanément, il retourne INFEASIBLE. Aucun planning n'est produit. Une contrainte souple peut être violée, mais chaque violation ajoute une pénalité à la fonction objectif. Le solveur minimise la pénalité totale, donc il essaie de satisfaire les contraintes souples, mais il les enfreindra si cela produit un meilleur planning global.

La question critique lors de la conception d'un modèle est : "Que se passe-t-il quand cette règle est violée ?" Si la réponse est "le planning est illégal", la règle est une contrainte dure. Si la réponse est "le planning est sous-optimal mais utilisable", la règle est une contrainte souple.

Se tromper dans cette distinction a des conséquences réelles. Trop de contraintes dures et le solveur retourne INFEASIBLE alors qu'un planning utilisable existe. Trop de contraintes souples et le solveur produit des plannings qui violent la réglementation. L'art de la modélisation par contraintes est de trouver la bonne frontière.

Contraintes dures en planification

Les contraintes dures encodent des règles qui ne peuvent être enfreintes en aucune circonstance. En planification du personnel, ce sont typiquement des exigences légales, des impossibilités physiques ou des engagements pré-existants.

Un shift par jour

# Pour chaque employe e, pour chaque jour d :
sum(assign[e, d, s] for s in all_shifts) <= 1

Un employé ne peut pas travailler deux shifts le même jour. C'est une contrainte physique : une personne ne peut pas être à deux endroits en même temps. Il n'y a aucun scénario où violer cette règle est acceptable, donc elle doit être dure.

Respect des qualifications

# Si l'employe e n'est pas qualifie pour le shift s :
assign[e, d, s] = 0  (pour tous les jours d)

Un agent de sécurité ne peut pas être affecté à un shift logistique s'il ne détient pas la qualification logistique. C'est une exigence réglementaire. La violer signifie du personnel non qualifié dans des postes critiques pour la sécurité.

Absences pré-assignées

# HOLIDAY, VACATION, FIXED_OFF le jour d pour l'employe e :
assign[e, d, s] = 0  (pour tous les shifts s)
is_off[e, d] = 1

Si un employé est en vacances approuvées, le solveur ne peut pas le planifier. Les vacances ont été convenues avant la génération du planning. Les outrepasser casserait un engagement contractuel.

Repos minimum de 11 heures

# Pour chaque paire toxique (s1, s2), pour chaque employe e, pour chaque jour d :
assign[e, d, s1] + assign[e, d+1, s2] <= 1

La loi du travail impose un repos minimum entre deux shifts. Nous pré-calculons les "paires toxiques" de shifts qui violeraient la règle des 11 heures et les interdisons. C'est une contrainte légale qui protège la santé et la sécurité des employés.

Contraintes souples et pénalités

Les contraintes souples encodent des objectifs que le solveur doit poursuivre, mais peut sacrifier si nécessaire. Chaque violation coûte une pénalité. Le solveur minimise la somme de toutes les pénalités : plus bas = meilleur.

Couverture (pénalité : 10 000 par poste manquant)

# Pour chaque fonction f, pour chaque jour d :
assigned = sum(assign[e, d, s] for e qualifie pour f, s dans fonction f)
missing = max(0, need[f, d] - assigned)
penalty += missing * WEIGHT_COVERAGE

La contrainte souple de plus haute priorité. Un poste non couvert signifie un trou opérationnel. Mais rendre la couverture dure signifierait que toute pénurie de personnel (vacances, maladie) rend le planning entier INFEASIBLE. La couverture est souple pour que le solveur puisse produire le meilleur planning possible même quand il n'y a pas assez de monde.

Garantie de weekend (pénalité : 5 000)

# Pour chaque employe e (non etudiant) :
has_weekend_off = max sur tous les weekends w de :
    (is_off[e, samedi_w] AND is_off[e, dimanche_w])
penalty += (1 - has_weekend_off) * WEIGHT_WEEKEND

Chaque employé devrait avoir au moins un weekend complet de repos par mois. C'est un objectif de qualité de vie, pas une obligation légale. En période de pointe, le solveur peut devoir sauter un weekend pour certains employés afin de maintenir la couverture.

Jours consécutifs de travail (pénalité : 2 000)

# Pour chaque employe e, pour chaque fenetre de 7 jours consecutifs :
si les 7 jours sont travailles : penalty += WEIGHT_CONSECUTIVE

Travailler plus de 6 jours consécutifs est indésirable mais parfois inévitable. C'est le cas classique d'une contrainte qui se situe à la frontière entre dure et souple (plus de détails ci-dessous).

Jours de repos (pénalité : 1 500 par jour manquant)

# Pour chaque employe e :
actual_off = sum(is_off[e, d] for d in mois)
missing_off = max(0, target_off[e] - actual_off)
penalty += missing_off * WEIGHT_DAYS_OFF

Chaque employé a un nombre cible de jours de repos base sur son contrat. Le solveur essaie d'atteindre la cible, mais peut être en dessous si les besoins de couverture l'exigent.

Jours de repos isolés (pénalité : 1 000)

# Pour chaque employe e, pour chaque jour d (sauf premier et dernier) :
si is_off[e, d] AND NOT is_off[e, d-1] AND NOT is_off[e, d+1] :
    penalty += WEIGHT_ISOLATED_OFF

Un jour de repos isolé entre deux jours de travail est moins reposant que des jours de repos consécutifs. Le solveur préfère regrouper les jours de repos.

Équité par qualification (pénalité : 500 par unité d'écart)

# Pour chaque groupe g, pour chaque fonction f :
gap = max_shifts[g, f] - min_shifts[g, f]
penalty += gap * WEIGHT_QUALIF_EQUITY

Au sein de chaque groupe, les shifts doivent être distribués équitablement entre les types de qualification. Les employés en congé ou en vacances sont exclus du calcul d'équité.

Équité de charge (pénalité : 50 par unité d'écart)

# Pour chaque groupe g :
gap = max_jours_travailles[g] - min_jours_travailles[g]
penalty += gap * WEIGHT_WORKLOAD_EQUITY

L'objectif de plus basse priorité. Le solveur sacrifiera l'équité de charge pour préserver tout objectif de priorité supérieure.

Quand une contrainte dure devient souple

L'exemple classique est celui des jours consécutifs de travail. La loi du travail dit qu'un employé ne devrait pas travailler plus de 6 jours consécutifs. L'instinct est de l'encoder en dur. Mais considérons ce qui se passe lors d'une pénurie de personnel.

Imaginons une équipe de 20 employés dont 5 sont en vacances la même semaine. Les 15 restants doivent couvrir tous les shifts. Avec les jours consécutifs en contrainte dure, le solveur ne peut trouver aucune affectation qui couvre tous les shifts sans que quelqu'un travaille 7 jours d'affilée. Le résultat : INFEASIBLE. Aucun planning du tout.

Maintenant, rendons les jours consécutifs souples avec une pénalité de 2 000. Le solveur trouve une solution où 3 employés travaillent 7 jours consécutifs, mais chaque shift est couvert. Le planificateur voit les violations dans le rapport, comprend le compromis, et décide s'il approuve le planning ou ajuste les données d'entrée (ex : décaler un jour de vacances).

La version souple est strictement meilleure : elle donne au planificateur un planning utilisable plus un avertissement clair, au lieu d'aucun planning du tout.

Le cadre de décision

Utilisez cet arbre de décision mental pour choisir comment encoder une règle :

La regle est-elle une exigence legale ou de securite ?
  OUI --> Le planning peut-il etre utilisable si violee ?
            OUI --> Souple (penalite elevee)
            NON --> Dure
  NON --> Est-ce une preference de qualite de vie ?
            OUI --> Souple (penalite moyenne/basse)
            NON --> Est-ce une impossibilite physique ?
                      OUI --> Dure
                      NON --> Souple

La plupart des règles de planification tombent dans la catégorie "souple avec pénalité élevée". Les seules contraintes véritablement dures sont les impossibilités physiques (un shift par jour, qualifications) et les engagements irrévocables (absences pré-assignées, repos impose par la loi sans exception).

Hiérarchie des pénalités

Les poids de pénalité créent un système de priorité. Le solveur sacrifiera les objectifs de basse priorité pour préserver ceux de haute priorité. Voici la hiérarchie que nous utilisons en production :

Objectif	Poids de pénalité	Priorité
Couverture manquante	Très élevé	Maximale
Pas de weekend garanti	Élevé	Haute
Jours consécutifs > 6	Élevé	Haute
Jours de repos manquants	Moyen	Moyenne
Jour de repos isolé	Moyen	Moyenne
Écart équité par qualification	Faible	Basse
Écart équité charge de travail	Très faible	Minimale

La logique : un poste non couvert (poids maximum) est toujours pire qu'un jour de repos manquant (poids moyen). Un jour de repos manquant est pire qu'une répartition légèrement inéquitable. La couverture a toujours la pénalité la plus élevée car un poste non couvert signifie une défaillance opérationnelle, alors que toute autre violation est un problème de qualité qui peut être examiné et accepté.

Les écarts entre les niveaux de pénalité comptent. La couverture à 10 000 est 2x la pénalité weekend à 5 000, ce qui signifie que le solveur sauterait le weekend d'un employé avant de laisser un poste non couvert. Mais il ne sauterait pas deux weekends (poids maximum) sauf s'il devait sinon laisser un poste entier non couvert.

Debugger un INFEASIBLE

Quand CP-SAT retourne INFEASIBLE, cela signifie que les contraintes dures sont en conflit entre elles. Il n'existe aucune affectation de variables qui les satisfait toutes simultanément. Ce n'est jamais causé par les contraintes souples, puisque celles-ci peuvent toujours être violées.

Causes fréquentes

• Trop d'absences + trop peu de personnel qualifie. Si 10 des 12 agents de sécurité sont en vacances et que le besoin journalier est de 3, le solveur ne peut pas couvrir tous les jours avec seulement 2 agents disponibles. Le vrai problème est généralement une combinaison d'absences et de rareté des qualifications.
• Affectations fixes en conflit. Un employé a un FIXED_OFF un jour où il a aussi un shift obligatoire assigné ailleurs dans les données. Deux contraintes dures qui se contredisent directement.
• Impossibilités de repos. La combinaison des horaires de shifts et des repos obligatoires rend impossible la création d'une séquence valide pour certains employés.

Approche de debug

# Etape 1 : Supprimer toutes les contraintes souples et resoudre
#           avec uniquement les contraintes dures
#           Si toujours INFEASIBLE, le conflit est dans les dures

# Etape 2 : Relacher les contraintes dures une par une
#           Supprimer les qualifications --> toujours INFEASIBLE ?
#           Supprimer les repos --> toujours INFEASIBLE ?
#           Supprimer les absences --> maintenant FEASIBLE ?
#           --> Le conflit implique les absences

# Etape 3 : Affiner
#           Re-ajouter les contraintes, supprimer les absences
#           d'un employe a la fois
#           --> Les absences de l'employe X causent le conflit

# Etape 4 : Decider
#           Option A : Ajuster les donnees (deplacer les vacances de X)
#           Option B : Convertir la contrainte dure en souple

En pratique, la correction la plus courante est de convertir une contrainte dure en souple avec une pénalité élevée. La deuxième plus courante est d'ajuster les données d'entrée (moins d'absences simultanées, affectations de qualifications différentes).

Exemple concret

Un planificateur saisit 15 employés en vacances la même semaine. L'opération compte 40 employés au total répartis sur 4 groupes fonctionnels. Les besoins journaliers nécessitent 25 employés en poste chaque jour.

Scénario A : toutes les contraintes dures

Avec les jours consécutifs en contrainte dure (max 6), le solveur retourne INFEASIBLE. Les 25 employés restants ne peuvent pas couvrir 7 jours de besoins (175 shifts-jours requis) en travaillant chacun au maximum 6 jours (150 shifts-jours disponibles). Le planificateur n'obtient aucun planning et aucune indication sur ce qu'il faut changer.

Scénario B : jours consécutifs en souple

Avec les jours consécutifs en contrainte souple (pénalité 2 000), le solveur trouve une solution. 3 employés travaillent 7 jours consécutifs. Tous les shifts sont couverts. Le rapport de pénalité montre :

Manques couverture :       0  (penalite :      0)
Violations weekend :       2  (penalite : 10 000)
Consecutifs > 6 :          3  (penalite :  6 000)
Jours repos manquants :    5  (penalite :  7 500)
Repos isoles :             4  (penalite :  4 000)
Ecarts equite :            -  (penalite :  1 200)
------------------------------------------------
Score total :                           28 700

Le planificateur voit que 3 employés vont travailler 7 jours d'affilée. Il peut maintenant prendre une décision éclairée : approuver le planning tel quel, déplacer des vacances sur une autre semaine, ou faire appel à un intérimaire. Le solveur lui a donné une base utilisable et une image claire des compromis.

Principes de conception

Commencer avec tout en dur

Commencez votre modèle avec toutes les règles en contraintes dures. Lancez le solveur sur des données réalistes. S'il retourne FEASIBLE, c'est terminé. S'il retourne INFEASIBLE, vous savez exactement quelles règles doivent devenir souples.

Convertir en souple une règle à la fois

Face à un INFEASIBLE, ne convertissez pas toutes les contraintes en souples d'un coup. Identifiez les règles "flexibles", celles où une violation est indésirable mais pas catastrophique, et convertissez-les une par une. Testez après chaque conversion.

Ne jamais rendre souples les contraintes de sécurité ou légales

Le respect des qualifications (personnel non qualifié dans des postes critiques), les repos minimaux (risque de sécurité lie à la fatigue) et les absences pré-assignées (obligations contractuelles) doivent rester durs. Si ceux-ci causent un INFEASIBLE, la réponse correcte est de corriger les données d'entrée, pas de relâcher la contrainte.

La couverture a toujours la pénalité la plus élevée

Un poste non couvert est pire que tout problème de qualité. Si le solveur doit choisir entre laisser un poste non couvert (poids maximum) ou faire travailler quelqu'un 7 jours consécutifs (2 000), le bon compromis est toujours de remplir le poste. La hiérarchie des pénalités encode cela automatiquement.

Utiliser le rapport de pénalité comme outil de diagnostic

La décomposition des pénalités indique au planificateur où le planning est le plus faible. Si 80% de la pénalité vient des manques de couverture, le problème est le sous-effectif. Si les pénalités d'équité dominent, les groupes sont peut-être déséquilibrés. Le solveur ne produit pas seulement un planning ; il produit un diagnostic.

Documenter la justification de chaque type de contrainte

Pour chaque contrainte du modèle, notez pourquoi elle est dure ou souple. Quand un planificateur demande "pourquoi l'employé X a-t-il travaille 7 jours d'affilée ?", la réponse doit être traçable : "les jours consécutifs sont souples (pénalité 2 000) car les rendre durs cause des INFEASIBLE pendant les semaines de forte absence. Le solveur a choisi cette violation pour préserver la couverture complète."