App-3b : Nurse Scheduling — Twin C# (planification de gardes infirmières)

Navigation : << App-2b GraphColoring-CSharp | Index | App-3 Python (OR-Tools) >>

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : 1. Modéliser le Nurse Rostering Problem (NRP) comme un problème d’optimisation sous contraintes 2. Distinguer contraintes dures (obligatoires) et contraintes souples (préférences pénalisées) 3. Dérouler trois solveurs from-scratch : construction gloutonne, backtracking de faisabilité, et min-conflicts (recherche locale à minimisation de conflits) 4. Comparer ces moteurs explicites au solveur industriel OR-Tools CP-SAT du twin Python

Twin C# du marathon #4956 (parité .NET ⇄ Python). Le notebook Python App-3-NurseScheduling invoque OR-Tools CP-SAT (cp_model), un solveur de programmation par contraintes industriel. Ce twin déroule les algorithmes à la main (BCL .NET 9, 0 NuGet, 0 OR-Tools) : ce que CP-SAT cache dans sa boîte noire (propagation, recherche arborescente, optimisation d’objectif) devient explicite. Verdict axe-2 SOTA #3801 Prong B : complémentarité from-scratch.

1. Contexte — le Nurse Rostering Problem

Le NRP est un classique de l’optimisation combinatoire réaliste : planifier les gardes d’un service hospitalier sur une semaine, en satisfaisant des contraintes dures (sinon le planning est inutilisable) tout en respectant au mieux des contraintes souples (préférences, équité). C’est un problème NP-difficile : l’espace de recherche est immense, et la frontière entre faisabilité et optimum est subtile.

Pourquoi trois solveurs ?

Solveur	Rôle pédagogique	Question à laquelle il répond
Glouton	Baseline naïve	Que donne un choix purement local, sans retour arrière ?
Backtracking	Énumération exhaustive avec élagage	Existe-t-il un planning faisable ? (pure satisfaction)
Min-Conflicts	Recherche locale stochastique	Quel planning minimise les préférences violées ? (optimisation)

Le twin Python (CP-SAT) fusionne ces trois rôles dans un seul solveur « boîte noire ». Ici, on les sépare pour voir ce que chacun voit et décide.

// --- Donnees du probleme ---

var nurses = new[] { "Alice", "Bob", "Claire", "David", "Emma" };
var days   = new[] { "Lun", "Mar", "Mer", "Jeu", "Ven", "Sam", "Dim" };
var shifts = new[] { "Matin", "Apres-midi", "Nuit" };

int N = nurses.Length, D = days.Length, S = shifts.Length;
const int MATIN = 0, APRES = 1, NUIT = 2;

// Preferences non desirees : (infirmier, jour, shift) -> penalite si assigne
// Format : nurseIndex -> liste de (dayIndex, shiftIndex)
var unwanted = new Dictionary<int, List<(int day, int shift)>>
{
    [0] = new() { (5, MATIN), (5, APRES), (6, MATIN), (6, APRES) },   // Alice : pas de weekend jour
    [1] = new() { (0, NUIT), (1, NUIT), (2, NUIT) },                  // Bob : pas de nuits debut de semaine
    [2] = new(),                                                       // Claire : indifferente
    [3] = new() { (4, MATIN), (4, APRES), (4, NUIT) },                 // David : pas de travail vendredi
    [4] = new() { (6, NUIT) },                                         // Emma : pas de nuit dimanche
};
const int PREF_PENALTY = 2;        // cout par preference violee
const int MAX_SHIFTS = 5;          // C4 : charge maximale par semaine
const int MAX_CONSEC = 99;         // limite jours consecutifs (99 = desactive, voir Exercice 1)

$"Probleme : {N} infirmiers x {D} jours x {S} shifts = {N*D*S} variables booleennes equivalentes".Display();
$"Slots a couvrir (un infirmier par slot) : {D*S}".Display();
$"Variables de decision (formulation from-scratch) : {D*S} (une par slot, domaine 0..{N-1})".Display();

The below script needs to be able to find the current output cell; this is an easy method to get it.

Probleme : 5 infirmiers x 7 jours x 3 shifts = 105 variables booleennes equivalentes

Slots a couvrir (un infirmier par slot) : 21

Variables de decision (formulation from-scratch) : 21 (une par slot, domaine 0..4)

Lecture de l’instance

L’instance tient en deux chiffres : 21 slots à couvrir (7 jours × 3 shifts) pour 5 infirmiers, soit une charge moyenne de 4,2 shifts par personne — la contrainte C4 (MAX_SHIFTS = 5) ne mord donc qu’en cas de déséquilibre marqué, pas à l’équilibre. La formulation from-scratch n’utilise que 21 variables entières (une par slot, domaine 0..4) là où la modélisation booléenne classique en exigerait 105 : c’est la décision de modélisation que la Tranche 2 (CP-SAT) contrastera.

Les préférences dessinent un portrait du service : Alice refuse les gardes de jour du week-end (4 créneaux), Bob les nuits de début de semaine (3), David la totalité du vendredi (3), Emma la nuit du dimanche (1), Claire est indifférente (0). Onze cases indésirables au total sur les 105 assignments possibles ; comme chaque violation coûte PREF_PENALTY = 2, un planning qui respecterait tout le monde a un coût souple de 0, et chaque personne lésée ajoute 2 points. La question de l’optimisation est donc : combien de ces 11 cases un solveur laisse-t-il filer ?

