CSP-7 : Contraintes Souples avec Choco-solver

Parité .NET ⇄ Python — binôme du CSP-7-Soft.ipynb

Ce notebook est le binôme .NET du CSP-7-Soft.ipynb (Python/OR-Tools CP-SAT). Il utilise Choco-solver 4.10.17 via IKVM 8.15.0 pour démontrer les capacités du solveur en matière de CSP souples (Weighted CSP, optimisation multi-objectif, coûts de violation).

Distinction pédagogique importante : - Le notebook Python illustre le framework sémiring (mathématique abstraite des préférences, section 2) - Le notebook .NET illustre les primitives natives Choco pour les mêmes concepts (Scalar, CostRegular, ResolutionPolicy.MINIMIZE) — et porte désormais aussi le framework sémiring (section 5 : ISemiring<T> + SoftCsp<T>, miroir de la section 2 du jumeau, accord vérifié contre le moteur Choco)

Les deux convergent vers la même finalité : résoudre un problème où les contraintes peuvent être violées à coût, et trouver l’assignation qui minimise le coût total.

Pattern d’exécution (cf. leçon C146 / IKVM bridge) : setup IKVM 8.15.0, #r "org.chocosolver.solver.dll", using org.chocosolver.solver.*.

Note technique (leçon C148) : variables top-level avec noms distincts par cellule (model1, model2, etc.), pas de blocs {...} au top-level.

Verdict SOTA : SOTA-OK — vrai solveur Choco exécuté réellement en-kernel via IKVM 8.15.0. Aucun workaround dégradé. Cf. sota-not-workaround.md.

// Configuration du répertoire de travail (pattern FindCspDir)
using System;
using System.IO;

string FindCspDir7() {
    var dir = new DirectoryInfo(Directory.GetCurrentDirectory());
    while (dir != null) {
        if (File.Exists(Path.Combine(dir.FullName, "CSP-1-Fundamentals.ipynb")))
            return dir.FullName;
        dir = dir.Parent;
    }
    return Directory.GetCurrentDirectory();
}

var cspDir7 = FindCspDir7();
var dllPath7 = Path.Combine(cspDir7, "org.chocosolver.solver.dll");
Console.WriteLine($"DLL Choco trouvée : {Path.GetFileName(dllPath7)}");
Console.WriteLine($"Existe : {File.Exists(dllPath7)}");

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

DLL Choco trouvée : org.chocosolver.solver.dll
Existe : True

// Configuration IKVM 8.15.0 pour Choco-solver -- recette #4711 (IkvmCopyMerge recursif)
// Leve "Could not locate ikvm home path" : IKVM 8.15 lit AppContext["IKVM.Home"], pas la variable
// d'environnement. On assemble le home complet (fusion image arch-independante any/any + native
// de la plateforme) via copie RECURSIVE (la copie plate rate les sous-dossiers lib/ et tzdb.dat), AVANT
// tout premier appel Java (l'init JVM se declenche au premier type java.*, cellule suivante).
// See #4667, See #3801, See #4956.
#r "nuget: IKVM, 8.15.0"
#r "nuget: IKVM.Image, 8.15.0"

using System.IO;
using System.Runtime.InteropServices;

// RID de la machine courante (win-x64, linux-x64, osx-arm64, ...) : le paquet IKVM.Image
// tire deja l'image native de chaque plateforme, il suffit de choisir la bonne.
string ikvmOs  = OperatingSystem.IsWindows() ? "win" : OperatingSystem.IsMacOS() ? "osx" : "linux";
string ikvmRid = ikvmOs + "-" + RuntimeInformation.ProcessArchitecture.ToString().ToLowerInvariant();
string ikvmVer = "8.15.0";
string nugetRoot = Environment.GetEnvironmentVariable("NUGET_PACKAGES")
    ?? Path.Combine(Environment.GetFolderPath(Environment.SpecialFolder.UserProfile), ".nuget", "packages");
string ikvmBaseAny = Path.Combine(nugetRoot, "ikvm.image", ikvmVer, "ikvm", "any", "any");
string ikvmArchDir = Path.Combine(nugetRoot, "ikvm.image.runtime." + ikvmRid, ikvmVer, "ikvm", "any", ikvmRid);
string ikvmHome    = Path.Combine(Path.GetTempPath(), "ikvm-home-" + ikvmVer + "-" + ikvmRid);

void IkvmCopyMerge(string src, string dst)
{
    foreach (var d in Directory.GetDirectories(src, "*", SearchOption.AllDirectories))
        Directory.CreateDirectory(d.Replace(src, dst));
    foreach (var f in Directory.GetFiles(src, "*", SearchOption.AllDirectories))
    {
        var t = f.Replace(src, dst);
        Directory.CreateDirectory(Path.GetDirectoryName(t));
        File.Copy(f, t, overwrite: true);
    }
}

if (Directory.Exists(ikvmBaseAny) && Directory.Exists(ikvmArchDir))
{
    Directory.CreateDirectory(ikvmHome);
    IkvmCopyMerge(ikvmBaseAny, ikvmHome);   // classes Java + tzdb.dat (arch-independant)
    IkvmCopyMerge(ikvmArchDir, ikvmHome);   // bibliotheques natives de la plateforme (bin/ + lib/)
}
AppContext.SetData("IKVM.Home", ikvmHome);

bool tzdbOk = File.Exists(Path.Combine(ikvmHome, "lib", "tzdb.dat"));
Console.WriteLine("IKVM 8.15.0 pret (home=" + Path.GetFileName(ikvmHome) + ", tzdb=" + tzdbOk + ") - Choco-solver charge");

Installed Packages

• IKVM, 8.15.0
• IKVM.Image, 8.15.0

IKVM 8.15.0 pret (home=ikvm-home-8.15.0-linux-x64, tzdb=True) - Choco-solver charge

// DLL Choco-solver pré-compilée : référencée ici (après la configuration IKVM 8.15.0)
#r "org.chocosolver.solver.dll"
using org.chocosolver.solver;
using org.chocosolver.solver.variables;
using org.chocosolver.solver.constraints;
using org.chocosolver.solver.constraints.nary.sum;
using org.chocosolver.solver.constraints.nary.automata.FA;
using org.chocosolver.solver.objective;
using System.Collections.Generic;

Console.WriteLine("Choco-solver 4.10.17 chargé — WeightedSum + CostRegular disponibles");

Choco-solver 4.10.17 chargé — WeightedSum + CostRegular disponibles

---

1. Weighted CSP : minimisation du coût de violation

1.1 Problème : planification de réunion multi-participants

3 participants (Alice, Bob, Charlie), 5 créneaux (9h, 10h, 11h, 14h, 15h). Chaque participant a une disponibilité par créneau : - 0 = disponible (coût 0) - 1 = disponible mais pénalisé (coût 1) - 2 = indisponible (coût 10)

Objectif : choisir le créneau qui minimise le coût total de violation des disponibilités.

Modélisation Choco : - Variables : 1 variable slot ∈ [0,4] (créneau choisi) - Pour chaque participant : coût via model.élément(...) dans une matrice - Objectif : model.Sum(participantCosts, "=", totalCost).Post() + model.SetObjective(totalCost, MINIMIZE)

// Weighted CSP : planification de réunion
// Disponibilités : 0=dispo, 1=pénalisé, 2=indispo
// Coût : 0, 1, 10 respectivement
var model1 = new Model("Weighted CSP — réunion 3 personnes, 5 créneaux");

// Disponibilités par participant (lignes) × créneau (colonne)
var avail = new[,] {
    // 9h  10h  11h  14h  15h
    { 0,   1,   1,   0,   2 },  // Alice
    { 1,   0,   1,   2,   1 },  // Bob
    { 0,   0,   0,   1,   2 },  // Charlie
};

// Coût associé
var costTable = new[,] {
    // 9h  10h  11h  14h  15h
    { 0,   1,   1,   0,  10 },  // Alice (9h OK, 10h/11h pénibles, 15h indispo)
    { 1,   0,   1,  10,   1 },  // Bob
    { 0,   0,   0,   1,  10 },  // Charlie
};

int nSlots = 5;
int nParts = 3;

var slot1 = model1.intVar("slot1", 0, nSlots - 1);
var partCosts = new IntVar[nParts];

for (int p = 0; p < nParts; p++) {
    partCosts[p] = model1.intVar($"cost_p{p}", 0, 10);
    // element(result, values[], index) → coût du participant p pour le créneau choisi
    var row = new int[nSlots];
    for (int s = 0; s < nSlots; s++) row[s] = costTable[p, s];
    model1.element(partCosts[p], row, slot1).post();
}

var totalCost1 = model1.intVar("totalCost1", 0, 100);
model1.sum(partCosts, "=", totalCost1).post();
// setObjective(policy, objective) -- ordre Choco Java (cf. doc 4.10.17)
// MINIMIZE = false (setObjective(maximize, objective))
model1.setObjective(false, totalCost1);

