Contraintes Dures vs Souples dans CP-SAT

La distinction : interdit vs couteux

Chaque regle dans un modele de planification CP-SAT appartient a l'une de deux categories. Une contrainte dure doit etre satisfaite. Si le solveur ne peut pas trouver de solution qui respecte toutes les contraintes dures simultanement, il retourne INFEASIBLE. Aucun planning n'est produit. Une contrainte souple peut etre violee, mais chaque violation ajoute une penalite a la fonction objectif. Le solveur minimise la penalite 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 modele est : "Que se passe-t-il quand cette regle est violee ?" Si la reponse est "le planning est illegal", la regle est une contrainte dure. Si la reponse est "le planning est sous-optimal mais utilisable", la regle est une contrainte souple.

Se tromper dans cette distinction a des consequences reelles. 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 reglementation. L'art de la modelisation par contraintes est de trouver la bonne frontiere.

Contraintes dures en planification

Les contraintes dures encodent des regles qui ne peuvent etre enfreintes en aucune circonstance. En planification du personnel, ce sont typiquement des exigences legales, des impossibilites physiques ou des engagements pre-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 employe ne peut pas travailler deux shifts le meme jour. C'est une contrainte physique : une personne ne peut pas etre a deux endroits en meme temps. Il n'y a aucun scenario ou violer cette regle est acceptable, donc elle doit etre 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 securite ne peut pas etre affecte a un shift logistique s'il ne detient pas la qualification logistique. C'est une exigence reglementaire. La violer signifie du personnel non qualifie dans des postes critiques pour la securite.

Absences pre-assignees

# 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 employe est en vacances approuvees, le solveur ne peut pas le planifier. Les vacances ont ete convenues avant la generation 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 pre-calculons les "paires toxiques" de shifts qui violeraient la regle des 11 heures et les interdisons. C'est une contrainte legale qui protege la sante et la securite des employes.

Contraintes souples et penalites

Les contraintes souples encodent des objectifs que le solveur doit poursuivre, mais peut sacrifier si necessaire. Chaque violation coute une penalite. Le solveur minimise la somme de toutes les penalites : plus bas = meilleur.