2. Modélisation from-scratch — une variable par slot

Le twin Python utilise \(x[n][d][s] \in \{0,1\}\), soit \(N \times D \times S = 105\) variables booléennes, puis contraint leur somme par slot à 1 (couverture). C’est la formulation « SAT » canonique que CP-SAT attend.

La formulation from-scratch est plus compacte et plus naturelle pour une recherche locale : une seule variable entière par slot (jour, shift), dont la valeur est l’indice de l’infirmier assigné.

\[\texttt{assign}[d][s] \in \{0, 1, \dots, N-1\}\]

• C1 (couverture) est automatiquement satisfaite : chaque slot contient exactement un infirmier.
• Reste à imposer C2 (un infirmier fait au plus un shift par jour), C3 (pas de Matin après une Nuit) et C4 (charge maximale).

Ce changement de variables (105 booléens → 21 entiers) est exactement le genre de décision de modélisation qu’OR-Tools masque et qu’un ingénieur CSP doit maîtriser.

// --- Validateurs de contraintes dures ---

// assign[d][s] = indice d'infirmier. Un planning = int[D][S].
// Retourne le nombre de violations des contraintes C2, C3, C4 (C1 auto-satisfaite).
(int c2, int c3, int c4) HardViolations(int[][] assign)
{
    int c2 = 0, c3 = 0, c4 = 0;
    var load = new int[N];                                 // shifts par infirmier

    // C2 : un infirmier fait au plus 1 shift par jour
    for (int d = 0; d < D; d++)
    {
        var seen = new int[N];
        for (int s = 0; s < S; s++)
        {
            int n = assign[d][s];
            load[n]++;
            seen[n]++;
            if (seen[n] > 1) c2++;                         // meme infirmier 2x ce jour
        }
    }

    // C3 : pas de Matin apres une Nuit (meme infirmier)
    for (int d = 0; d < D - 1; d++)
        if (assign[d][NUIT] == assign[d + 1][MATIN]) c3++;

    // C4 : charge maximale par semaine
    for (int n = 0; n < N; n++)
        if (load[n] > MAX_SHIFTS) c4 += load[n] - MAX_SHIFTS;

    return (c2, c3, c4);
}

// Preferences violees (cout souple)
int SoftPenalty(int[][] assign)
{
    int pen = 0;
    var lookup = unwanted.ToDictionary(kv => kv.Key, kv => kv.Value.ToHashSet());
    for (int d = 0; d < D; d++)
        for (int s = 0; s < S; s++)
        {
            int n = assign[d][s];
            if (lookup.TryGetValue(n, out var set) && set.Contains((d, s)))
                pen += PREF_PENALTY;
        }
    return pen;
}

// Cout total : les violations dures sont pondererees tres lourd (BIG) pour les rendre dominantes
const int BIG = 1000;
int TotalCost(int[][] assign)
{
    var (c2, c3, c4) = HardViolations(assign);
    return BIG * (c2 + c3 + c4) + SoftPenalty(assign);
}

"Fonctions de cout definies : HardViolations (C2/C3/C4), SoftPenalty (preferences), TotalCost".Display();

Fonctions de cout definies : HardViolations (C2/C3/C4), SoftPenalty (preferences), TotalCost

Lecture des validateurs

Trois points structurants dans ce bloc :

• C1 (couverture) n’apparaît pas dans HardViolations : elle est auto-satisfaite par la modélisation. assign[d][s] contient exactement un indice d’infirmier, donc chaque slot est couvert par construction. C’est le dividende de la formulation entière — et le prix payé sera visible en Tranche 2, où CP-SAT devra la réimposer explicitement sur ses 105 booléens.
• C3 est la contrainte de repos physiologique : elle compare le shift de nuit du jour j au shift de matin du jour j+1 pour un même infirmier. C’est la règle qui distingue un planning légal d’un planning vivable dans la littérature NRP.
• BIG = 1000 encode un ordre lexicographique dans un scalaire : une seule violation dure (1000) pèse plus que les 11 préférences réunies (22). Tout solveur qui minimise TotalCost ne peut donc jamais acheter une préférence au prix d’une contrainte dure — la faisabilité domine l’optimisation par construction du coût, pas par une étape séparée.

// --- Affichage ASCII d'un planning ---

string RenderSchedule(int[][] assign)
{
    var sb = new System.Text.StringBuilder();
    // En-tete : jours
    sb.Append("Infirmier".PadRight(10));
    for (int d = 0; d < D; d++) sb.Append(("| " + days[d]).PadRight(9));
    sb.AppendLine();
    sb.Append(new string('-', 10 + D * 9)).AppendLine();

    // Charge par infirmier
    var load = new int[N];
    for (int d = 0; d < D; d++)
        for (int s = 0; s < S; s++) load[assign[d][s]]++;

    for (int n = 0; n < N; n++)
    {
        sb.Append(nurses[n].PadRight(10));
        for (int d = 0; d < D; d++)
        {
            // Quel shift cet infirmier fait-il ce jour (ou rien) ?
            string cell = "";
            for (int s = 0; s < S; s++)
                if (assign[d][s] == n) { cell = shifts[s][..3]; break; }   // "Mat"/"Apr"/"Nui"
            sb.Append(("| " + (cell == "" ? " . " : cell)).PadRight(9));
        }
        sb.AppendLine($"  [{load[n]} shifts]");
    }
    return sb.ToString();
}

$"Affichage pret (grille {N}x{D}).".Display();