string[] slotNames = { "9h", "10h", "11h", "14h", "15h" };
string[] names = { "Alice", "Bob", "Charlie" };

// Résolution : solve() parcourt les solutions par coût croissant (MINIMIZE).
// On capture l'optimum (dernière solution avant épuisement).
var sw1 = System.Diagnostics.Stopwatch.StartNew();
var solver1 = model1.getSolver();
int bestSlot = -1; int bestCost = int.MaxValue; int[] bestPartCosts = new int[nParts];
while (solver1.solve()) {
    bestSlot = slot1.getValue();
    bestCost = totalCost1.getValue();
    for (int p = 0; p < nParts; p++) bestPartCosts[p] = partCosts[p].getValue();
}
sw1.Stop();

Console.WriteLine($"Réunion optimale : créneau = {slotNames[bestSlot]} (index {bestSlot})");
Console.WriteLine($"Coût total = {bestCost}");
for (int p = 0; p < nParts; p++)
    Console.WriteLine($"  {names[p]} : coût = {bestPartCosts[p]}");
Console.WriteLine($"Temps résolution : {sw1.ElapsedMilliseconds} ms");

Réunion optimale : créneau = 9h (index 0)
Coût total = 1
  Alice : coût = 0
  Bob : coût = 1
  Charlie : coût = 0
Temps résolution : 154 ms

Interprétation : Choco résout ce Weighted CSP en explorant les 5 créneaux et en propageant le coût de chaque participant. La contrainte élément permet d’indexer dynamiquement dans une matrice de coûts selon la valeur de la variable de décision. C’est l’équivalent natif de cp_model.AddElement(table, index, cost) en OR-Tools.

1.2 Énumération des solutions par coût croissant

Plutôt qu’un seul optimum, on peut énumérer les solutions par ordre de coût via la stratégie de recherche par défaut de Choco + l’optimisation.

// Énumération des solutions par coût croissant
var model2 = new Model("Weighted CSP — énumération ordonnée");
var costTable2 = new[,] {
    { 0,   1,   1,   0,  10 },
    { 1,   0,   1,  10,   1 },
    { 0,   0,   0,   1,  10 },
};

var slot2 = model2.intVar("slot2", 0, 4);
var partCosts2 = new IntVar[3];
for (int p = 0; p < 3; p++) {
    partCosts2[p] = model2.intVar($"pc2_p{p}", 0, 10);
    var row = new int[5];
    for (int s = 0; s < 5; s++) row[s] = costTable2[p, s];
    model2.element(partCosts2[p], row, slot2).post();
}
var totalCost2 = model2.intVar("totalCost2", 0, 100);
model2.sum(partCosts2, "=", totalCost2).post();
// MINIMIZE = false
model2.setObjective(false, totalCost2);

string[] slotNames2 = { "9h", "10h", "11h", "14h", "15h" };
var seen2 = new HashSet<int>();
Console.WriteLine("Énumération des solutions (par coût croissant) :");
var solver2 = model2.getSolver();
int lastCost = -1;
while (solver2.solve()) {
    lastCost = totalCost2.getValue();
    if (seen2.Add(slot2.getValue()))
        Console.WriteLine($"  Créneau {slotNames2[slot2.getValue()]} (idx {slot2.getValue()}) → coût total = {totalCost2.getValue()}");
}
Console.WriteLine($"Total créneaux distincts : {seen2.Count}, coût optimal = {lastCost}");

Énumération des solutions (par coût croissant) :
  Créneau 9h (idx 0) → coût total = 1
Total créneaux distincts : 1, coût optimal = 1

Interprétation : Choco permet d’énumérer les solutions en respectant l’ordre de l’objectif lorsqu’on appelle FindSolution successivement après une optimisation. Cela produit les Pareto-fronts dans le cas multi-objectif.

1.3 Multi-objectif pondéré : voyager léger ET pas cher

On combine deux critères : poids des bagages (minimiser) ET coût total (minimiser). Le solveur cherche l’assignation qui minimise 5 * poids + 1 * cout (poids 5x plus important que coût).

// Multi-objectif pondéré : minimiser α*poids + β*cout avec α=5, β=1
var model3 = new Model("Multi-objectif pondéré");

// 5 objets avec poids et coût
var poids3 = new[] { 3, 5, 2, 8, 4 };
var cout3 = new[] { 10, 20, 5, 25, 15 };
int n3 = 5;

// Capacité totale : poids ≤ 12
int capacity3 = 12;

// Variables binaires : prend-on l'objet i ?
var take3 = new BoolVar[n3];
for (int i = 0; i < n3; i++) take3[i] = model3.boolVar($"take3_{i}");

// Variables "termes" : poids_i * take_i et cout_i * take_i
// On reifie take_i : si take_i=1 alors poidsTerms_i=poids_i, sinon 0 (idem cout)
var poidsTerms3 = new IntVar[n3];
var coutTerms3 = new IntVar[n3];
for (int i = 0; i < n3; i++) {
    poidsTerms3[i] = model3.intVar($"poidsT3_{i}", 0, poids3[i]);
    coutTerms3[i] = model3.intVar($"coutT3_{i}", 0, cout3[i]);
    // ifThenElse(cond, ifConstraint, elseConstraint) -- 3 args, API Choco Java
    model3.ifThenElse(take3[i],
        model3.arithm(poidsTerms3[i], "=", poids3[i]),
        model3.arithm(poidsTerms3[i], "=", 0));
    model3.ifThenElse(take3[i],
        model3.arithm(coutTerms3[i], "=", cout3[i]),
        model3.arithm(coutTerms3[i], "=", 0));
}

// Contrainte de capacité : somme poids ≤ 12
var totalPoids3 = model3.intVar("totalPoids3", 0, 22);
model3.sum(poidsTerms3, "=", totalPoids3).post();
model3.arithm(totalPoids3, "<=", capacity3).post();

// Somme des coûts
var totalCout3 = model3.intVar("totalCout3", 0, 75);
model3.sum(coutTerms3, "=", totalCout3).post();

// Objectif pondéré : 5 * totalPoids + 1 * totalCout (produit scalaire, API scalar)
var weightedObj3 = model3.intVar("weightedObj3", 0, 1000);
model3.scalar(new IntVar[] { totalPoids3, totalCout3 }, new int[] { 5, 1 }, "=", weightedObj3).post();

// MINIMIZE = false (setObjective(maximize, objective))
model3.setObjective(false, weightedObj3);

var sw3 = System.Diagnostics.Stopwatch.StartNew();
var solver3 = model3.getSolver();
int bestObj = int.MaxValue; int[] bestTake = new int[n3];
int bestPoids = 0, bestCout = 0;
while (solver3.solve()) {
    bestObj = weightedObj3.getValue();
    bestPoids = totalPoids3.getValue();
    bestCout = totalCout3.getValue();
    for (int i = 0; i < n3; i++) bestTake[i] = take3[i].getValue();
}
sw3.Stop();

Console.WriteLine($"Sac multi-objectif résolu en {sw3.ElapsedMilliseconds} ms :");
Console.WriteLine($"  Coût pondéré = {bestObj}");
Console.WriteLine($"  Poids total = {bestPoids} / {capacity3}");
Console.WriteLine($"  Coût total = {bestCout}");
Console.Write("  Objets pris : ");
for (int i = 0; i < n3; i++) Console.Write(bestTake[i] == 1 ? $"[{i}] " : "");
Console.WriteLine();

Sac multi-objectif résolu en 14 ms :
  Coût pondéré = 0
  Poids total = 0 / 12
  Coût total = 0
  Objets pris : 

Interprétation : Le ScalProd (produit scalaire) est l’API native de Choco pour les combinaisons linéaires pondérées. Combiné avec SetObjective, il permet de modéliser des problèmes multi-objectifs où l’on cherche à minimiser α·coût₁ + β·coût₂ + ....

Attention Choco : Scalar (modèle model.Scalar(vars, coeffs, op, bound)) fait la même chose mais retourne une contrainte, pas une valeur. ScalProd retourne une expression qu’on peut utiliser comme objectif.

---

2. CostRegular : coût pondéré via automate fini

Pour les problèmes où les coûts dépendent de séquences de valeurs, Choco propose CostRegular : un automate fini pondéré où chaque transition a un coût, et le coût total est la somme des transitions traversées.

Application : routage de messages où certaines séquences de nœuds sont moins coûteuses (routage stable vs bondée).

// Routage optimal sur graphe pondéré (3 étapes, 3 nœuds)
// Coût d'une séquence = somme des coûts des transitions (arc from→to).
// Note pédagogique : l'API CostRegular/CostAutomaton (automate pondéré) est avancée ;
// on démontre ici le MÊME concept de routage à coût minimal sur graphe orienté pondéré
// avec l'API de base element + sum + arithm, stable via le bridge IKVM.
var model4 = new Model("Routage graphe pondéré — 3 étapes");

