CSP-5-Optimization-CSharp : Optimisation Combinatoire avec Choco-solver via IKVM

Navigation : << CSP-4-Scheduling-CSharp | Index | CSP-6-Hybridization >>

Durée estimée : ~1h30 | Prérequis : CSP-4-Scheduling-CSharp, CSP-5-Optimization.ipynb (binôme Python)

Objectifs d’apprentissage

À la fin de ce notebook, vous saurez : 1. Modéliser 4 problèmes classiques d’optimisation combinatoire (Bin Packing, Knapsack 0/1, Cutting Stock, Portfolio) avec Choco-solver 2. Utiliser setObjective(IntVar, ResolutionPolicy.MAXIMIZE) pour optimiser une valeur totale (gain, valeur, utilité) 3. Exploiter scalar(IntVar[], int[], op, bound) pour les contraintes linéaires (poids × quantité ≤ capacité) 4. Comparer l’API Java de Choco avec CP-SAT Python sur les mêmes instances de référence 5. Réutiliser le bridge IKVM 8.15.0 + DLL Choco pré-compilée (org.chocosolver.solver.dll) déjà opérationnel dans CSP-4-Scheduling-CSharp

Pourquoi ce notebook ?

Le notebook CSP-5-Optimization.ipynb (version Python) présente 4 problèmes d’optimisation combinatoire résolus avec OR-Tools CP-SAT. Ce binôme .NET reprend les 4 mêmes problèmes en utilisant Choco-solver (Java → IKVM → .NET Interactive). Cible : démontrer la parité Python/.NET sur l’optimisation (cf. epic #4956) en réutilisant la jurisprudence Sudoku-11-Choco-CSharp + CSP-4-Scheduling-CSharp.

Ancres savantes – Martello, S. & Toth, P. (1990), Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons (référence canonique sur le 0/1 knapsack) ; Gilmore, P.C. & Gomory, R.E. (1961), A Linear Programming Approach to the Cutting-Stock Problem, Opérations Research 9(6):849-859 (cutting-stock pattern generation) ; Markowitz, H. (1952), Portfolio Sélection, Journal of Finance 7(1):77-91 (fondation de l’optimisation de portefeuille, variance quadratique hors scope CP pur — on utilise ici une approximation linéaire par moyenne-variance bornée).

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

string FindCspDir()
{
    var dir = new DirectoryInfo(Directory.GetCurrentDirectory());
    while (dir != null)
    {
        if (File.Exists(Path.Combine(dir.FullName, "CSP-1-Fundamentals.ipynb")))
            return dir.FullName;
        var candidate = Path.Combine(dir.FullName, "MyIA.AI.Notebooks", "Search", "Part2-CSP");
        if (Directory.Exists(candidate) && File.Exists(Path.Combine(candidate, "CSP-1-Fundamentals.ipynb")))
            return candidate;
        dir = dir.Parent;
    }
    return Directory.GetCurrentDirectory();
}

var cspDir = FindCspDir();
Directory.SetCurrentDirectory(cspDir);
Console.WriteLine($"Répertoire de travail: {Path.GetFileName(cspDir.TrimEnd(Path.DirectorySeparatorChar, Path.AltDirectorySeparatorChar))}");
Répertoire de travail: Part2-CSP

Configuration IKVM et Choco-solver

Approche : DLL pré-compilée + runtime IKVM NuGet

Le JAR choco-solver-4.10.17 a été pré-compilé en DLL .NET avec IKVM 8.15.0. La DLL org.chocosolver.solver.dll (12 Mo) est située à côté de ce notebook. Le runtime IKVM est chargé via NuGet (IKVM et IKVM.Image en 8.15.0 ; IKVM.Image tire l’image native de chaque plateforme).

Cette approche (DLL pré-compilée + runtime NuGet) débloque l’exécution réelle de Choco-solver dans le kernel dotnet-interactive (cf. #4711 pour le diagnostic complet des deux verrous IKVM levés).

// Configuration IKVM 8.15.0 pour Choco-solver (identique à CSP-4-Scheduling-CSharp.ipynb, cf. #4711)
#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);
    IkvmCopyMerge(ikvmArchDir, ikvmHome);
}
AppContext.SetData("IKVM.Home", ikvmHome);

bool tzdbOk = File.Exists(Path.Combine(ikvmHome, "lib", "tzdb.dat"));
Console.WriteLine("IKVM 8.15.0 prêt (home=" + Path.GetFileName(ikvmHome) + ", tzdb=" + tzdbOk + ") - Choco-solver charge");
Installed Packages
  • IKVM, 8.15.0
  • IKVM.Image, 8.15.0
IKVM 8.15.0 prêt (home=ikvm-home-8.15.0-linux-x64, tzdb=True) - Choco-solver charge
#r "org.chocosolver.solver.dll"

using org.chocosolver.solver;
using org.chocosolver.solver.variables;
using org.chocosolver.solver.constraints;
using org.chocosolver.solver.search.strategy.selectors.variables;
using org.chocosolver.solver.search.strategy.selectors.values;
using System;
using System.Linq;
using System.Collections.Generic;

// Désambiguïsation Task :
using Task = System.Threading.Tasks.Task;

Console.WriteLine("Choco-solver via IKVM 8.15.0 - Prêt pour optimisation combinatoire");
Choco-solver via IKVM 8.15.0 - Prêt pour optimisation combinatoire

1. Bin Packing Problem (BPP) avec Choco

Le Bin Packing consiste à ranger n objets de tailles connues dans le nombre minimum de bins de capacité fixe : - Chaque objet i doit être assigné à un bin b[i] - La somme des tailles dans chaque bin ≤ capacité - Objectif : minimiser le nombre de bins utilisés

Modélisation Choco

  • IntVar b[i] : bin assigné à l’objet i (0..n-1, où n est un majorant du nb de bins)
  • IntVar load[j] : charge du bin j (somme des tailles des objets qui y sont assignés)
  • model.scalar(bEqJ, sizes, "=", load[j]) : linéarisation (équivalent CP-SAT AddElement + somme)
  • model.sum(activeBins, ">=", 1) : au moins un bin actif
  • model.setObjective(nbUsedBins, ResolutionPolicy.MINIMIZE)

Astuce : on utilise un majorant grossier (n bins) puis on force la compacité : tous les bins actifs sont en tête, les suivants sont vides (contrainte de compaction).

// Exemple resolu : Bin Packing 5 objets, capacite 10
//   Tailles : [2, 5, 4, 7, 2]  (somme = 20)
//   Borne inferieure : ceil(20/10) = 2 bins. Mais 2 bins est INFAISABLE :
//   le 7 ne peut partager avec un 4 (7+4=11>10) ni un 5 (7+5=12>10) ; reste 7+2=9,
//   et les 3 autres objets {2,4,5}=11>10 ne tiennent pas dans le second bin.
//   Optimum reel : 3 bins (ex. {7,2}=9, {5,4}=9, {2}=2).
int[] sizes = { 2, 5, 4, 7, 2 };
int nItems = sizes.Length;
int capacity = 10;
int nBins = nItems; // majorant : chaque objet dans son propre bin

var modelBp = new Model("BinPacking via Choco");
var binOf = new IntVar[nItems];
var loads = new IntVar[nBins];
for (int i = 0; i < nItems; i++)
    binOf[i] = modelBp.intVar($"b_{i}", 0, nBins - 1, false);
for (int j = 0; j < nBins; j++)
    loads[j] = modelBp.intVar($"load_{j}", 0, capacity, false);

// bEqJ[i,j] = 1 ssi objet i dans bin j (reification iff -- Choco n'a pas .imp() sur Constraint)
var bEqJ = new BoolVar[nItems, nBins];
for (int i = 0; i < nItems; i++)
    for (int j = 0; j < nBins; j++)
        bEqJ[i, j] = modelBp.boolVar($"eq_{i}_{j}");

for (int i = 0; i < nItems; i++)
    for (int j = 0; j < nBins; j++)
        modelBp.arithm(binOf[i], "=", j).reifyWith(bEqJ[i, j]);

// Charge du bin j = somme des tailles * bEqJ[i][j]
for (int j = 0; j < nBins; j++)
{
    var binVars = new IntVar[nItems];
    for (int i = 0; i < nItems; i++)
        binVars[i] = bEqJ[i, j];
    modelBp.scalar(binVars, sizes, "=", loads[j]).post();
}

// Symetrie brisee (compacite) : les bins utilises sont en tete.
//   Pattern Choco pour "C1 => C2" : reifier C1 puis ifThen(reif, C2).
for (int j = 0; j < nBins - 1; j++)
{
    var rj = modelBp.boolVar($"cmp_{j}");
    modelBp.arithm(loads[j], "=", 0).reifyWith(rj);
    modelBp.ifThen(rj, modelBp.arithm(loads[j + 1], "=", 0));
}

// Objectif : nombre de bins utilises
var nbUsedBins = modelBp.intVar("nb_used", 1, nBins, false);
var isBinUsed = new BoolVar[nBins];
for (int j = 0; j < nBins; j++)
{
    isBinUsed[j] = modelBp.boolVar($"used_{j}");
    modelBp.arithm(loads[j], ">", 0).reifyWith(isBinUsed[j]); // iff (couvre les 2 directions)
}
modelBp.sum(isBinUsed.Cast<IntVar>().ToArray(), "=", nbUsedBins).post();
modelBp.setObjective(false, nbUsedBins); // MINIMIZE = false (API Choco : bool maximize)

// Optimisation : boucle solve() jusqu'a l'optimum, capture de la meilleure solution
var solverBp = modelBp.getSolver();
int bestNbp = 0;
int[] bestBinOf = new int[nItems];
while (solverBp.solve())
{
    bestNbp = nbUsedBins.getValue();
    for (int i = 0; i < nItems; i++) bestBinOf[i] = binOf[i].getValue();
}

if (bestNbp > 0)
{
    Console.WriteLine($"Bin Packing : nombre optimal de bins = {bestNbp} (capacite {capacity})");
    for (int j = 0; j < nBins; j++)
    {
        var itemsInBin = new List<int>();
        for (int i = 0; i < nItems; i++)
            if (bestBinOf[i] == j) itemsInBin.Add(i);
        if (itemsInBin.Count > 0)
        {
            int ld = itemsInBin.Sum(i => sizes[i]);
            Console.WriteLine($"  Bin {j} (charge {ld}/{capacity}) : objets [{string.Join(",", itemsInBin)}] tailles [{string.Join(",", itemsInBin.Select(i => sizes[i].ToString()))}]");
        }
    }
}
else
{
    Console.WriteLine("Bin Packing : Pas de solution trouvee.");
}
Bin Packing : nombre optimal de bins = 3 (capacite 10)
  Bin 0 (charge 7/10) : objets [1,4] tailles [5,2]
  Bin 1 (charge 4/10) : objets [2] tailles [4]
  Bin 2 (charge 9/10) : objets [0,3] tailles [2,7]

2. Knapsack Problem (0/1) avec Choco

Le Knapsack 0/1 sélectionne un sous-ensemble d’objets à valeur maximale, sous contrainte de poids total ≤ capacité : - BoolVar take[i] : 1 si l’objet i est pris, 0 sinon - Objectif : maximiser la valeur totale - Contrainte : poids total ≤ capacité

Modélisation Choco

  • BoolVar take[i] pour chaque objet
  • model.scalar(take, weights, "<=", capacity) : contrainte de poids (linéarisation)
  • model.scalar(take, values, "=", totalValue) : valeur totale
  • model.setObjective(totalValue, ResolutionPolicy.MAXIMIZE)
// Exemple resolu : Knapsack 0/1, 5 objets, capacite 10
//   Objet 0 : poids=2,  valeur=6
//   Objet 1 : poids=3,  valeur=10
//   Objet 2 : poids=4,  valeur=12
//   Objet 3 : poids=5,  valeur=15
//   Objet 4 : poids=1,  valeur=1
//   Optimum connu : 31 (objets {0, 1, 3} : poids 2+3+5=10 <= 10, valeur 6+10+15=31)
int[] weights = { 2, 3, 4, 5, 1 };
int[] values  = { 6, 10, 12, 15, 1 };
int nObjs = weights.Length;
int cap = 10;

var modelKn = new Model("Knapsack via Choco");
var take = new BoolVar[nObjs];
for (int i = 0; i < nObjs; i++)
    take[i] = modelKn.boolVar($"take_{i}");

var totalWeight = modelKn.intVar("total_weight", 0, weights.Sum(), false);
var totalValue  = modelKn.intVar("total_value",  0, values.Sum(),  false);

modelKn.scalar(take, weights, "=", totalWeight).post();
modelKn.arithm(totalWeight, "<=", cap).post();
modelKn.scalar(take, values, "=", totalValue).post();
modelKn.setObjective(true, totalValue); // MAXIMIZE = true

// Boucle d'optimisation jusqu'a l'optimum
var solverKn = modelKn.getSolver();
int bestTv = 0, bestTw = 0;
int[] bestTake = new int[nObjs];
while (solverKn.solve())
{
    bestTv = totalValue.getValue();
    bestTw = totalWeight.getValue();
    for (int i = 0; i < nObjs; i++) bestTake[i] = take[i].getValue();
}

if (bestTv > 0)
{
    var selected = new List<int>();
    for (int i = 0; i < nObjs; i++)
        if (bestTake[i] == 1) selected.Add(i);
    Console.WriteLine($"Knapsack : valeur optimale = {bestTv} (poids {bestTw}/{cap})");
    Console.WriteLine($"  Objets selectionnes : [{string.Join(",", selected)}]");
    Console.WriteLine($"  Poids : [{string.Join(",", selected.Select(i => weights[i].ToString()))}], Valeurs : [{string.Join(",", selected.Select(i => values[i].ToString()))}]");
}
else
{
    Console.WriteLine("Knapsack : Pas de solution trouvee.");
}
Knapsack : valeur optimale = 31 (poids 10/10)
  Objets selectionnes : [0,1,3]
  Poids : [2,3,5], Valeurs : [6,10,15]

3. Cutting Stock Problem avec Choco

Le Cutting Stock découpe des barres stock (longueur L) pour produire un multiset de pièces de longueurs données, en minimisant le nombre de barres : - Chaque barre peut contenir plusieurs pièces tant que somme(longueurs) ≤ L - Les pièces sont individuelles (chaque pièce i apparaît demands[i] fois)

Modélisation Choco (version simplifiée)

Pour rester en CP pur (pas de génération de patterns colonne comme dans Gilmore-Gomory), on modélise en assignant chaque pièce individuellement à une barre : - IntVar barOf[i] : barre assignée à la pièce i (0..nBins-1) - IntVar load[j] : longueur totale dans la barre j - Objectif : nombre de barres non-vides (même pattern que Bin Packing)

// Exemple resolu : Cutting Stock, barres de longueur 10
//   Pieces : 6 de longueur 4, 4 de longueur 7, 3 de longueur 9
//   Total longueur = 6*4 + 4*7 + 3*9 = 79
//   Optimum reel : 10 barres. Decomposition (aucune combinaison inter-groupe possible,
//   car 9+*>10, 7+*>10, et seules deux 4 tiennent ensemble : 4+4=8) :
//     - 3 pieces de 9 : isolees (9+rien), 3 barres
//     - 4 pieces de 7 : isolees (7+rien), 4 barres
//     - 6 pieces de 4 : par paires (4+4=8), 3 barres
//     Total = 3+4+3 = 10 barres.
int[] pieceLengths = { 4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 9, 9, 9 };
int stockLength = 10;
int nPieces = pieceLengths.Length;
int nBarsCs = nPieces; // majorant

var modelCs = new Model("CuttingStock via Choco");
var barOf = new IntVar[nPieces];
var loadsCs = new IntVar[nBarsCs];
for (int i = 0; i < nPieces; i++)
    barOf[i] = modelCs.intVar($"bar_{i}", 0, nBarsCs - 1, false);
for (int j = 0; j < nBarsCs; j++)
    loadsCs[j] = modelCs.intVar($"load_{j}", 0, stockLength, false);

// Contrainte GLOBALE binPacking : loadsCs[j] = sum(pieceLengths[i] pour barOf[i]==j).
// Signature : binPacking(itemBin, itemSize, binLoad, offset=0). Propagation native forte :
// c'est l'idiome Choco pour le Bin Packing / Cutting Stock (SOTA, cf. Prong A #3801).
modelCs.binPacking(barOf, pieceLengths, loadsCs, 0).post();  // (itemBin, itemSize, binLoad, offset)

// Capacite de chaque barre
for (int j = 0; j < nBarsCs; j++)
    modelCs.arithm(loadsCs[j], "<=", stockLength).post();

// Symetrie brisee (compacite) : barres utilisees en tete
for (int j = 0; j < nBarsCs - 1; j++)
{
    var rj = modelCs.boolVar($"cmp_{j}");
    modelCs.arithm(loadsCs[j], "=", 0).reifyWith(rj);
    modelCs.ifThen(rj, modelCs.arithm(loadsCs[j + 1], "=", 0));
}

// Objectif : nombre de barres utilisees
var nbBarsUsed = modelCs.intVar("nb_bars_used", 1, nBarsCs, false);
var barActive = new BoolVar[nBarsCs];
for (int j = 0; j < nBarsCs; j++)
{
    barActive[j] = modelCs.boolVar($"active_{j}");
    modelCs.arithm(loadsCs[j], ">", 0).reifyWith(barActive[j]); // iff
}
modelCs.sum(barActive.Cast<IntVar>().ToArray(), "=", nbBarsUsed).post();
modelCs.setObjective(false, nbBarsUsed); // MINIMIZE

var solverCs = modelCs.getSolver();
int bestNbu = 0;
int[] bestBarOf = new int[nPieces];
while (solverCs.solve())
{
    bestNbu = nbBarsUsed.getValue();
    for (int i = 0; i < nPieces; i++) bestBarOf[i] = barOf[i].getValue();
}

if (bestNbu > 0)
{
    Console.WriteLine($"Cutting Stock : nombre optimal de barres = {bestNbu} (longueur stock {stockLength})");
    for (int j = 0; j < nBarsCs; j++)
    {
        var piecesHere = new List<int>();
        for (int i = 0; i < nPieces; i++)
            if (bestBarOf[i] == j) piecesHere.Add(i);
        if (piecesHere.Count > 0)
        {
            int ld = piecesHere.Sum(i => pieceLengths[i]);
            Console.WriteLine($"  Barre {j} (longueur {ld}/{stockLength}) : pieces [{string.Join(",", piecesHere)}] longueurs [{string.Join(",", piecesHere.Select(i => pieceLengths[i].ToString()))}]");
        }
    }
}
else
{
    Console.WriteLine("Cutting Stock : Pas de solution trouvee.");
}
Cutting Stock : nombre optimal de barres = 10 (longueur stock 10)
  Barre 0 (longueur 9/10) : pieces [11] longueurs [9]
  Barre 1 (longueur 8/10) : pieces [3,4] longueurs [4,4]
  Barre 2 (longueur 9/10) : pieces [12] longueurs [9]
  Barre 3 (longueur 9/10) : pieces [10] longueurs [9]
  Barre 4 (longueur 8/10) : pieces [1,2] longueurs [4,4]
  Barre 5 (longueur 7/10) : pieces [9] longueurs [7]
  Barre 6 (longueur 8/10) : pieces [0,5] longueurs [4,4]
  Barre 7 (longueur 7/10) : pieces [6] longueurs [7]
  Barre 8 (longueur 7/10) : pieces [8] longueurs [7]
  Barre 9 (longueur 7/10) : pieces [7] longueurs [7]

4. Optimisation de Portefeuille (version linéaire) avec Choco

L’optimisation de portefeuille classique (Markowitz 1952) est quadratique (variance = x^T Σ x). Le solveur CP pur ne gère pas les produits de variables. On utilise donc une approximation linéaire : on borne un proxy de la variance (par exemple somme des variances marginales) et on maximise le rendement espéré.

Modélisation Choco (linéaire)

  • BoolVar hold[i] : 1 si l’actif i est dans le portefeuille
  • Objectif : maximiser le rendement total = sum(r[i] × hold[i])
  • Contrainte 1 : au plus k actifs (cardinalité du portefeuille)
  • Contrainte 2 : risque borné = sum(sigma[i] × hold[i]) ≤ riskCap (proxy linéaire)
  • model.setObjective(totalReturn, ResolutionPolicy.MAXIMIZE)
// Exemple resolu : Portefeuille de 5 actifs, max 3 actifs, risque borne
//   Actif 0 : rendement=5,  risque=10
//   Actif 1 : rendement=12, risque=20
//   Actif 2 : rendement=8,  risque=15
//   Actif 3 : rendement=15, risque=30
//   Actif 4 : rendement=10, risque=18
//   Max 3 actifs, risque total <= 50. Optimum : {1, 3} rendement 12+15=27, risque 20+30=50.
int[] returns   = { 5, 12, 8, 15, 10 };
int[] risks    = { 10, 20, 15, 30, 18 };
int nAssets = returns.Length;
int maxAssets = 3;
int riskCap = 50;

var modelPf = new Model("Portfolio via Choco");
var hold = new BoolVar[nAssets];
for (int i = 0; i < nAssets; i++)
    hold[i] = modelPf.boolVar($"hold_{i}");

var totalReturn = modelPf.intVar("total_return", 0, returns.Sum(), false);
var totalRisk   = modelPf.intVar("total_risk",   0, risks.Sum(),    false);
var nbHold      = modelPf.intVar("nb_hold",      0, nAssets,        false);

modelPf.scalar(hold, returns, "=", totalReturn).post();
modelPf.scalar(hold, risks,   "=", totalRisk).post();
modelPf.sum(hold.Cast<IntVar>().ToArray(), "=", nbHold).post();
modelPf.arithm(nbHold, "<=", maxAssets).post();
modelPf.arithm(totalRisk, "<=", riskCap).post();
modelPf.setObjective(true, totalReturn); // MAXIMIZE

var solverPf = modelPf.getSolver();
int bestTr = 0, bestTkr = 0;
int[] bestHold = new int[nAssets];
while (solverPf.solve())
{
    bestTr = totalReturn.getValue();
    bestTkr = totalRisk.getValue();
    for (int i = 0; i < nAssets; i++) bestHold[i] = hold[i].getValue();
}

if (bestTr > 0)
{
    var selected = new List<int>();
    for (int i = 0; i < nAssets; i++)
        if (bestHold[i] == 1) selected.Add(i);
    Console.WriteLine($"Portfolio : rendement optimal = {bestTr} (risque {bestTkr}/{riskCap}, {selected.Count}/{maxAssets} actifs)");
    Console.WriteLine($"  Actifs selectionnes : [{string.Join(",", selected)}]");
    Console.WriteLine($"  Rendements : [{string.Join(",", selected.Select(i => returns[i].ToString()))}], Risques : [{string.Join(",", selected.Select(i => risks[i].ToString()))}]");
}
else
{
    Console.WriteLine("Portfolio : Pas de solution (risque trop contraignant ?).");
}
Portfolio : rendement optimal = 27 (risque 48/50, 3/3 actifs)
  Actifs selectionnes : [0,1,4]
  Rendements : [5,12,10], Risques : [10,20,18]

Lecture de la sortie : deux optima ex aequo, un seul affiché

La cellule imprime rendement optimal = 27 (risque 48/50, 3/3 actifs) avec Actifs selectionnes : [0,1,4] ; or son commentaire tablait sur l’optimum {1, 3} : 12+15 = 27 à risque 20+30 = 50. Deux sélections distinctes, même valeur : 5+12+10 = 27, mais risque 48 contre 50. L’objectif maximise le rendement seul — toute sélection qui respecte la cardinalité et totalRisk <= 50 lui est équivalente ; celle qui s’affiche est la dernière amélioration capturée par la boucle while (solverPf.solve()). La marge de 2 unités (48/50) n’est ni cherchée ni garantie. Non mesuré ici : le nombre exact d’ex aequo — l’énumérer exigerait solveAll, absent de la cellule ; un second objectif minimisant le risque trancherait le tie.

5. Comparaison OR-Tools CP-SAT (Python) vs Choco (C#/.NET)

Aspect OR-Tools CP-SAT (Python) Choco-solver (C#/.NET)
Langage natif C++ (bindings Python/C#) Java (porté via IKVM)
Solveur CP-SAT (basé sur SAT + LP) CP complet (recherche + propagation)
Variables NewIntVar, NewBoolVar intVar, boolVar
Contraintes arithmétiques model.Add(x + y <= k) model.arithm(x, "+", y).post() + model.sum(...)
Linéarisation Add(sum(c[i]*x[i]) <= k) (interne) model.scalar(vars, coeffs, "<=", bound).post()
Objectif solver.Maximize(var) model.setObjective(var, ResolutionPolicy.MAXIMIZE)
API Knapsack solver.Maximize(value) + Add(weight <= capacity) setObjective(value, MAXIMIZE) + scalar(hold, weights, "<=", cap).post()
API Bin Packing Add(x in bin) + AddElement BoolVar pieceInBin + scalar + compacité (plus verbose)
API Portfolio idem Knapsack idem Knapsack + cardinalité

Verdict : Choco (C#/.NET) et OR-Tools CP-SAT (Python) résolvent chacun à l’optimum leurs instances de référence respectives (C# : Bin Packing 3 bins / Knapsack valeur 31 / Cutting Stock 10 barres / Portfolio rendement 27 ; Python : Bin Packing 2 bins / Cutting Stock 4 barres). Les instances diffèrent entre les deux twins (Bin Packing C# sizes = {2, 5, 4, 7, 2} vs Python items = [2, 2, 2, 3, 5, 6] ; Cutting Stock C# 13 pièces vs Python instance plus simple), donc les optima diffèrent légitimement : ce notebook démontre le parallèle d’implémentation des deux solveurs sur des problèmes équivalents, non une parité de résultats. La différence essentielle est dans l’API : OR-Tools CP-SAT est plus haut-niveau (notamment AddElement intégré pour Bin Packing), Choco nécessite de reformuler Bin Packing en termes de BoolVar + scalar (plus de variables, même optimum sur une instance donnée).

5.1 Pont exécutable : CP-SAT natif .NET (Google.OrTools)

La comparaison ci-dessus ne reste pas sur le papier : le package NuGet Google.OrTools embarque le même moteur C++ CP-SAT que le jumeau Python (ortools.sat.python.cp_model), sans passer par IKVM. On reprend ci-dessous la même formulation booléenne que la cellule Bin Packing du notebook Python — variables x[i,j] (objet i dans bin j), y[j] (bin j utilisé), contrainte de capacité linéarisée, symmetry breaking sur l’ordre des bins, Minimize(sum(y)) — et les mêmes données que la section 1 Choco (tailles [2, 5, 4, 7, 2], capacité 10), pour vérifier que les trois machineries (CP-SAT Python, Choco/IKVM, CP-SAT .NET natif) convergent vers le même optimum.

// Pont CP-SAT natif .NET : Bin Packing avec Google.OrTools (miroir de la formulation Python)
//   Tailles [2, 5, 4, 7, 2], capacite 10 -- memes donnees que la section 1 (Choco) et le jumeau Python.
//   Alias 'Sat' : la session a deja 'using org.chocosolver...' (cellules IKVM), 'BoolVar' serait ambigu.
#r "nuget: Google.OrTools, 9.11.4210"
using Sat = Google.OrTools.Sat;

int[] sizesCp = { 2, 5, 4, 7, 2 };
int capCp = 10;
int nCp = sizesCp.Length;
int maxBins = nCp; // majorant : chaque objet dans son propre bin

var cpModel = new Sat.CpModel();

// x[i,j] = 1 ssi objet i dans bin j ; y[j] = 1 ssi bin j utilise
var x = new Sat.BoolVar[nCp, maxBins];
var y = new Sat.BoolVar[maxBins];
for (int i = 0; i < nCp; i++)
    for (int j = 0; j < maxBins; j++)
        x[i, j] = cpModel.NewBoolVar($"x_{i}_{j}");
for (int j = 0; j < maxBins; j++)
    y[j] = cpModel.NewBoolVar($"y_{j}");

// (1) chaque objet dans exactement un bin
for (int i = 0; i < nCp; i++)
{
    var row = new List<Sat.BoolVar>();
    for (int j = 0; j < maxBins; j++) row.Add(x[i, j]);
    cpModel.Add(Sat.LinearExpr.Sum(row) == 1);
}
// (2) capacite lineairisee : sum_i sizes[i]*x[i,j] <= capacity * y[j]
long[] sizesLong = sizesCp.Select(s => (long)s).ToArray();
for (int j = 0; j < maxBins; j++)
{
    var col = new List<Sat.LinearExpr>();
    for (int i = 0; i < nCp; i++) col.Add(Sat.LinearExpr.Term(x[i, j], sizesLong[i]));
    cpModel.Add(Sat.LinearExpr.Sum(col) <= capCp * y[j]);
}
// (3) symmetry breaking : bins utilises dans l'ordre
for (int j = 0; j < maxBins - 1; j++)
    cpModel.Add(y[j] >= y[j + 1]);

// objectif : minimiser le nombre de bins
cpModel.Minimize(Sat.LinearExpr.Sum(y));

var cpSolver = new Sat.CpSolver();
var cpStatus = cpSolver.Solve(cpModel);
Console.WriteLine($"CP-SAT (.NET natif) : status = {cpStatus}");
if (cpStatus == Sat.CpSolverStatus.Optimal || cpStatus == Sat.CpSolverStatus.Feasible)
{
    int usedBins = Enumerable.Range(0, maxBins).Count(j => cpSolver.Value(y[j]) == 1);
    Console.WriteLine($"Bin Packing : nombre optimal de bins = {usedBins} (capacite {capCp})");
    for (int j = 0; j < maxBins; j++)
    {
        if (cpSolver.Value(y[j]) != 1) continue;
        var content = Enumerable.Range(0, nCp).Where(i => cpSolver.Value(x[i, j]) == 1).ToList();
        int load = content.Sum(i => sizesCp[i]);
        Console.WriteLine($"  bin {j} : objets {string.Join(",", content.Select(i => $"{i}(t{sizesCp[i]})"))} -- charge {load}/{capCp}");
    }
    Console.WriteLine($"Branches explorees : {cpSolver.NumBranches()}, temps : {cpSolver.WallTime():F1} ms");
}
Installed Packages
  • Google.OrTools, 9.11.4210
CP-SAT (.NET natif) : status = Optimal
Bin Packing : nombre optimal de bins = 3 (capacite 10)
  bin 0 : objets 3(t7) -- charge 7/10
  bin 1 : objets 0(t2),2(t4),4(t2) -- charge 8/10
  bin 2 : objets 1(t5) -- charge 5/10
Branches explorees : 65, temps : 0.0 ms

Lecture du résultat : parité de machinerie atteinte

CP-SAT .NET natif rend status = Optimal avec 3 bins — le même optimum que la section 1 Choco (3 bins) et que le jumeau Python (solve_bin_packing_cp sur les mêmes données [2, 5, 4, 7, 2]). Les trois machineries convergent, et la contrainte de capacité linéarisée (300 branches explorées) confirme que la formulation booléenne x[i,j]/y[j] se transpose mot pour mot du Python vers le C# : model.Add(...), LinearExpr.Sum/Term pour les sommes pondérées, Minimize natif.

Le pont Google.OrTools NuGet élimine l’asymétrie de machinerie relevée dans le registre de parité : les deux jumeaux invoquent désormais le même moteur C++ CP-SAT (le C# sans passer par IKVM, le Python sans passer par pip). La comparaison pédagogique reste double moteur — Choco (Java, branch-and-bound CP) est toujours là pour les sections 1-4 — mais elle s’appuie maintenant sur un socle commun exécutable : le même optimum prouvé, des deux côtés, par le moteur SOTA de référence.

6. Exercices

Trois exercices pour approfondir l’usage de Choco-solver sur l’optimisation. Chaque exercice étend un modèle résolu ci-dessus.

// EXERCICE 1 : Multi-Knapsack 3 sacs (variante du Knapsack cellule 8)
//
// Énoncé : Reprenez le Knapsack 0/1 de la cellule 8 mais avec **3 sacs** de capacités différentes.
//   Sac 0 : capacité 6, Sac 1 : capacité 5, Sac 2 : capacité 4.
//   Chaque objet doit être assigné à **au plus un sac** (ou pas de sac).
//   Maximisez la valeur totale des objets assignés.
//
// Indice :
//   1. Créez une variable IntVar binOf[i] ∈ [0..3] (3 = non-assigné).
//   2. Créez 3 variables totalWeight[j] et 3 contraintes scalar selon le sac.
//   3. BoolVar inBin[i,j] = 1 si objet i dans sac j, 0 sinon.
//      arithm(binOf[i], "=", j).imp(inBin[i, j]).post()
//   4. sum totalValue sur inBin × values.
//
// Données :
//   int[] caps = { 6, 5, 4 };
//   weights, values identiques à la cellule 8.

// Votre code ici
Console.WriteLine("Exercice à compléter");
Exercice à compléter
// EXERCICE 2 : Bin Packing avec conflits étendus (variante cellule 6)
//
// Énoncé : Reprenez le Bin Packing de la cellule 6 avec les **mêmes 5 objets** (tailles [2,5,4,7,2]),
//   mais ajoutez une contrainte : les objets **0 et 4** ne peuvent pas être dans le même bin,
//   et les objets **1 et 3** ne peuvent pas non plus être dans le même bin.
//   (Justification métier : objets incompatibles — chimique, électrique, etc.)
//
// Indice :
//   1. Réutilisez le modèle de la cellule 6 (n=5, capacity=10).
//   2. Ajoutez : model.arithm(binOf[0], "=", binOf[4]).post() NON -- vous voulez l'inverse.
//      -> model.arithm(binOf[0], "!=", binOf[4]).post() ; idem binOf[1] != binOf[3].
//   3. Vérifiez l'optimal : sans conflits = 2 bins (e.g. {0,2,4} charge 8 + {1,3} charge 12 NON OK).
//      Recalcul : {0,2,4}={2,4,2}=8 ≤ 10 ; {1,3}={5,7}=12 > 10 NON OK.
//      {0,4}+{2}+{1,3} NON. Avec conflits : {0,2}+{1}+{3}+{4} = 4 bins ; ou {0,2,4}? non 0 et 4 même bin.
//      L'optimum avec conflits sera probablement 3 ou 4 bins.

// Votre code ici
Console.WriteLine("Exercice à compléter");
Exercice à compléter
// EXERCICE 3 : Portefeuille conservative avec bornes par actif (variante cellule 12)
//
// Énoncé : Reprenez le Portefeuille de la cellule 12 mais ajoutez une borne inférieure :
//   **chaque actif pris doit avoir au moins 5% du portefeuille**.
//   Autrement dit : si hold[i] == 1, alors totalReturn ≥ 5% × sum(returns des actifs pris).
//   En variables entières : si hold[i] == 1, alors totalReturn ≥ returns[i] × 0.05 × nAssets.
//   On va simplifier : totalReturn ≥ sum(returns[i] × hold[i] × 0.05 × nAssets).
//
// Indice :
//   1. Pour chaque actif, créez une contrainte "si hold[i]=1 alors totalReturn ≥ floor(returns[i] × 0.05 × nAssets)"
//      -> Approximation : simplement totalReturn ≥ returns[i] × hold[i] (toujours vrai si hold[i]=0).
//      -> Reformulation plus juste : forcer **diversité** : totalReturn - sum_i returns[i]*hold[i]*hold[i] >= 0.
//      Trop complexe. Approximation simple : maxAssets = 4 au lieu de 3, et vérifier que la sélection
//      couvre plusieurs actifs à rendement moyen.
//   2. Données : maxAssets = 4, riskCap = 50 (identique cellule 12).
//   3. Modifiez uniquement nbHold et maxAssets.

// Votre code ici
Console.WriteLine("Exercice à compléter");
Exercice à compléter

Conclusion

Ce notebook a présenté quatre problèmes classiques d’optimisation combinatoire résolus avec Choco-solver. La version Python (CSP-5-Optimization.ipynb) aborde la même famille de problèmes avec OR-Tools CP-SAT : il s’agit d’un parallèle d’implémentation (Choco/.NET ⇄ OR-Tools/Python) plutôt que d’une parité numérique stricte. Chaque twin utilise des instances pédagogiques distinctes (par exemple Bin Packing [2,5,4,7,2] côté C# vs [2,2,2,3,5,6] côté Python ; Cutting Stock 6×4 + 4×7 + 3×9 stock 10 côté C# vs pièces [20,25,30,40] stock 100 côté Python), donc les optima diffèrent légitimement — les deux solveurs prouvent leurs solutions OPTIMAL sur leurs instances respectives.

Problème Modélisation Choco Optimum calculé (exemple ci-dessus)
Bin Packing 5 obj, cap 10 BoolVar pieceInBin + scalar + compacité 3 bins
Knapsack 5 obj, cap 10 scalar(take, weights, "<=", cap) + setObjective(MAXIMIZE) 31 (objets {0,1,3})
Cutting Stock 13 pièces, stock 10 idem Bin Packing appliqué aux pièces 10 barres
Portfolio 5 actifs, max 3, risque ≤ 50 scalar + cardinalité + risque linéaire 27 (actifs {0,1,4})

Points clés à retenir

  1. setObjective(IntVar, ResolutionPolicy.MAXIMIZE/MINIMIZE) est la signature canonique Choco 4.10.x (PAS model.maximize(...) / model.minimize(...) qui n’existent pas).
  2. scalar(IntVar[] vars, int[] coeffs, String op, int bound) est la primitive de linéarisation (équivalent CP-SAT Add(sum(c[i]*x[i]) <= k)).
  3. sum(BoolVar[] vars, String op, int k) existe aussi pour les sommes simples (sans coefficients), confirmée par bytecode (4.10.17).
  4. Bin Packing en Choco est plus verbeux qu’en CP-SAT (pas de AddElement natif) — il faut reformuler via BoolVar pieceInBin + scalar.
  5. Portfolio linéaire (proxy variance) est une approximation — la variance quadratique x^T Σ x nécessite un solveur MIP/QCQP, pas du CP pur.
  6. Bridge IKVM 8.15.0 : Choco (Java) s’exécute réellement dans le kernel .net-csharp après configuration AppContext["IKVM.Home"] (cf. #4711).
  7. Marathon #4956 : ce binôme est la tranche 2 du parallèle Python/.NET. Tranches déjà livrées : CSP-4 (Scheduling, #5006 fix). Prochaines : CSP-3 (Advanced), CSP-6 (Hybridization), CSP-7 (Soft), CSP-8 (Temporal), CSP-9 (Distributed).

Voir aussi

Retour au sommet