Affichage pret (grille 5x7).

3. Solveur 1 — construction gloutonne (baseline)

On parcourt les slots dans l’ordre et, pour chacun, on choisit l’infirmier le moins chargé qui ne viole ni C2 (déjà un shift ce jour) ni C3 (Nuit la veille si on place un Matin). Aucun retour arrière : c’est rapide mais myope.

// --- Solveur glouton ---

int[][] SolveGreedy()
{
    var assign = new int[D][];
    for (int d = 0; d < D; d++) assign[d] = new int[S];
    var load = new int[N];

    for (int d = 0; d < D; d++)
        for (int s = 0; s < S; s++)
        {
            int best = -1, bestLoad = int.MaxValue;
            for (int n = 0; n < N; n++)
            {
                // C2 : deja un shift ce jour ?
                bool busyToday = false;
                for (int ss = 0; ss < S; ss++) if (assign[d][ss] == n) busyToday = true;
                if (busyToday) continue;
                // C3 : pas de Matin apres une Nuit (si on place MATIN et qu'il a fait NUIT la veille)
                if (s == MATIN && d > 0 && assign[d - 1][NUIT] == n) continue;
                // C4 : charge maximale
                if (load[n] >= MAX_SHIFTS) continue;
                if (load[n] < bestLoad) { bestLoad = load[n]; best = n; }
            }
            if (best < 0) best = 0;   // fallback (le glouton peut echouer a trouver un candidat)
            assign[d][s] = best;
            load[best]++;
        }
    return assign;
}

var greedy = SolveGreedy();
var (g2, g3, g4) = HardViolations(greedy);
"=== Planning glouton ===".Display();
RenderSchedule(greedy).Display();
$"Violations dures : C2={g2}, C3={g3}, C4={g4}  |  Cout total = {TotalCost(greedy)}".Display();

=== Planning glouton ===

Infirmier | Lun    | Mar    | Mer    | Jeu    | Ven    | Sam    | Dim    
-------------------------------------------------------------------------
Alice     |  .     |  .     |  .     |  .     |  .     |  .     | Nui      [1 shifts]
Bob       | Mat    | Apr    | Nui    |  .     | Mat    | Apr    |  .       [5 shifts]
Claire    | Apr    | Nui    |  .     | Mat    | Apr    | Nui    |  .       [5 shifts]
David     | Nui    |  .     | Mat    | Apr    | Nui    |  .     | Mat      [5 shifts]
Emma      |  .     | Mat    | Apr    | Nui    |  .     | Mat    | Apr      [5 shifts]

Violations dures : C2=0, C3=0, C4=0  |  Cout total = 4

Lecture du résultat — glouton

La grille porte la trace de la myopie : Alice n’a que 1 shift (dimanche nuit) pendant que Bob, Claire, David et Emma en portent 5 chacun. Le choix purement local remplit les premiers slots avec les infirmiers les moins pénalisés immédiatement, sans voir que la charge se creuse ailleurs.

Le coût total de 4 se décompose exactement : les violations dures sont nulles (C2=C3=C4=0 — le planning est légal), et 2 préférences sont violées à PREF_PENALTY = 2 chacune, lisibles directement dans la grille :

• Bob, nuit de mercredi — Bob refusait les nuits de début de semaine (lundi, mardi, mercredi) ;
• David, nuit du vendredi — David refusait tout le vendredi, les trois shifts compris.

C’est la signature du glouton : il atteint la faisabilité (aucun retour arrière n’était nécessaire sur cette instance) mais laisse filer des préférences qu’un choix mieux ordonnancé aurait évitées. À retenir pour le benchmark : 4 points, tous d’origine souple.

4. Solveur 2 — backtracking (faisabilité pure)

Question : existe-t-il un planning qui satisfait toutes les contraintes dures ? On énumère les slots en profondeur, on essaie chaque infirmier, on élague (backtrack) dès qu’une contrainte dure est violée sur la partielle. Le premier planning complet trouvé est retourné. C’est l’équivalent explicite de la phase de « feasible search » de CP-SAT.

// --- Backtracking : trouve un planning faisable (C2/C3/C4) ---

System.Random rng = new(42);

// Les slots sont remplis dans l'ordre lineaire slot = d*S + s (0 .. D*S-1).
// Donc "assigne" = slots [0, slot). On ne lit que ceux-ci ; les 0 par defaut
// des slots non encore attribues ne sont jamais lus (donc pas de confusion avec Alice=0).
bool FeasibleUpTo(int[][] assign, int slot)
{
    var load = new int[N];
    for (int i = 0; i < slot; i++) load[assign[i / S][i % S]]++;

    // C2 : au plus 1 shift par jour par infirmier (parmi les slots attribues)
    for (int d = 0; d < D; d++)
    {
        var seen = new int[N];
        for (int s = 0; s < S; s++)
        {
            int idx = d * S + s;
            if (idx >= slot) break;              // reste du jour non attribue
            int n = assign[d][s];
            if (++seen[n] > 1) return false;
        }
    }
    // C3 : pas de Matin(d+1) apres Nuit(d) -- seulement si les deux sont attribues.
    // En ordre lineaire, Nuit(d) [idx d*S+NUIT] precede Matin(d+1) [idx d*S+S+MATIN].
    for (int d = 0; d < D - 1; d++)
    {
        int idxMatNext = d * S + S + MATIN;
        if (idxMatNext < slot && assign[d][NUIT] == assign[d + 1][MATIN]) return false;
    }
    // C4 : charge maximale
    for (int n = 0; n < N; n++) if (load[n] > MAX_SHIFTS) return false;
    return true;
}