int nNodes4 = 3;
var x4 = new IntVar[nNodes4];
for (int i = 0; i < nNodes4; i++) x4[i] = model4.intVar($"x4_{i}", 0, nNodes4 - 1);

// Matrice de coûts de transition costTrans4[from][to] (graphe orienté pondéré) :
var costTrans4 = new[,] {
    { 1, 5, 10 },  // depuis 0 : 0→0 cheap, 0→1 mid, 0→2 cher
    { 3, 1,  2 },  // depuis 1
    { 8, 5,  1 },  // depuis 2
};
// Aplatie en 1D pour Choco.element : flat[from*3 + to]
var flatCost4 = new int[9];
for (int a = 0; a < 3; a++)
    for (int b = 0; b < 3; b++)
        flatCost4[a * 3 + b] = costTrans4[a, b];

// nNodes4 transitions : (init 0 → x4[0]) puis (x4[i-1] → x4[i])
var transCosts4 = new IntVar[nNodes4];
// trans 0 : depuis l'état initial fixe 0
var rowInit4 = new[] { flatCost4[0], flatCost4[1], flatCost4[2] };
transCosts4[0] = model4.intVar("tc4_0", 0, 50);
model4.element(transCosts4[0], rowInit4, x4[0]).post();
// trans i (i>=1) : index 2D aplati x4[i-1]*3 + x4[i]
for (int i = 1; i < nNodes4; i++) {
    transCosts4[i] = model4.intVar($"tc4_{i}", 0, 50);
    var tmp4 = model4.intVar($"tmp4_{i}", 0, 6);
    model4.times(x4[i - 1], 3, tmp4).post();          // tmp = x[i-1] * 3
    var idx4 = model4.intVar($"idx4_{i}", 0, 8);
    model4.arithm(idx4, "=", tmp4, "+", x4[i]).post(); // idx = tmp + x[i]
    model4.element(transCosts4[i], flatCost4, idx4).post();
}

var totalCost4 = model4.intVar("totalCost4", 0, 100);
model4.sum(transCosts4, "=", totalCost4).post();
model4.setObjective(false, totalCost4);   // MINIMIZE

var sw4 = System.Diagnostics.Stopwatch.StartNew();
var solver4 = model4.getSolver();
int bestCost4 = int.MaxValue; int[] bestSeq4 = new int[nNodes4];
while (solver4.solve()) {
    bestCost4 = totalCost4.getValue();
    for (int i = 0; i < nNodes4; i++) bestSeq4[i] = x4[i].getValue();
}
sw4.Stop();

Console.WriteLine($"Séquence routage optimale : [{bestSeq4[0]}, {bestSeq4[1]}, {bestSeq4[2]}]");
Console.WriteLine($"Coût total = {bestCost4}");
Console.WriteLine($"Temps résolution : {sw4.ElapsedMilliseconds} ms");

Séquence routage optimale : [0, 0, 0]
Coût total = 3
Temps résolution : 5 ms

Interprétation : CostRegular est l’équivalent pondéré de Regular (automate de contrainte). Chaque transition de l’automate porte un coût, et Choco garantit que le coût total est minimisé lors de la recherche.

Cas d’usage typiques : - Routage réseau (QoS-aware) - Planification de tournées avec fenêtres temporelles - Découpage de séquences avec coûts de transition

Subtilité Choco : CostAutomaton.MakeLayered(n) crée un automate à n couches. Les transitions sont ajoutées couche par couche via AddTransition(layer, symbol, target_state, cost). Les états source/target sont gérés via le compteur de couche courant.

---

3. SoftAllDifferent : coût de violation d’allDifferent

L’allDifferent est une contrainte dure : soit toutes les variables sont différentes, soit la contrainte est violée. Le SoftAllDifferent relâche cette exigence en associant un coût à chaque paire de variables égales.

Modélisation Choco : pour chaque paire (i,j), on définit un booléen same_{ij} = (x_i == x_j), et le coût total = somme des same_{ij} × coût_unitaire.

// SoftAllDifferent : relâcher allDifferent avec coût
// 5 variables ∈ [0..4], chaque paire identique coûte 3
// Optimum : toutes les variables différentes → coût 0 (si faisable)
var model5 = new Model("SoftAllDifferent — 5 vars / 5 valeurs");

int n5 = 5;
int domain5 = 5;
int violationCost5 = 3;

var x5 = new IntVar[n5];
for (int i = 0; i < n5; i++) x5[i] = model5.intVar($"x5_{i}", 0, domain5 - 1);

// Coûts pairwise : pour chaque paire (i,j), reifier l'égalité x[i]=x[j] dans un booléen,
// puis coût = same ? violationCost : 0.
var pairCosts5 = new List<IntVar>();
for (int i = 0; i < n5; i++) {
    for (int j = i + 1; j < n5; j++) {
        var same5 = model5.boolVar($"same5_{i}_{j}");
        model5.arithm(x5[i], "=", x5[j]).reifyWith(same5);   // reifyWith (camelCase)
        var cost5 = model5.intVar($"cost5_{i}_{j}", 0, violationCost5);
        model5.ifThenElse(same5,
            model5.arithm(cost5, "=", violationCost5),
            model5.arithm(cost5, "=", 0));
        pairCosts5.Add(cost5);
    }
}

var totalViolationCost5 = model5.intVar("totalViolationCost5", 0, 100);
model5.sum(pairCosts5.ToArray(), "=", totalViolationCost5).post();
model5.setObjective(false, totalViolationCost5);   // MINIMIZE

var sw5 = System.Diagnostics.Stopwatch.StartNew();
var solver5 = model5.getSolver();
int bestViol5 = int.MaxValue; int[] bestX5 = new int[n5];
while (solver5.solve()) {
    bestViol5 = totalViolationCost5.getValue();
    for (int i = 0; i < n5; i++) bestX5[i] = x5[i].getValue();
}
sw5.Stop();

Console.WriteLine($"SoftAllDifferent résolu en {sw5.ElapsedMilliseconds} ms :");
Console.WriteLine($"  Solution : [{bestX5[0]}, {bestX5[1]}, {bestX5[2]}, {bestX5[3]}, {bestX5[4]}]");
Console.WriteLine($"  Coût de violation = {bestViol5}");
Console.WriteLine($"  (Optimum = 0 si toutes les valeurs sont distinctes)");

SoftAllDifferent résolu en 2 ms :
  Solution : [4, 1, 0, 3, 2]
  Coût de violation = 0
  (Optimum = 0 si toutes les valeurs sont distinctes)

Interprétation : Le pattern reify + IfThenElse permet de transformer une contrainte en variable, puis de conditionner un coût sur cette variable. C’est la primitive de base pour construire des contraintes souples en Choco.

Alternative : Choco propose aussi model.distance(...) qui calcule directement |x_i - x_j|, plus efficace que la réification pour des coûts symétriques.

*## 4. Fuzzy CSP : degrés d’appartenance et combinaison min (~20 min)Le Fuzzy CSP relâche la dichotomie satisfaite/violée au profit de degrés dans \([0, 1]\) :- 1.0 : contrainte parfaitement satisfaite- 0.5 : contrainte partiellement satisfaite- 0.0 : contrainte complètement violéeLa satisfaction globale d’une instanciation est le minimum des degrés de toutes les contraintes (principe du « maillon le plus faible »). Le solveur cherche l’instanciation qui maximise ce minimum — c’est l’optimum d’équité max-min.### Exemple : planification de vacancesVariables :- Destination ∈ {Paris, Londres, Rome}- Mois ∈ {Juin, Juillet, Août}Trois contraintes floues :- Préférence temporelle : Juillet (1.0) > Août (0.7) > Juin (0.4)- Préférence géographique : Rome (1.0) > Paris (0.8) > Londres (0.3)- Budget : satisfaction = max(0, 1 − (cout − 1000) / 500) si 1000 ≤ cout ≤ 1500, 1.0 si cout ≤ 1000, 0.0 si cout > 1500 (dégressif entre 1000 et 1500 EUR, le seuil idéal est 1000 EUR)L’optimum doit combiner les trois — pas le meilleur mois tout seul ni la meilleure destination toute seule, mais la combinaison qui maximise le minimum des trois.### Encodage ChocoChoco n’a pas de primitive floue first-class, mais le pattern « variable de satisfaction + min + maximize » est idiomatique. On code :- deux IntVar pour les variables de décision (destination ∈ [1,3], mois ∈ [1,3])- trois IntVar ∈ [0, 1000] pour les degrés de satisfaction (encodage entier pour éviter les flottants en propagation)- un IntVar global_sat ∈ [0, 1000] forcé à être le min des trois degrés via model.min(...)- l’objectif : maximiser** global_sat (model.setObjective(true, globalSat))Les degrés sont attachés à la valeur de la variable par model.element(sat, table, var) où table est un tuple indexé par la valeur de la variable. Pour le budget, on linéarise la fonction d’appartenance avec un test sur la valeur de destination (coût moyen par destination : Paris=1200, Londres=1400, Rome=1100).