Couverture (penalite : 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 priorite. Un poste non couvert signifie un trou operationnel. Mais rendre la couverture dure signifierait que toute penurie de personnel (vacances, maladie) rend le planning entier INFEASIBLE. La couverture est souple pour que le solveur puisse produire le meilleur planning possible meme quand il n'y a pas assez de monde.

Garantie de weekend (penalite : 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 employe devrait avoir au moins un weekend complet de repos par mois. C'est un objectif de qualite de vie, pas une obligation legale. En periode de pointe, le solveur peut devoir sauter un weekend pour certains employes afin de maintenir la couverture.

Jours consecutifs de travail (penalite : 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 consecutifs est indesirable mais parfois inevitable. C'est le cas classique d'une contrainte qui se situe a la frontiere entre dure et souple (plus de details ci-dessous).

Jours de repos (penalite : 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 employe a un nombre cible de jours de repos base sur son contrat. Le solveur essaie d'atteindre la cible, mais peut etre en dessous si les besoins de couverture l'exigent.

Jours de repos isoles (penalite : 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 isole entre deux jours de travail est moins reposant que des jours de repos consecutifs. Le solveur prefere regrouper les jours de repos.

Equite par qualification (penalite : 500 par unite d'ecart)

# 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 etre distribues equitablement entre les types de qualification. Les employes en conge ou en vacances sont exclus du calcul d'equite.

Equite de charge (penalite : 50 par unite d'ecart)

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

L'objectif de plus basse priorite. Le solveur sacrifiera l'equite de charge pour preserver tout objectif de priorite superieure.

Quand une contrainte dure devient souple

L'exemple classique est celui des jours consecutifs de travail. La loi du travail dit qu'un employe ne devrait pas travailler plus de 6 jours consecutifs. L'instinct est de l'encoder en dur. Mais considerons ce qui se passe lors d'une penurie de personnel.

Imaginons une equipe de 20 employes dont 5 sont en vacances la meme semaine. Les 15 restants doivent couvrir tous les shifts. Avec les jours consecutifs en contrainte dure, le solveur ne peut trouver aucune affectation qui couvre tous les shifts sans que quelqu'un travaille 7 jours d'affilee. Le resultat : INFEASIBLE. Aucun planning du tout.

Maintenant, rendons les jours consecutifs souples avec une penalite de 2 000. Le solveur trouve une solution ou 3 employes travaillent 7 jours consecutifs, mais chaque shift est couvert. Le planificateur voit les violations dans le rapport, comprend le compromis, et decide s'il approuve le planning ou ajuste les donnees d'entree (ex : decaler 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 decision

Utilisez cet arbre de decision mental pour choisir comment encoder une regle :

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 regles de planification tombent dans la categorie "souple avec penalite elevee". Les seules contraintes veritablement dures sont les impossibilites physiques (un shift par jour, qualifications) et les engagements irrevocables (absences pre-assignees, repos impose par la loi sans exception).

Hierarchie des penalites

Les poids de penalite creent un systeme de priorite. Le solveur sacrifiera les objectifs de basse priorite pour preserver ceux de haute priorite. Voici la hierarchie que nous utilisons en production :

Objectif	Poids de penalite	Priorite
Couverture manquante	Tres eleve	Maximale
Pas de weekend garanti	Eleve	Haute
Jours consecutifs > 6	Eleve	Haute
Jours de repos manquants	Moyen	Moyenne
Jour de repos isole	Moyen	Moyenne
Ecart equite par qualification	Faible	Basse
Ecart equite charge de travail	Tres 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 repartition legerement inequitable. La couverture a toujours la penalite la plus elevee car un poste non couvert signifie une defaillance operationnelle, alors que toute autre violation est un probleme de qualite qui peut etre examine et accepte.

Les ecarts entre les niveaux de penalite comptent. La couverture a 10 000 est 2x la penalite weekend a 5 000, ce qui signifie que le solveur sauterait le weekend d'un employe 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 simultanement. Ce n'est jamais cause par les contraintes souples, puisque celles-ci peuvent toujours etre violees.

Causes frequentes

• Trop d'absences + trop peu de personnel qualifie. Si 10 des 12 agents de securite 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 probleme est generalement une combinaison d'absences et de rarete des qualifications.
• Affectations fixes en conflit. Un employe a un FIXED_OFF un jour ou il a aussi un shift obligatoire assigne ailleurs dans les donnees. Deux contraintes dures qui se contredisent directement.
• Impossibilites de repos. La combinaison des horaires de shifts et des repos obligatoires rend impossible la creation d'une sequence valide pour certains employes.

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 penalite elevee. La deuxieme plus courante est d'ajuster les donnees d'entree (moins d'absences simultanees, affectations de qualifications differentes).

Exemple concret

Un planificateur saisit 15 employes en vacances la meme semaine. L'operation compte 40 employes au total repartis sur 4 groupes fonctionnels. Les besoins journaliers necessitent 25 employes en poste chaque jour.

Scenario A : toutes les contraintes dures

Avec les jours consecutifs en contrainte dure (max 6), le solveur retourne INFEASIBLE. Les 25 employes 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.

Scenario B : jours consecutifs en souple

Avec les jours consecutifs en contrainte souple (penalite 2 000), le solveur trouve une solution. 3 employes travaillent 7 jours consecutifs. Tous les shifts sont couverts. Le rapport de penalite 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 employes vont travailler 7 jours d'affilee. Il peut maintenant prendre une decision eclairee : approuver le planning tel quel, deplacer des vacances sur une autre semaine, ou faire appel a un interimaire. Le solveur lui a donne une base utilisable et une image claire des compromis.

Principes de conception

Commencer avec tout en dur

Commencez votre modele avec toutes les regles en contraintes dures. Lancez le solveur sur des donnees realistes. S'il retourne FEASIBLE, c'est termine. S'il retourne INFEASIBLE, vous savez exactement quelles regles doivent devenir souples.

Convertir en souple une regle a la fois

Face a un INFEASIBLE, ne convertissez pas toutes les contraintes en souples d'un coup. Identifiez les regles "flexibles", celles ou une violation est indesirable mais pas catastrophique, et convertissez-les une par une. Testez apres chaque conversion.

Ne jamais rendre souples les contraintes de securite ou legales

Le respect des qualifications (personnel non qualifie dans des postes critiques), les repos minimaux (risque de securite lie a la fatigue) et les absences pre-assignees (obligations contractuelles) doivent rester durs. Si ceux-ci causent un INFEASIBLE, la reponse correcte est de corriger les donnees d'entree, pas de relacher la contrainte.

La couverture a toujours la penalite la plus elevee

Un poste non couvert est pire que tout probleme de qualite. Si le solveur doit choisir entre laisser un poste non couvert (poids maximum) ou faire travailler quelqu'un 7 jours consecutifs (2 000), le bon compromis est toujours de remplir le poste. La hierarchie des penalites encode cela automatiquement.

Utiliser le rapport de penalite comme outil de diagnostic

La decomposition des penalites indique au planificateur ou le planning est le plus faible. Si 80% de la penalite vient des manques de couverture, le probleme est le sous-effectif. Si les penalites d'equite dominent, les groupes sont peut-etre desequilibres. Le solveur ne produit pas seulement un planning ; il produit un diagnostic.

Documenter la justification de chaque type de contrainte

Pour chaque contrainte du modele, notez pourquoi elle est dure ou souple. Quand un planificateur demande "pourquoi l'employe X a-t-il travaille 7 jours d'affilee ?", la reponse doit etre tracable : "les jours consecutifs sont souples (penalite 2 000) car les rendre durs cause des INFEASIBLE pendant les semaines de forte absence. Le solveur a choisi cette violation pour preserver la couverture complete."