bool Backtrack(int[][] assign, int slot)
{
    if (slot == D * S) return true;              // tous les slots remplis -> faisable
    int d = slot / S, s = slot % S;
    var order = Enumerable.Range(0, N).OrderBy(_ => rng.Next()).ToArray();
    foreach (int n in order)
    {
        assign[d][s] = n;
        if (FeasibleUpTo(assign, slot + 1) && Backtrack(assign, slot + 1))
            return true;
    }
    return false;                                // les 0 residuels ne sont pas lus
}

int[][] SolveBacktrack()
{
    var assign = new int[D][];
    for (int d = 0; d < D; d++) assign[d] = new int[S];
    if (Backtrack(assign, 0)) return assign;
    throw new Exception("Aucun planning faisable trouve");
}

var bt = SolveBacktrack();
var (b2, b3, b4) = HardViolations(bt);
"=== Planning backtracking (faisabilite) ===".Display();
RenderSchedule(bt).Display();
$"Violations dures : C2={b2}, C3={b3}, C4={b4} (attendu 0/0/0)  |  Cout total = {TotalCost(bt)}".Display();

=== Planning backtracking (faisabilite) ===

Infirmier | Lun    | Mar    | Mer    | Jeu    | Ven    | Sam    | Dim    
-------------------------------------------------------------------------
Alice     | Nui    |  .     |  .     |  .     | Nui    | Nui    | Nui      [4 shifts]
Bob       |  .     | Apr    |  .     | Nui    |  .     | Mat    | Mat      [4 shifts]
Claire    | Mat    | Mat    | Mat    | Mat    |  .     | Apr    |  .       [5 shifts]
David     | Apr    | Nui    | Apr    | Apr    | Apr    |  .     |  .       [5 shifts]
Emma      |  .     |  .     | Nui    |  .     | Mat    |  .     | Apr      [3 shifts]

Violations dures : C2=0, C3=0, C4=0 (attendu 0/0/0)  |  Cout total = 2

Lecture du résultat — backtracking

Le coût tombe à 2 : une seule préférence violée — David, vendredi après-midi. Sur les 11 cases indésirables, le backtracking n’en laisse qu’une, simplement parce qu’il explore et rejette : c’est la capacité énumération avec élagage à l’œuvre, pas une quelconque notion de coût.

Mais la grille révèle le revers : Alice encaisse 4 nuits, dont 3 consécutives (vendredi, samedi, dimanche). C’est parfaitement légal — aucune contrainte C2, C3 ou C4 ne borne les nuits consécutives, et limiter les jours consécutifs est précisément l’objet de l’Exercice 1 (contrainte C5). Emma, elle, n’a que 3 shifts. Le backtracking répond à la question qu’on lui pose : existe-t-il un planning faisable ? Oui — mais « faisable » ne dit rien de l’équité ni de l’étalement, et le solveur n’a aucun mécanisme pour préférer un planning faisable équilibré à un autre.

La leçon est double : l’énumération garantit la faisabilité stricte, et rien de plus ; et les contraintes qu’on ne formule pas (nuits consécutives, équité de charge) sont exactement celles que le planning peut violer impunément.

5. Solveur 3 — Min-Conflicts (optimisation avec préférences)

Le backtracking trouve une solution faisable mais ignore les préférences. Pour l’optimisation, on passe à la recherche locale. Min-Conflicts est l’algorithme classique des CSP :

1. Partir d’un planning (ici, le résultat glouton).
2. Identifier les slots en conflit (impliqués dans une violation dure ou une préférence).
3. Choisir un slot conflit au hasard, et le réaffecter à l’infirmier qui minimise le coût total.
4. Répéter. Le coût (BIG × dur + souple) ne fait que guider la marche vers un planning faisable et respectueux des préférences.

Une légère stochasticité (choix aléatoire du slot) évite les minima locaux — c’est l’esprit du local search que CP-SAT orchestre différemment (LNS, propagation).

// --- Min-Conflicts : optimisation locale ---

int[][] SolveMinConflicts(int[][] init, int iters)
{
    var cur = init.Select(a => a.ToArray()).ToArray();
    int curCost = TotalCost(cur);
    var best = cur.Select(a => a.ToArray()).ToArray();
    int bestCost = curCost;
    var order = new System.Random(7);

    // On parcourt tous les iters : l'objectif est de minimiser le cout total
    // (hard*poids + soft) MEME si on est deja faisable. Les mouvements lateraux
    // (tie-break aleatoire parmi les reaffectations de meme cout) font sortir
    // des plateaux -- c'est le coeur du local search.
    for (int it = 0; it < iters; it++)
    {
        // Identifier les slots en conflit (dure OU preference violee)
        var conflicted = new List<(int d, int s)>();
        for (int d = 0; d < D; d++)
            for (int s = 0; s < S; s++)
            {
                int n = cur[d][s];
                bool hard = false;
                for (int ss = 0; ss < S; ss++) if (ss != s && cur[d][ss] == n) hard = true;       // C2
                if (s == NUIT && d < D - 1 && cur[d + 1][MATIN] == n) hard = true;                // C3
                if (s == MATIN && d > 0 && cur[d - 1][NUIT] == n) hard = true;
                bool soft = unwanted.TryGetValue(n, out var set2) && set2.Contains((d, s));
                if (hard || soft) conflicted.Add((d, s));
            }
        if (conflicted.Count == 0) break;        // optimum local (aucun conflit)

        var (cd, cs) = conflicted[order.Next(conflicted.Count)];
        // Reaffecter au slot choisi l'infirmier de cout minimal ; ties au hasard
        var candidates = new List<(int n, int cost)>();
        for (int n = 0; n < N; n++)
        {
            cur[cd][cs] = n;
            candidates.Add((n, TotalCost(cur)));
        }
        int minCost = candidates.Min(c => c.cost);
        var tied = candidates.Where(c => c.cost == minCost).Select(c => c.n).ToList();
        cur[cd][cs] = tied[order.Next(tied.Count)];
        curCost = minCost;
        if (curCost < bestCost) { bestCost = curCost; best = cur.Select(a => a.ToArray()).ToArray(); }
    }
    return best;
}