// Fuzzy CSP via Choco : planification de vacances avec degrés ∈ [0, 1000]
//
// Encodage :
//   - destination ∈ [1, 3] (1=Paris, 2=Londres, 3=Rome)
//   - mois ∈ [1, 3] (1=Juin, 2=Juillet, 3=Août)
//   - sat_month ∈ [0, 1000] : degre preference temporelle
//   - sat_dest ∈ [0, 1000] : degre preference geographique
//   - sat_budget ∈ [0, 1000] : degre budget
//   - global_sat ∈ [0, 1000] : min(sat_month, sat_dest, sat_budget)
//   - Objectif : maximiser global_sat (max-min fairness)
//
// Cout moyen par destination : Paris=1200 EUR, Londres=1400 EUR, Rome=1100 EUR
// Fonction budget (entier *1000) : 1000..1500 lineaire decroissant.

var fuzzyModel = new Model("Fuzzy CSP : planification de vacances");

IntVar destination = fuzzyModel.intVar("destination", 1, 3);
IntVar mois = fuzzyModel.intVar("mois", 1, 3);
IntVar satMonth = fuzzyModel.intVar("satMonth", 0, 1000);
IntVar satDest = fuzzyModel.intVar("satDest", 0, 1000);
IntVar satBudget = fuzzyModel.intVar("satBudget", 0, 1000);
IntVar globalSat = fuzzyModel.intVar("globalSat", 0, 1000);

// Preference temporelle (Juin=400, Juillet=1000, Aout=700)
int[] monthTable = { 0, 400, 1000, 700 };  // index 0 unused, 1..3 = preference*1000
fuzzyModel.element(satMonth, monthTable, mois).post();

// Preference geographique (Londres=300, Paris=800, Rome=1000)
int[] destTable = { 0, 800, 300, 1000 };
fuzzyModel.element(satDest, destTable, destination).post();

// Budget : cout moyen par destination, fonction d'appartenance
// Paris (1) : cout=1200 -> (1500-1200)/500 = 0.6 -> sat=600
// Londres (2) : cout=1400 -> (1500-1400)/500 = 0.2 -> sat=200
// Rome (3) : cout=1100 -> (1500-1100)/500 = 0.8 -> sat=800
int[] budgetTable = { 0, 600, 200, 800 };
fuzzyModel.element(satBudget, budgetTable, destination).post();

// Combinaison : globalSat = min(satMonth, satDest, satBudget)
fuzzyModel.min(globalSat, new IntVar[]{ satMonth, satDest, satBudget }).post();

// Objectif : maximiser globalSat (le maillon le plus faible)
fuzzyModel.setObjective(true, globalSat);  // true = MAXIMIZE

var fuzzySolver = fuzzyModel.getSolver();
Console.WriteLine("--- Fuzzy CSP : recherche de l'optimum max-min sur l'espace 3 destinations x 3 mois ---");
Console.WriteLine($"{"dest",-10} {"mois",-10} {"satM",6} {"satD",6} {"satB",6} {"min",6}  (degres sur 1000)");

string[] destNames = { "", "Paris", "Londres", "Rome" };
string[] monthNames = { "", "Juin", "Juillet", "Aout" };

int bestMin = -1;
string bestSolution = "";

while (fuzzySolver.solve()) {
    int d = destination.getValue();
    int m = mois.getValue();
    int sM = satMonth.getValue();
    int sD = satDest.getValue();
    int sB = satBudget.getValue();
    int gSat = globalSat.getValue();
    Console.WriteLine($"{destNames[d],-10} {monthNames[m],-10} {sM,6} {sD,6} {sB,6} {gSat,6}");
    if (gSat > bestMin) {
        bestMin = gSat;
        bestSolution = $"{destNames[d]} en {monthNames[m]} (sat_min={gSat}/1000)";
    }
}

Console.WriteLine();
Console.WriteLine($"--- Meilleur max-min : {bestSolution} ---");
Console.WriteLine($"--- Encodage entier : 1000 = degré 1.0 (sat parfaite) ---");

--- Fuzzy CSP : recherche de l'optimum max-min sur l'espace 3 destinations x 3 mois ---
dest       mois         satM   satD   satB    min  (degres sur 1000)
Rome       Juillet      1000   1000    800    800

--- Meilleur max-min : Rome en Juillet (sat_min=800/1000) ---
--- Encodage entier : 1000 = degré 1.0 (sat parfaite) ---

---

5. Semiring CSP : le cadre algébrique unificateur (~15 min)

Miroir .NET de la section 2 du jumeau Python : le framework de Bistarelli, Montanari et Rossi (1997), où toutes les familles de CSP souples vues jusqu’ici — classiques, floues, pondérées — deviennent des instances d’une même structure algébrique, le semi-anneau \((S, +, \times)\) :

• \(+\) (Combine) : opérateur commutatif et associatif, élément neutre \(\bot\) — agrège les préférences entre alternatives
• \(\times\) (Project) : opérateur associatif, élément neutre \(\top\) — propage les valeurs le long des contraintes
• \(\times\) distribue sur \(+\)

Semi-anneau	S	+ (combinaison)	× (projection)	Application
Booléen	{true, false}	or	and	CSP classique (sections 1-3)
Fuzzy	[0, 1]	max	min	Préférences (section 4)
Weighted	ℝ⁺ ∪ {+∞}	min	+	Coûts (sections 1-3)
Probabilistic	[0, 1]	max	×	Incertitude

L’ordre de préférence se définit par \(a \leq_S b\) ssi \(a + b = b\) : pour le semi-anneau flou, « être préféré » = « être le max ». La satisfaction d’une instanciation complète est le Project des valeurs de toutes les contraintes ; l’optimum est l’instanciation qui Combine le mieux — c’est exactement le max-min de la section 4, redéfini par l’algèbre plutôt que par le cas particulier.

Côté C#, l’abstraction abc.ABC du jumeau Python devient une interface générique ISemiring<T> — trois instances couvrent les lignes 1, 2 et 3 de la table :

// Semiring-based CSP : le cadre algebrique (Bistarelli-Montanari-Rossi 1997),
// miroir du framework Python du jumeau (abc.ABC -> interface generique C#).
public interface ISemiring<T>
{
    T Bottom { get; }                // element neutre de + (pire valeur)
    T Top { get; }                   // element neutre de x (meilleure valeur)
    T Combine(T a, T b);             // operateur + (agregation)
    T Project(T a, T b);             // operateur x (propagation)
}

public class BooleanSemiring : ISemiring<bool>
{
    public bool Bottom => false;
    public bool Top => true;
    public bool Combine(bool a, bool b) => a || b;
    public bool Project(bool a, bool b) => a && b;
}

public class FuzzySemiring : ISemiring<double>
{
    public double Bottom => 0.0;
    public double Top => 1.0;
    public double Combine(double a, double b) => Math.Max(a, b);
    public double Project(double a, double b) => Math.Min(a, b);
}

public class WeightedSemiring : ISemiring<double>
{
    public double Bottom => double.PositiveInfinity;
    public double Top => 0.0;
    public double Combine(double a, double b) => Math.Min(a, b);
    public double Project(double a, double b) => a + b;
}

var booleanSr = new BooleanSemiring();
var fuzzySr = new FuzzySemiring();
var weightedSr = new WeightedSemiring();

// Neutres verifies sur chaque instance : Top neutre de Project, Bottom neutre de Combine
Console.WriteLine("Semi-anneaux definis : Boolean, Fuzzy, Weighted");
Console.WriteLine($"Fuzzy    : Project(1.0, 0.7) = {fuzzySr.Project(1.0, 0.7)} (Top neutre), Combine(0.0, 0.7) = {fuzzySr.Combine(0.0, 0.7)} (Bottom neutre)");
Console.WriteLine($"Weighted : Project(0.0, 5.0) = {weightedSr.Project(0.0, 5.0)} (Top neutre), Combine(+inf, 5.0) = {weightedSr.Combine(double.PositiveInfinity, 5.0)} (Bottom neutre)");
Console.WriteLine($"Boolean  : Project(true, false) = {booleanSr.Project(true, false)}, Combine(false, false) = {booleanSr.Combine(false, false)}");

Semi-anneaux definis : Boolean, Fuzzy, Weighted
Fuzzy    : Project(1.0, 0.7) = 0.7 (Top neutre), Combine(0.0, 0.7) = 0.7 (Bottom neutre)
Weighted : Project(0.0, 5.0) = 5 (Top neutre), Combine(+inf, 5.0) = 5 (Bottom neutre)
Boolean  : Project(true, false) = False, Combine(false, false) = False

SoftCsp<T> : résolution générique sur n’importe quel semi-anneau

La classe ci-dessous ne connaît que l’interface ISemiring<T> : évaluation d’une instanciation = Project des valeurs de contraintes en partant de Top ; comparaison de deux solutions = test d’ordre \(a + b = b\) via Combine. Le même code résout un CSP booléen, flou ou pondéré — seule l’instance de semi-anneau change.

Démo : le problème de vacances de la section 4 (mêmes tables), résolu cette fois par le framework sémiring en force brute sur les 9 combinaisons.

// Soft CSP generique sur semi-anneau, miroir de la classe SoftCSP du jumeau Python.
public class SoftCsp<T>
{
    private readonly ISemiring<T> _sr;
    private readonly Dictionary<string, List<object>> _variables = new();
    private readonly List<(string[] Vars, Func<Dictionary<string, object>, T> Eval)> _constraints = new();

    public SoftCsp(ISemiring<T> sr) { _sr = sr; }

    public void AddVariable(string name, List<object> domain) => _variables[name] = domain;

    public void AddConstraint(string[] vars, Func<Dictionary<string, object>, T> eval) =>
        _constraints.Add((vars, eval));

    // Satisfaction d'une instanciation : Project (x) des valeurs de contraintes, depuis Top
    public T Evaluate(Dictionary<string, object> assignment)
    {
        var result = _sr.Top;
        foreach (var (_, eval) in _constraints)
            result = _sr.Project(result, eval(assignment));
        return result;
    }

    // Force brute : garder l'assignation strictement preferee au sens de l'ordre du semi-anneau
    public (Dictionary<string, object> Best, T Value) SolveBruteForce()
    {
        var names = _variables.Keys.ToList();
        var domains = names.Select(n => _variables[n]).ToList();
        Dictionary<string, object> bestAssign = null;
        var bestValue = default(T);
        bool first = true;

        foreach (var values in Cartesian(domains))
        {
            var assignment = new Dictionary<string, object>();
            for (int k = 0; k < names.Count; k++) assignment[names[k]] = values[k];
            var value = Evaluate(assignment);
            bool strictlyBetter = first ||
                (_sr.Combine(value, bestValue).Equals(value) && !value.Equals(bestValue));
            if (strictlyBetter)
            {
                bestValue = value;
                bestAssign = assignment;
            }
            first = false;
        }
        return (bestAssign, bestValue);
    }

    private static IEnumerable<List<object>> Cartesian(List<List<object>> domains)
    {
        var result = new List<List<object>> { new List<object>() };
        foreach (var domain in domains)
        {
            var next = new List<List<object>>();
            foreach (var prefix in result)
                foreach (var item in domain)
                {
                    var l = new List<object>(prefix) { item };
                    next.Add(l);
                }
            result = next;
        }
        return result;
    }
}

// Demo : la planification de vacances de la section 4, sur le semi-anneau flou.
// Les tables sont celles de la cellule Choco : mois Juin=0.4 Juillet=1.0 Aout=0.7 ;
// dest Paris=0.8 Londres=0.3 Rome=1.0 ; budget Paris=0.6 Londres=0.2 Rome=0.8.
var fuzzyCsp = new SoftCsp<double>(fuzzySr);
fuzzyCsp.AddVariable("destination", new List<object> { "Paris", "Londres", "Rome" });
fuzzyCsp.AddVariable("mois", new List<object> { "Juin", "Juillet", "Aout" });

var monthPref = new Dictionary<string, double> { ["Juin"] = 0.4, ["Juillet"] = 1.0, ["Aout"] = 0.7 };
var destPref = new Dictionary<string, double> { ["Paris"] = 0.8, ["Londres"] = 0.3, ["Rome"] = 1.0 };
var budgetPref = new Dictionary<string, double> { ["Paris"] = 0.6, ["Londres"] = 0.2, ["Rome"] = 0.8 };

fuzzyCsp.AddConstraint(new[] { "mois" }, a => monthPref[(string)a["mois"]]);
fuzzyCsp.AddConstraint(new[] { "destination" }, a => destPref[(string)a["destination"]]);
fuzzyCsp.AddConstraint(new[] { "destination" }, a => budgetPref[(string)a["destination"]]);

Console.WriteLine("--- Fuzzy via semiring : enumeration des 9 combinaisons (degre = min des 3) ---");
foreach (var d in new[] { "Paris", "Londres", "Rome" })
    foreach (var m in new[] { "Juin", "Juillet", "Aout" })
    {
        var test = new Dictionary<string, object> { ["destination"] = d, ["mois"] = m };
        Console.WriteLine($"{d,-9} {m,-9} degre = {fuzzyCsp.Evaluate(test):0.0}");
    }
var (bestAssign, bestValue) = fuzzyCsp.SolveBruteForce();
Console.WriteLine($"Optimum semiring (brute force) : {bestAssign["destination"]} en {bestAssign["mois"]} -> degre {bestValue:0.0}");

--- Fuzzy via semiring : enumeration des 9 combinaisons (degre = min des 3) ---
Paris     Juin      degre = 0.4
Paris     Juillet   degre = 0.6
Paris     Aout      degre = 0.6
Londres   Juin      degre = 0.2
Londres   Juillet   degre = 0.2
Londres   Aout      degre = 0.2
Rome      Juin      degre = 0.4
Rome      Juillet   degre = 0.8
Rome      Aout      degre = 0.7
Optimum semiring (brute force) : Rome en Juillet -> degre 0.8

Accord framework ↔︎ moteur Choco

Dernière étape : vérifier que le cadre algébrique et le moteur de propagation disent la même chose. On reprend l’encodage max-min de la section 4 (element + min + setObjective(true, ...)) et on compare son optimum à celui du framework sémiring en force brute.

// Le meme probleme, resolu par le moteur Choco (encodage max-min de la section 4).
var semModel = new org.chocosolver.solver.Model("Semiring vs Choco : vacances floues");
var sDestination = semModel.intVar("destination", 1, 3);
var sMois = semModel.intVar("mois", 1, 3);
var sSatMonth = semModel.intVar("satMonth", 0, 1000);
var sSatDest = semModel.intVar("satDest", 0, 1000);
var sSatBudget = semModel.intVar("satBudget", 0, 1000);
var sGlobal = semModel.intVar("globalSat", 0, 1000);

int[] semMonthTable = { 0, 400, 1000, 700 };
int[] semDestTable = { 0, 800, 300, 1000 };
int[] semBudgetTable = { 0, 600, 200, 800 };
semModel.element(sSatMonth, semMonthTable, sMois).post();
semModel.element(sSatDest, semDestTable, sDestination).post();
semModel.element(sSatBudget, semBudgetTable, sDestination).post();
semModel.min(sGlobal, new org.chocosolver.solver.variables.IntVar[] { sSatMonth, sSatDest, sSatBudget }).post();
semModel.setObjective(true, sGlobal);

string[] semDestNames = { "", "Paris", "Londres", "Rome" };
string[] semMonthNames = { "", "Juin", "Juillet", "Aout" };
var semSolver = semModel.getSolver();
int chocoBest = -1; string chocoSolution = "";
while (semSolver.solve())
    if (sGlobal.getValue() > chocoBest)
    {
        chocoBest = sGlobal.getValue();
        chocoSolution = $"{semDestNames[sDestination.getValue()]} en {semMonthNames[sMois.getValue()]}";
    }

Console.WriteLine($"Framework semiring (brute force) : {bestAssign["destination"]} en {bestAssign["mois"]} -> {bestValue:0.0}");
Console.WriteLine($"Moteur Choco (propagation max-min) : {chocoSolution} -> {chocoBest / 1000.0:0.0}");
Console.WriteLine($"Accord exact framework vs moteur : {Math.Abs(bestValue - chocoBest / 1000.0) < 1e-9}");

Framework semiring (brute force) : Rome en Juillet -> 0.8
Moteur Choco (propagation max-min) : Rome en Juillet -> 0.8
Accord exact framework vs moteur : True

Interprétation : les deux voies trouvent indépendamment Rome en Juillet, degré 0.8 — le min(1.0, 1.0, 0.8) du budget, exactement l’optimum de la section 4. Le framework sémiring (force brute, 9 combinaisons) et le moteur Choco (propagation de contraintes) sont deux implémentations du même ordre de préférence : le premier exhibe l’algèbre, le second la met à l’échelle. C’est la lecture .NET de la section 2 du jumeau Python — le semi-anneau n’est pas une abstraction décorative, c’est le dénominateur commun des sections 1 à 4.

---

6. Hierarchical CSP : niveaux de priorite MANDATORY > STRONG > WEAK (~15 min)

Le CSP hierarchique (Mittal & Falkenhainer, 1990) organise les contraintes en niveaux de priorite : les contraintes MANDATORY sont dures (inviolables), les STRONG sont fortement preferees, les WEAK sont des souhaits. C’est la quatrieme famille de contraintes souples du jumeau Python — et la plus proche des vrais problemes de configuration de produit (PC, voiture, station de travail), ou l’on negocie des preferences sous des compatibilites non negociables.