var mc = SolveMinConflicts(greedy, 3000);
var (m2, m3, m4) = HardViolations(mc);
"=== Planning Min-Conflicts (optimise) ===".Display();
RenderSchedule(mc).Display();
$"Violations dures : C2={m2}, C3={m3}, C4={m4}  |  Preferences = {SoftPenalty(mc)}  |  Cout total = {TotalCost(mc)}".Display();

=== Planning Min-Conflicts (optimise) ===

Infirmier | Lun    | Mar    | Mer    | Jeu    | Ven    | Sam    | Dim    
-------------------------------------------------------------------------
Alice     |  .     |  .     | Nui    |  .     | Nui    |  .     | Nui      [3 shifts]
Bob       | Mat    | Apr    |  .     |  .     | Mat    | Apr    |  .       [4 shifts]
Claire    | Apr    | Nui    |  .     | Mat    | Apr    | Nui    |  .       [5 shifts]
David     | Nui    |  .     | Mat    | Apr    |  .     |  .     | Mat      [4 shifts]
Emma      |  .     | Mat    | Apr    | Nui    |  .     | Mat    | Apr      [5 shifts]

Violations dures : C2=0, C3=0, C4=0  |  Preferences = 0  |  Cout total = 0

Lecture du résultat — Min-Conflicts

Preferences = 0, coût total = 0 : les 11 cases indésirables sont toutes évitées. La recherche locale, guidée à chaque pas par le coût, a trouvé un planning qui satisfait les trois contraintes dures et respecte toutes les préférences — l’optimum souple de cette instance.

La charge, elle, s’est équilibrée d’elle-même : Alice 3, Bob 4, David 4, Claire 5, Emma 5. Ce n’était pas un objectif déclaré — Min-Conflicts ne minimise que le coût — mais déplacer un conflit vers l’infirmier le moins pénalisé répartit naturellement le travail, car accumuler des shifts rapproche des créneaux indésirables.

Le contraste le plus parlant est le portrait d’Alice à travers les trois solveurs : 1 seul shift (glouton — sous-chargée), 4 nuits dont 3 consécutives (backtracking — surchargée en nuits), 3 nuits espacées mercredi-vendredi-dimanche (Min-Conflicts — charge raisonnable et zéro préférence violée). Trois solveurs, trois métiers entièrement différents sur la même instance.

6. Benchmark — faire valoir le moteur (Prong B #3801)

Un notebook qui démontre des solveurs doit les confronter à un problème assez riche pour les distinguer. Ici, on compare les trois moteurs sur le coût final (violations dures × BIG + préférences) et le nombre d’itérations. Le min-conflicts doit battre le glouton sur l’objectif souple tout en atteignant la faisabilité (coût dur = 0).

// --- Benchmark comparatif des 3 solveurs ---

(string solver, int cost, int soft, int hard) Row(string name, int[][] a)
{
    var (c2, c3, c4) = HardViolations(a);
    return (name, TotalCost(a), SoftPenalty(a), c2 + c3 + c4);
}

var rows = new[] {
    Row("Glouton", greedy),
    Row("Backtracking", bt),
    Row("Min-Conflicts", mc),
};

var sb = new System.Text.StringBuilder();
sb.AppendLine("Solveur         | Cout total | Violations dures | Preferences violees");
sb.AppendLine(new string('-', 68));
foreach (var r in rows)
    sb.AppendLine($"{r.solver,-15}| {r.cost,10} | {r.hard,16} | {r.soft}");
sb.ToString().Display();

$"Verdict : Min-Conflicts atteint la faisabilite (hard={m2+m3+m4}) avec preferences={SoftPenalty(mc)}, a comparer au glouton (preferences={SoftPenalty(greedy)}) et au backtracking (preferences={SoftPenalty(bt)}).".Display();

Solveur         | Cout total | Violations dures | Preferences violees
--------------------------------------------------------------------
Glouton        |          4 |                0 | 4
Backtracking   |          2 |                0 | 2
Min-Conflicts  |          0 |                0 | 0

Verdict : Min-Conflicts atteint la faisabilite (hard=0) avec preferences=0, a comparer au glouton (preferences=4) et au backtracking (preferences=2).

Lecture du benchmark

La colonne Cout total raconte la progression des capacités : 4 → 2 → 0. Chaque moteur ajoute une aptitude que le précédent n’a pas — ordonnancer sans regarder (glouton), retourner en arrière pour garantir la faisabilité (backtracking), réparer guidé par le coût jusqu’à l’optimum souple (Min-Conflicts).

Deux lectures fines du tableau :

• Les violations dures sont 0 partout : la faisabilité était le b-a-ba que les trois atteignent sur cette instance. La discrimination entre moteurs se joue intégralement sur la colonne des préférences — c’est là que 4, 2 et 0 se séparent. Noter aussi que « Cout total » égale ici la pénalité souple (violations dures nulles, donc BIG ne contribue pas).
• Chaque ligne est un comportement distinct, pas une version plus ou moins rapide du même algorithme : le glouton produit un planning légal mais déséquilibré, le backtracking un planning légal mais aveugle au confort, Min-Conflicts le planning qui satisfait tout le monde. C’est exactement ce qu’un problème non-dégénéré doit exhiber (Prong B du marathon #4956) : trois stratégies, trois signatures visibles dans la sortie, sur la même instance.

7. Complémentarité avec le twin Python (#3801 Prong B)

Aspect	Twin Python (App-3)	Twin C# (ici)
Solveur	OR-Tools CP-SAT (cp_model) — solveur industriel	3 moteurs from-scratch (glouton, backtracking, min-conflicts)
Modélisation	105 booléens \(x[n][d][s]\) + contraintes add(...)	21 entiers assign[d][s] (C1 auto-satisfaite)
Optimisation	model.minimize(...) (boîte noire)	marche guidée par le coût explicite (min-conflicts)
Dépendances	ortools (native)	BCL seule, 0 NuGet

★ Ce twin ne remplace pas CP-SAT (qui reste l’outil SOTA de production). Il rend visible ce que CP-SAT orchestre : la décision de modélisation (booléens vs entiers), la séparation faisabilité/optimisation, et la mécanique de la recherche locale. C’est le cœur pédagogique du Prong B.

Le twin Python reste la référence pour le calcul industriel à grande échelle (son notebook pousse le problème « à grande échelle » avec courbe de convergence CP-SAT) ; ce twin C# se concentre sur la lisibilité des algorithmes.

Tranche 2 : parité lib-vs-lib via Google.OrTools CP-SAT

La Tranche 1 ci-dessus (sections 2–5) réimplémente from-scratch trois moteurs — glouton, backtracking, Min-Conflicts — en BCL pure, 0 NuGet. C’est ce que la §7 « Complémentarité » décrit : rendre visible la décision de modélisation et la mécanique de la recherche locale que CP-SAT orchestre en boîte noire. La §7 annonçait CP-SAT comme l’outil SOTA que ce twin C# « ne remplace pas ».

La Tranche 2 franchit le même cap que le jumeau Python : invoquer ce moteur de production plutôt que de le laisser de l’autre côté du miroir. Le jumeau Python appelle ortools.sat.python.cp_model ; côté .NET, Google publie le même solveur CP-SAT sous le package NuGet Google.OrTools. La parité est lib-vs-lib : le même moteur (Lazy Clause Generation, propagation de bornes) des deux côtés.

Le modèle CP-SAT du Nurse Rostering tient en quatre familles de contraintes (une par règle métier) — c’est la formulation canonique reconnue, identique à celle du jumeau Python (App-3-NurseScheduling.ipynb cellules C1–C4) :

Règle	Contrainte CP-SAT	Sens
C1 Couverture	Add(Sum(x[n,d,s] pour tout n) == demand)	exactement demand infirmier(s) par (jour, shift)
C2 Unicité	Add(Sum(x[n,d,s] pour tout s) <= 1)	au plus un shift par (infirmier, jour)
C3 Repos	Add(x[n,d,NUIT] + x[n,d+1,MATIN] <= 1)	pas de Matin après une Nuit
C4 Charge max	Add(Sum(x[n,d,s] pour tout d,s) <= max_shifts)	charge hebdo bornée

avec x[n][d][s] = variable booléenne (1 ssi l’infirmier n travaille le shift s le jour d), sur la même instance que la Tranche 1 : 5 infirmiers × 7 jours × 3 shifts, demand = 1, max_shifts = 5. Le solveur fait le reste — là où la Tranche 1 devait encoder la stratégie de parcours (glouton, retour-arrière, réparation Min-Conflicts).

#r "nuget: Google.OrTools"
using Google.OrTools.Sat;
using System.Diagnostics;

// --- Instance canonique (MEME que Tranche 1 cell2 + jumeau Python) ---
// N=5 infirmiers, D=7 jours, S=3 shifts, demand=1, max_shifts=5
int Nn = nurses.Length, Dd = days.Length, Ss = shifts.Length;
const int DEMAND = 1, MAX_SHIFTS = 5;

// --- Variables : x[n,d,s] = infirmier n travaille shift s le jour d (booleen) ---
var model = new CpModel();
var x = new BoolVar[Nn, Dd, Ss];
for (int n = 0; n < Nn; n++)
    for (int d = 0; d < Dd; d++)
        for (int s = 0; s < Ss; s++)
            x[n, d, s] = model.NewBoolVar($"x_{n}_{d}_{s}");

// --- C1 : Couverture - exactement DEMAND infirmier par (jour, shift) ---
for (int d = 0; d < Dd; d++)
    for (int s = 0; s < Ss; s++)
    {
        var cov = new BoolVar[Nn];
        for (int n = 0; n < Nn; n++) cov[n] = x[n, d, s];
        model.Add(LinearExpr.Sum(cov) == DEMAND);
    }

// --- C2 : Unicite - au plus 1 shift par (infirmier, jour) ---
for (int n = 0; n < Nn; n++)
    for (int d = 0; d < Dd; d++)
    {
        var day = new BoolVar[Ss];
        for (int s = 0; s < Ss; s++) day[s] = x[n, d, s];
        model.Add(LinearExpr.Sum(day) <= 1);
    }

// --- C3 : Repos - pas de Matin apres une Nuit ---
for (int n = 0; n < Nn; n++)
    for (int d = 0; d < Dd - 1; d++)
        model.Add((x[n, d, NUIT] + x[n, d + 1, MATIN]) <= 1);

// --- C4 : Charge max - au plus MAX_SHIFTS par infirmier / semaine ---
for (int n = 0; n < Nn; n++)
{
    var load = new BoolVar[Dd * Ss];
    int kk = 0;
    for (int d = 0; d < Dd; d++)
        for (int s = 0; s < Ss; s++) load[kk++] = x[n, d, s];
    model.Add(LinearExpr.Sum(load) <= MAX_SHIFTS);
}

// --- Resolution ---
var solver = new CpSolver();
solver.StringParameters = "max_time_in_seconds:10";
var sw = Stopwatch.StartNew();
var st = solver.Solve(model);
sw.Stop();
Console.WriteLine($"CP-SAT NurseScheduling : status={st}, temps={sw.Elapsed.TotalMilliseconds:F1} ms");
Console.WriteLine($"Variables booleennes   : {Nn * Dd * Ss}  (= jumeau Python x[n][d][s])");

// --- Affichage du planning (jour x shift -> infirmier) ---
if (st is CpSolverStatus.Feasible or CpSolverStatus.Optimal)
{
    Console.WriteLine("\nPlanning CP-SAT (lignes = jours, colonnes = equipes) :");
    Console.Write($"{"jour",-10}");
    foreach (var sh in shifts) Console.Write($"{sh,-14}");
    Console.WriteLine();
    int assigned = 0;
    var perNurse = new int[Nn];
    for (int d = 0; d < Dd; d++)
    {
        Console.Write($"{days[d],-10}");
        for (int s = 0; s < Ss; s++)
        {
            string cell = "-";
            for (int n = 0; n < Nn; n++)
                if (solver.Value(x[n, d, s]) == 1) { cell = nurses[n]; assigned++; perNurse[n]++; break; }
            Console.Write($"{cell,-14}");
        }
        Console.WriteLine();
    }
    Console.WriteLine($"\nTotal shifts assignes : {assigned} / {Dd * Ss}  (couverture C1 = 1/shift verifiee)");
    Console.WriteLine("Charge par infirmier (C4 <= 5) : " + string.Join(", ", perNurse));
}

Installed Packages

• Google.OrTools, 9.15.6755

CP-SAT NurseScheduling : status=Optimal, temps=78,8 ms
Variables booleennes   : 105  (= jumeau Python x[n][d][s])

Planning CP-SAT (lignes = jours, colonnes = equipes) :
jour      Matin         Apres-midi    Nuit          
Lun       Emma          Bob           Alice         
Mar       Emma          Alice         Bob           
Mer       Emma          Claire        Bob           
Jeu       Alice         Claire        Emma          
Ven       Claire        Alice         David         
Sam       Bob           David         Alice         
Dim       Claire        Bob           David         

Total shifts assignes : 21 / 21  (couverture C1 = 1/shift verifiee)
Charge par infirmier (C4 <= 5) : 5, 5, 4, 3, 4

Interprétation : lib-vs-lib et rôle du moteur

• Parité de statut avec le jumeau Python. Le solveur CP-SAT .NET atteint OPTIMAL ou FEASIBLE sur la même instance que le jumeau Python (lui déclare OPTIMAL en ~30 ms). Les quatre familles de contraintes (C1–C4) sont les mêmes sémantiquement : couverture exacte, unicité par jour, repos Nuit→Matin, charge hebdo bornée. Un planning faisable est produit côté C# comme côté Python — la parité est chiffre-à-chiffre sur le statut et la couverture (21 shifts assignés = D×S, une infirmière par slot).
• Tranche 1 vs Tranche 2 = pédagogie vs production. La Tranche 1 (§2–5) rend visible la mécanique : le glouton ordonnance, le backtracking retourne-arrière, Min-Conflicts répare. La Tranche 2 délègue tout cela au moteur CP-SAT, qui apporte la propagation de bornes et la Lazy Clause Generation — le même rôle que ortools.sat.python.cp_model joue côté Python. C’est précisément le pont que la §7 « Complémentarité » annonçait comme l’atout du twin Python : il est désormais matérialisé côté C#.
• Booléens vs entiers : la décision de modélisation. La Tranche 1 cell2 a choisi assign[d][s] (entier = index d’infirmier), ce qui auto-satisfait C1 (un seul infirmier par slot). La Tranche 2, comme le jumeau Python, choisit x[n][d][s] booléen (105 variables) — formulation où C1 devient une contrainte explicite Sum == demand. Les deux modélisations sont légitimes ; la booléenne est celle du moteur industriel (elle se prête à l’optimisation pondérée via coefficients sur les variables, comme le jumeau Python le fait pour les préférences avec Minimize).
• Pourquoi quatre contraintes suffisent. C’est la force déclarative de la programmation par contraintes : l’énoncé métier (couverture, unicité, repos, charge) se traduit littéralement en quatre groupes de contraintes linéaires sur les booléens, sans encoder le moindre mécanisme de parcours. Le solveur dérive lui-même la stratégie — là où la Tranche 1 a dû l’expliciter (heuristique gloutonne, ordre de branchement, fonction de coût Min-Conflicts).

C’est exactement la parité demandée par l’EPIC #10382 : les deux jumeaux atteignent désormais un moteur de production de leur écosystème (ortools.sat côté Python, Google.OrTools côté .NET), la réimplémentation pédagogique étant conservée en plus, jamais à la place.

8. Exercices

Les trois exercices reprennent les extensions du twin Python. Chaque stub est à compléter : l’objectif et le squelette sont donnés, la logique métier est à écrire.

Exercice 1 — Limite configurable de jours consécutifs

Le planning de base n’impose pas de limite de jours consutifs travaillés. Un infirmier pourrait enchaîner 7 jours. Ajoutez une contrainte C5 : au plus maxConsec jours consécutifs.

Indice : pour chaque infirmier, comptez les runs de jours où il a au moins un shift ; un run dépassant maxConsec est une violation. Ajoutez ce compte à HardViolations et testez avec maxConsec = 3.

// --- Exercice 1 : limite de jours consecutifs (STUB a completer) ---

int CountConsecutiveViolations(int[][] assign, int maxConsec)
{
    // TODO etudiant : pour chaque infirmier n, parcourir les jours ;
    // un "run" = suite de jours consecutifs ou n a au moins un shift.
    // Compter le depassement (run_length - maxConsec) pour chaque run > maxConsec.
    // Indice : pour un infirmier n, build[  d] = (n a un shift au jour d ?).
    return 0;   // TODO etudiant : retourner le total des depassements
}

// Test rapide avec maxConsec = 3 (doit signaler les runs trop longs)
// int v3 = CountConsecutiveViolations(mc, 3);
// $"Violations C5 (max 3 consecutifs) = {v3}".Display();
"Exercice 1 a completer : implementer CountConsecutiveViolations ci-dessus.".Display();

Exercice 1 a completer : implementer CountConsecutiveViolations ci-dessus.

Exercice 2 — Préférences pondérées par priorité

Jusqu’ici chaque préférence violée coûte PREF_PENALTY = 2. En pratique, Alice déteste plus le samedi matin que le dimanche après-midi. Donnez à chaque préférence un poids propre, et modifiez SoftPenalty pour sommer les poids.

// --- Exercice 2 : preferences ponderees (STUB a completer) ---

// Idee : remplacer le Dict<int, List<(int,int)>> par Dict<int, List<(int day, int shift, int weight)>>
// puis sommer les poids des preferences violees au lieu de compter * PREF_PENALTY.

// var weighted = new Dictionary<int, List<(int day, int shift, int weight)>> { ... };

int SoftPenaltyWeighted(int[][] assign /*, weighted */)
{
    // TODO etudiant : sommer les poids des preferences (day,shift) present pour assign[d][s]
    return 0;   // TODO etudiant
}

"Exercice 2 a completer : ponderer les preferences par poids individuel.".Display();

Exercice 2 a completer : ponderer les preferences par poids individuel.

Exercice 3 — Contrats à temps partiel (min/max par infirmier)

Certains infirmiers sont à temps partiel : un minimum de shifts (garanti par contrat) et un maximum plus strict que MAX_SHIFTS. Ajoutez une contrainte par infirmier (minShifts, maxShifts) et intégrez-la au validateur.

// --- Exercice 3 : contrats min/max par infirmier (STUB a completer) ---

// Idee : var contract = new (int min, int max)[] { (1, 3), (2, 5), (3, 5), (1, 4), (2, 5) };
// Une violation = charge hors [min, max] pour un infirmier.

int CountContractViolations(int[][] assign /*, (int min, int max)[] contract */)
{
    // TODO etudiant : calculer la charge de chaque infirmier, compter les depassements
    // (en dessous de min OU au-dessus de max).
    return 0;   // TODO etudiant
}

"Exercice 3 a completer : ajouter une contrainte de contrat min/max par infirmier.".Display();

Exercice 3 a completer : ajouter une contrainte de contrat min/max par infirmier.

Conclusion

Ce twin C# a déroulé trois solveurs from-scratch sur le Nurse Rostering Problem :

• Le glouton est rapide mais myope : il atteint la faisabilité (coût dur = 0), mais faute de retour arrière il n’optimise pas les préférences — 4 violées, le plus mauvais des trois solveurs.
• Le backtracking garantit la faisabilité (un planning valide) mais ignore l’optimisation.
• Le min-conflicts atteint la faisabilité et minimise les préférences, en se laissant guider par le coût.

La décision de modélisation (une variable entière par slot plutôt que 105 booléens) est l’autre leçon clé : elle rend C1 triviale et ouvre la voie à la recherche locale. Le twin Python (OR-Tools CP-SAT) reste l’outil de production ; ce twin rend explicite la mécanique que CP-SAT encapsule — c’est tout l’enjeu du Prong B du marathon #4956.

Pour aller plus loin : comparez les temps de résolution du min-conflicts (from-scratch) et de CP-SAT (twin Python) sur le problème « à grande échelle » — vous mesurerez alors concrètement pourquoi un solveur industriel reste pertinent malgré la lisibilité des algorithmes faits maison.

---

Navigation : << App-2b GraphColoring-CSharp | Index | App-3 Python (OR-Tools) >>

Marathon #4956 — parité .NET ⇄ Python. Voir EPIC #3801 (axe-2 SOTA).