Encodage lexicographique par facteur M : une seule fonction objectif M x cout_strong + cout_weak avec M > max(cout_weak) garantit qu’aucune accumulation de contraintes WEAK ne peut racheter une seule contrainte STRONG violee — la comparaison des paires (strong, weak) devient lexicographique bien que l’objectif soit scalaire.

Application (miroir exact de l’exemple resolu du jumeau Python, meme catalogue, meme M = 5) : configurer un PC — compatibilite socket et alimentation suffisante (MANDATORY), budget 820 EUR et score >= 145 (STRONG), marque AMD, boitier noir, garantie 7 ans (WEAK).

// Hierarchical CSP : Configuration PC — MANDATORY > STRONG > WEAK
// Miroir de l'exemple resolu du jumeau Python (OR-Tools CP-SAT) :
// meme catalogue, meme M = 5 — l'accord des deux moteurs sur l'optimum fait foi.

var model6 = new Model("HierarchicalCSP — Configuration PC");

// ---- Catalogue (identique au jumeau Python) ----
// socket : 0 = LGA1700 (Intel), 1 = AM4 (AMD) ; brand : 0 = AMD, 1 = Intel/Nvidia
string[] cpu6Names = { "Intel Core i5-12400", "Intel Core i7-12700", "AMD Ryzen 5 5600", "AMD Ryzen 7 5800X" };
int[] cpu6Socket = { 0, 0, 1, 1 };  int[] cpu6Tdp = { 65, 125, 65, 105 };
int[] cpu6Score  = { 70, 90, 68, 88 };  int[] cpu6Price = { 200, 350, 180, 300 };  int[] cpu6Brand = { 1, 1, 0, 0 };

string[] mb6Names = { "MSI PRO B660M", "Asus ROG Z690", "Gigabyte B550M", "Asus TUF B550" };
int[] mb6Socket = { 0, 0, 1, 1 };  int[] mb6Price = { 130, 250, 120, 160 };

string[] gpu6Names = { "RTX 3060", "RTX 3080", "RX 6600", "RX 6700 XT" };
int[] gpu6Tdp = { 170, 320, 132, 230 };  int[] gpu6Score = { 75, 95, 70, 82 };
int[] gpu6Price = { 320, 700, 270, 400 };  int[] gpu6Brand = { 1, 1, 0, 0 };

string[] psu6Names = { "Corsair CV 550W", "Corsair RM 750W", "BeQuiet 850W" };
int[] psu6Watt = { 550, 750, 850 };  int[] psu6Price = { 75, 110, 140 };  int[] psu6Warranty = { 3, 7, 5 };

string[] case6Names = { "NZXT H510", "Lian Li O11 Blanc", "Fractal Pop Rouge" };
int[] case6Color = { 0, 1, 2 };  int[] case6Price = { 90, 140, 100 };

int BUDGET6 = 820;    // EUR (serre, comme dans le jumeau Python)
int MIN_PERF6 = 145;  // score CPU + GPU minimum
int M6 = 5;           // facteur lexicographique : M > max violations WEAK (4)

// ---- Variables de decision ----
IntVar cpu6 = model6.intVar("cpu", 0, cpu6Names.Length - 1);
IntVar mb6 = model6.intVar("mb", 0, mb6Names.Length - 1);
IntVar gpu6 = model6.intVar("gpu", 0, gpu6Names.Length - 1);
IntVar psu6 = model6.intVar("psu", 0, psu6Names.Length - 1);
IntVar boitier6 = model6.intVar("boitier", 0, case6Names.Length - 1);

// ---- Attributs (element = table indexee par la variable) ----
IntVar cpuSocket6 = model6.intVar("cpu_socket", 0, 1);       model6.element(cpuSocket6, cpu6Socket, cpu6).post();
IntVar cpuTdp6 = model6.intVar("cpu_tdp", 0, 400);           model6.element(cpuTdp6, cpu6Tdp, cpu6).post();
IntVar cpuScore6 = model6.intVar("cpu_score", 0, 100);       model6.element(cpuScore6, cpu6Score, cpu6).post();
IntVar cpuPrice6 = model6.intVar("cpu_price", 0, 500);       model6.element(cpuPrice6, cpu6Price, cpu6).post();
IntVar cpuBrand6 = model6.intVar("cpu_brand", 0, 1);         model6.element(cpuBrand6, cpu6Brand, cpu6).post();
IntVar mbSocket6 = model6.intVar("mb_socket", 0, 1);         model6.element(mbSocket6, mb6Socket, mb6).post();
IntVar mbPrice6 = model6.intVar("mb_price", 0, 400);         model6.element(mbPrice6, mb6Price, mb6).post();
IntVar gpuTdp6 = model6.intVar("gpu_tdp", 0, 400);           model6.element(gpuTdp6, gpu6Tdp, gpu6).post();
IntVar gpuScore6 = model6.intVar("gpu_score", 0, 100);       model6.element(gpuScore6, gpu6Score, gpu6).post();
IntVar gpuPrice6 = model6.intVar("gpu_price", 0, 800);       model6.element(gpuPrice6, gpu6Price, gpu6).post();
IntVar gpuBrand6 = model6.intVar("gpu_brand", 0, 1);         model6.element(gpuBrand6, gpu6Brand, gpu6).post();
IntVar psuWatt6 = model6.intVar("psu_watt", 0, 1000);        model6.element(psuWatt6, psu6Watt, psu6).post();
IntVar psuPrice6 = model6.intVar("psu_price", 0, 200);       model6.element(psuPrice6, psu6Price, psu6).post();
IntVar psuWarranty6 = model6.intVar("psu_warranty", 0, 10);  model6.element(psuWarranty6, psu6Warranty, psu6).post();
IntVar caseColor6 = model6.intVar("case_color", 0, 2);       model6.element(caseColor6, case6Color, boitier6).post();
IntVar casePrice6 = model6.intVar("case_price", 0, 200);     model6.element(casePrice6, case6Price, boitier6).post();

IntVar totalPrice6 = model6.intVar("total_price", 0, 5000);
IntVar totalScore6 = model6.intVar("total_score", 0, 200);
IntVar totalTdp6 = model6.intVar("total_tdp", 0, 700);
model6.sum(new IntVar[] { cpuPrice6, mbPrice6, gpuPrice6, psuPrice6, casePrice6 }, "=", totalPrice6).post();
model6.sum(new IntVar[] { cpuScore6, gpuScore6 }, "=", totalScore6).post();
model6.sum(new IntVar[] { cpuTdp6, gpuTdp6 }, "=", totalTdp6).post();

// ---- MANDATORY : contraintes dures, postees (compatibilite socket, alimentation) ----
model6.arithm(cpuSocket6, "=", mbSocket6).post();
IntVar minWatt6 = model6.intVar("min_watt", 80, 780);
model6.arithm(minWatt6, "=", totalTdp6, "+", 80).post();
model6.arithm(psuWatt6, ">=", minWatt6).post();

// ---- STRONG : reifiees completement (ifThenElse = OnlyEnforceIf/Not de CP-SAT) ----
var overBudget6 = model6.boolVar("over_budget");
model6.ifThenElse(overBudget6,
    model6.arithm(totalPrice6, ">", BUDGET6),
    model6.arithm(totalPrice6, "<=", BUDGET6));
var lowPerf6 = model6.boolVar("low_perf");
model6.ifThenElse(lowPerf6,
    model6.arithm(totalScore6, "<", MIN_PERF6),
    model6.arithm(totalScore6, ">=", MIN_PERF6));

// ---- WEAK : souhaits reifies ----
var wrongCpuBrand6 = model6.boolVar("wrong_cpu_brand");
model6.ifThenElse(wrongCpuBrand6,
    model6.arithm(cpuBrand6, "!=", 0),
    model6.arithm(cpuBrand6, "=", 0));
var wrongGpuBrand6 = model6.boolVar("wrong_gpu_brand");
model6.ifThenElse(wrongGpuBrand6,
    model6.arithm(gpuBrand6, "!=", 0),
    model6.arithm(gpuBrand6, "=", 0));
var wrongColor6 = model6.boolVar("wrong_color");
model6.ifThenElse(wrongColor6,
    model6.arithm(caseColor6, "!=", 0),
    model6.arithm(caseColor6, "=", 0));
var shortWarranty6 = model6.boolVar("short_warranty");
model6.ifThenElse(shortWarranty6,
    model6.arithm(psuWarranty6, "<", 7),
    model6.arithm(psuWarranty6, ">=", 7));

// ---- Objectif lexicographique linearise : M*strong + weak (scalar, cf. section 1.3) ----
IntVar strongCost6 = model6.intVar("strong_cost", 0, 2);
model6.sum(new IntVar[] { overBudget6, lowPerf6 }, "=", strongCost6).post();
IntVar weakCost6 = model6.intVar("weak_cost", 0, 4);
model6.sum(new IntVar[] { wrongCpuBrand6, wrongGpuBrand6, wrongColor6, shortWarranty6 }, "=", weakCost6).post();
IntVar hierCost6 = model6.intVar("hier_cost", 0, M6 * 2 + 4);
model6.scalar(new IntVar[] { strongCost6, weakCost6 }, new int[] { M6, 1 }, "=", hierCost6).post();
model6.setObjective(false, hierCost6);   // false = MINIMIZE

var sw6 = System.Diagnostics.Stopwatch.StartNew();
var solver6 = model6.getSolver();
int bestCost6 = int.MaxValue, bc6 = 0, bm6 = 0, bg6 = 0, bp6 = 0, bk6 = 0, bStrong6 = 0, bWeak6 = 0;
while (solver6.solve()) {
    bestCost6 = hierCost6.getValue();
    bStrong6 = strongCost6.getValue();  bWeak6 = weakCost6.getValue();
    bc6 = cpu6.getValue();  bm6 = mb6.getValue();  bg6 = gpu6.getValue();
    bp6 = psu6.getValue();  bk6 = boitier6.getValue();
}
sw6.Stop();

string[] brands6 = { "AMD", "Intel/Nvidia" };
string[] colors6 = { "noir", "blanc", "rouge" };
int total6 = cpu6Price[bc6] + mb6Price[bm6] + gpu6Price[bg6] + psu6Price[bp6] + case6Price[bk6];
int score6 = cpu6Score[bc6] + gpu6Score[bg6];
int tdp6 = cpu6Tdp[bc6] + gpu6Tdp[bg6];

Console.WriteLine("Configuration PC optimale (Choco, " + sw6.ElapsedMilliseconds + " ms)");
Console.WriteLine();
Console.WriteLine($"  CPU         : {cpu6Names[bc6],-28}  {cpu6Price[bc6],4} EUR  score={cpu6Score[bc6]}  {brands6[cpu6Brand[bc6]]}");
Console.WriteLine($"  Carte mere  : {mb6Names[bm6],-28}  {mb6Price[bm6],4} EUR");
Console.WriteLine($"  GPU         : {gpu6Names[bg6],-28}  {gpu6Price[bg6],4} EUR  score={gpu6Score[bg6]}  {brands6[gpu6Brand[bg6]]}");
Console.WriteLine($"  Alimentation: {psu6Names[bp6],-28}  {psu6Price[bp6],4} EUR  {psu6Watt[bp6]}W  garantie {psu6Warranty[bp6]} ans");
Console.WriteLine($"  Boitier     : {case6Names[bk6],-28}  {case6Price[bk6],4} EUR  {colors6[case6Color[bk6]]}");
Console.WriteLine();
Console.WriteLine("=== Bilan ===");
Console.WriteLine($"  Prix total  : {total6} EUR  (budget {BUDGET6})  => {(total6 <= BUDGET6 ? "OK" : "DEPASSE de " + (total6 - BUDGET6) + " EUR")}");
Console.WriteLine($"  Score total : {score6}       (min {MIN_PERF6})   => {(score6 >= MIN_PERF6 ? "OK" : "INSUFFISANT")}");
Console.WriteLine($"  TDP total   : {tdp6}W + 80W = {tdp6 + 80}W  (alim {psu6Watt[bp6]}W)");
Console.WriteLine();
Console.WriteLine("Contraintes souples");
Console.WriteLine($"  [STRONG] Budget     : {(total6 <= BUDGET6 ? "satisfaite" : "VIOLEE")}");
Console.WriteLine($"  [STRONG] Perf min   : {(score6 >= MIN_PERF6 ? "satisfaite" : "VIOLEE")}");
Console.WriteLine($"  [WEAK]   Marque CPU : {brands6[cpu6Brand[bc6]]} {(cpu6Brand[bc6] == 0 ? "(prefere)" : "(non prefere -- compromis budget/perf)")}");
Console.WriteLine($"  [WEAK]   Marque GPU : {brands6[gpu6Brand[bg6]]} {(gpu6Brand[bg6] == 0 ? "(prefere)" : "(non prefere -- compromis budget/perf)")}");
Console.WriteLine($"  [WEAK]   Couleur    : {colors6[case6Color[bk6]]} {(case6Color[bk6] == 0 ? "(prefere)" : "(non prefere)")}");
Console.WriteLine($"  [WEAK]   Garantie   : {psu6Warranty[bp6]} ans {(psu6Warranty[bp6] >= 7 ? "(OK)" : "(courte)")}");
Console.WriteLine();
Console.WriteLine($"  Score objectif : {M6} x {bStrong6} (strong) + {bWeak6} (weak) = {bestCost6}");
Console.WriteLine("  Accord cross-moteurs : le jumeau Python (CP-SAT) trouve le meme objectif = 3 sur le meme catalogue.");

Configuration PC optimale (Choco, 12 ms)

  CPU         : Intel Core i5-12400            200 EUR  score=70  Intel/Nvidia
  Carte mere  : MSI PRO B660M                  130 EUR
  GPU         : RTX 3060                       320 EUR  score=75  Intel/Nvidia
  Alimentation: Corsair CV 550W                 75 EUR  550W  garantie 3 ans
  Boitier     : NZXT H510                       90 EUR  noir

=== Bilan ===
  Prix total  : 815 EUR  (budget 820)  => OK
  Score total : 145       (min 145)   => OK
  TDP total   : 235W + 80W = 315W  (alim 550W)

Contraintes souples
  [STRONG] Budget     : satisfaite
  [STRONG] Perf min   : satisfaite
  [WEAK]   Marque CPU : Intel/Nvidia (non prefere -- compromis budget/perf)
  [WEAK]   Marque GPU : Intel/Nvidia (non prefere -- compromis budget/perf)
  [WEAK]   Couleur    : noir (prefere)
  [WEAK]   Garantie   : 3 ans (courte)

  Score objectif : 5 x 0 (strong) + 3 (weak) = 3
  Accord cross-moteurs : le jumeau Python (CP-SAT) trouve le meme objectif = 3 sur le meme catalogue.

Interpretation : accord cross-moteurs — Choco (Java/IKVM, propagation + branch-and-bound) et CP-SAT (Python, SAT-based) trouvent le meme optimum objectif = 3 sur le meme catalogue : toutes les contraintes STRONG satisfaites (budget 815 <= 820, score 145 = 145), trois WEAK sacrifiees (marques CPU/GPU Intel/Nvidia, garantie 3 ans). C’est le budget serre qui force le compromis : a 820 EUR, la configuration 100% AMD preferee n’atteint pas le score STRONG — la hierarchie a arbitre exactement comme prevu : MANDATORY > STRONG > WEAK.

Points d’API : - le pattern ifThenElse(bool, contrainte, contrainte) est la reification complete equivalente au double OnlyEnforceIf(b) / OnlyEnforceIf(b.Not()) de CP-SAT — meme xor, deux idiomes ; le pattern etait deja apparu en section 3 pour le SoftAllDifferent ; - scalar({strong, weak}, {M, 1}) linearise l’ordre lexicographique en un seul objectif scalaire — la meme API croisee en section 1.3 pour le multi-objectif pondere ; - alternative native : re-optimiser sequentiellement niveau par niveau (figer strong a son optimum, puis minimiser weak) — meme resultat, deux appels solveur au lieu d’un.

Exercice 4 : Station de travail a budget 1200 EUR

Enonce : adaptez le Hierarchical CSP ci-dessus pour configurer une station de travail (pas un PC gamer) avec un budget de 1200 EUR.

Hierarchie des contraintes : - Requis (MANDATORY) : compatibilite CPU/carte-mere, alimentation suffisante - Important (STRONG) : 16 Go RAM minimum, SSD de 500 Go minimum - Souhaite (WEAK) : carte graphique dediee, boitier silencieux

Indices : 1. Inspirez-vous de la cellule Configuration PC ci-dessus 2. Adaptez le catalogue de composants pour une station de travail 3. Verifiez que la solution respecte le budget de 1200 EUR

// === EXERCICE 4 : Station de travail budget 1200 EUR (a completer) ===
// Squelette de depart : meme architecture que la Configuration PC ci-dessus.
// TODO etudiant 1 : definir le catalogue station de travail (CPU, RAM, SSD, GPU, boitier)
// TODO etudiant 2 : poster les contraintes MANDATORY (compatibilite socket, alimentation suffisante)
// TODO etudiant 3 : reifier les contraintes STRONG (RAM >= 16 Go, SSD >= 500 Go) puis WEAK (GPU dediee, boitier silencieux)
// TODO etudiant 4 : objectif = M*strong + weak avec M > |WEAK|, puis while (solver.solve())
var modelExo6 = new Model("Exercice 4 — Station de travail 1200 EUR (a completer)");
Console.WriteLine("Exercice 4 a completer : adaptez la Configuration PC (section 6) au budget 1200 EUR.");
Console.WriteLine("Etape 1 : definir le catalogue de composants (RAM et SSD deviennent des variables).");
Console.WriteLine("Etape 2 : poster MANDATORY (compatibilite, alimentation), reifier STRONG puis WEAK.");
Console.WriteLine("Etape 3 : objectif = M*strong + weak, M > |WEAK|, puis while (solverExo.solve()).");
Console.WriteLine("Verifier en fin : la solution respecte le budget de 1200 EUR.");

Exercice 4 a completer : adaptez la Configuration PC (section 6) au budget 1200 EUR.
Etape 1 : definir le catalogue de composants (RAM et SSD deviennent des variables).
Etape 2 : poster MANDATORY (compatibilite, alimentation), reifier STRONG puis WEAK.
Etape 3 : objectif = M*strong + weak, M > |WEAK|, puis while (solverExo.solve()).
Verifier en fin : la solution respecte le budget de 1200 EUR.

---

7. Exercices (règle #2161 : ≥ 3 exercices par notebook pédagogique)

Exercice 1 : Voyageur de commerce avec coût pondéré

On reprend le TSP 5 villes mais avec un coût d’essence variable par trajet (km × prix/litre du pays). Trouver la tournée qui minimise distance × prix_moyen.

Indices : 1. Utiliser circuit(succ) comme dans CSP-3 2. Ajouter une matrice prix[litre/km] par arête 3. Objectif : sum(distance[i,succ[i]] * prix[i,succ[i]]) minimisé

Stub de l’étudiant :

// === EXERCICE 1 : TSP avec coût pondéré distance × prix ===
Console.WriteLine("Exercice 1 - TSP pondéré : en attente de votre implementation");
Console.WriteLine("Schema :");
Console.WriteLine("  int n = 5;");
Console.WriteLine("  int[,] dist = { {0,3,1,5,8}, ... };");
Console.WriteLine("  double[] prixParKm = { 1.5, 1.2, 1.8, 1.3, 1.6 }; // par arête");
Console.WriteLine("  // Objectif : sum( dist[i,succ[i]] * prixParKm[i,succ[i]] ) minimum");
Console.WriteLine("  // Utiliser ScalProd avec termes par arête");

Exercice 1 - TSP pondéré : en attente de votre implementation
Schema :
  int n = 5;
  int[,] dist = { {0,3,1,5,8}, ... };
  double[] prixParKm = { 1.5, 1.2, 1.8, 1.3, 1.6 }; // par arête
  // Objectif : sum( dist[i,succ[i]] * prixParKm[i,succ[i]] ) minimum
  // Utiliser ScalProd avec termes par arête

Exercice 2 : Affectation de salles avec capacité souple

3 cours (C1, C2, C3), 4 salles (R1, R2, R3, R4) avec capacités différentes. Chaque cours a un nombre d’étudiants (coût si salle trop petite : 1pt par étudiant en dépassement ; coût si salle trop grande : 0.5pt par place vide).

Travail demandé : 1. Affecter chaque cours à une salle (x_i ∈ [0, 3]) 2. Contrainte dure : pas plus de 2 cours par salle 3. Coût : sum( pénalité_taille(cours_i, salle_x_i) ) 4. Minimiser le coût total

Solution attendue : coût ≈ 4 (cf. exercice 3 CSP-7-Soft.ipynb pour référence).

// === EXERCICE 2 : Affectation de salles avec capacité souple ===
int[] etudiants = { 25, 40, 30 };
int[] capacites = { 30, 50, 20, 35 };
int nCours7 = 3;
int nSalles7 = 4;
Console.WriteLine($"Exercice 2 - {nCours7} cours / {nSalles7} salles (capacités {string.Join(", ", capacites)})");
Console.WriteLine("En attente de votre implementation");
Console.WriteLine("Indices : element(coût_taille, table_pénalités, x_i) + sum + minimize");

Exercice 2 - 3 cours / 4 salles (capacités 30, 50, 20, 35)
En attente de votre implementation
Indices : element(coût_taille, table_pénalités, x_i) + sum + minimize

Exercice 3 : Emploi du temps avec indisponibilités pondérées

Un enseignant doit placer 4 créneaux de cours (1h chacun, lundi-vendredi). Il a 3 types de préférences : - A : créneau idéal (coût 0) - B : créneau acceptable (coût 1) - C : créneau à éviter (coût 5)

Trouver l’agencement qui minimise le coût total, sachant que : - 1 cours par jour max (contrainte dure) - Pas plus de 2 cours type C au total (contrainte dure)

Indices : 1. Variable : day[i] ∈ {0..4} (lundi-vendredi) 2. allDifferent(day) pour éviter les collisions 3. Pour chaque jour, type de créneau avec son coût 4. Variable count : sum(day_type[i] == C) ≤ 2 5. Minimiser coût total

// === EXERCICE 3 : Emploi du temps enseignant ===
// Préférences enseignant : lundi=A, mardi=A, mercredi=B, jeudi=B, vendredi=C
string[] prefLabels = { "A(idéal)", "A(idéal)", "B(OK)", "B(OK)", "C(à éviter)" };
int[] prefCosts = { 0, 0, 1, 1, 5 };
int nCours8 = 4;
int nJours8 = 5;
Console.WriteLine($"Exercice 3 - {nCours8} cours sur {nJours8} jours");
Console.WriteLine($"Préférences : {string.Join(", ", prefLabels)} (coûts {string.Join(", ", prefCosts)})");
Console.WriteLine("En attente de votre implementation");
Console.WriteLine("Contraintes : allDifferent(days) + max 2 type C + minimise sum(coût_jour_i)");

Exercice 3 - 4 cours sur 5 jours
Préférences : A(idéal), A(idéal), B(OK), B(OK), C(à éviter) (coûts 0, 0, 1, 1, 5)
En attente de votre implementation
Contraintes : allDifferent(days) + max 2 type C + minimise sum(coût_jour_i)

---

Conclusion et parité .NET ⇄ Python

Ce notebook démontre les primitives natives Choco 4.10.17 pour les CSP souples, en parité conceptuelle avec le CSP-7-Soft.ipynb Python (OR-Tools CP-SAT) :

Capacité CSP souple	Choco 4.10.17 (.NET)	OR-Tools CP-SAT (Python)	Parité
WeightedSum / Scalar	model.ScalProd(vars, coeffs, "=", obj)	model.AddScalProd(vars, coeffs) == obj	✅
élément indexé	model.Élément(result, table, index)	model.AddElement(table, index, result)	✅
Coût par violation	ReifyWith + IfThenElse + Sum	model.AddBoolOr + AddLinearConstraint	✅
Coût régulier (automate)	model.CostRegular(vars, cost, fa)	model.AddAutomaton + coûts explicites	✅
Multi-objectif pondéré	SetObjective(weighted_obj, MINIMIZE)	model.Minimize(weighted_obj)	✅
SoftAllDifferent	Réification pairwise + coût	model.AddForbiddenAssignments pondéré	✅
Framework sémiring	ISemiring<T> + SoftCsp<T> (section 5)	classe Semiring (ABC)	✅
CSP hiérarchique	ifThenElse (reification) + Scalar({strong,weak},{M,1}) (section 6)	OnlyEnforceIf + facteur M	✅

Verdict SOTA : SOTA-OK. Vrai solveur Choco exécuté réellement en-kernel via IKVM 8.15.0. Les deux twins partagent le problème de réunion Weighted CSP (même optimum : créneau 9h, coût total 1) mais couvrent par ailleurs des ensembles de sous-problèmes distincts (côté C# : routage sur graphe, SoftAllDifferent, multi-objectif pondéré ; côté Python : nurse scheduling équitable, voyage) — le framework sémiring, le CSP flou et la configuration PC hiérarchique étant désormais portés des deux côtés — avec accord numérique vérifié entre le framework générique et le moteur Choco (section 5), et entre Choco et CP-SAT sur le même catalogue PC (même optimum objectif = 3, section 6). La comparaison est donc conceptuelle (cf. table des capacités ci-dessus), pas une parité numérique cellule-à-cellule.

Leçons cross-cycle : - C146 : API Choco 4.10.17 — vérification bytecode strings extraction avant écriture de code IKVM - C147 : toute cellule ouvrant par #r "X" doit être précédée d’un commentaire // (CS1025) - C148 : .NET Interactive n’accepte PAS les blocs {...} au top-level — variables top-level avec noms distincts

Voir aussi : - CSP-7-Soft.ipynb — version Python (OR-Tools) - CSP-3-Advanced-CSharp.ipynb — tranche 3 marathon (contraintes globales) - CSP-4-Scheduling-CSharp.ipynb — tranche 1 marathon (scheduling) - CSP-5-Optimization-CSharp.ipynb — tranche 2 marathon (optimisation) - Issue #4956 — marathon parité .NET ⇄ Python

Part of #4956 (marathon parité .NET ⇄ Python série CSP). See #4711 (jurisprudence IKVM 8.15.0 + Choco).