CSP-5-Optimization : Problèmes d’Optimisation Combinatoire

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

Durée estimée : 2h00

Optimisation Combinatoire en Programmation par Contraintes

Ce notebook explore les problèmes d’optimisation combinatoire classiques résolus par CP.

Objectifs

À la fin de ce notebook, vous saurez : 1. Résoudre le Bin Packing Problem (BPP) avec CP-SAT 2. Implémenter le Knapsack Problem 0/1 3. Modéliser le Cutting Stock Problem 4. Appliquer au Portfolio Optimization

Prérequis

  • Notebooks CSP-1 à CSP-3 (fondements CSP)
  • CSP-4-Scheduling (ordonnancement)
  • Python 3.10+ : ortools, matplotlib, numpy
  • Notions de base en optimisation combinatoire

Ancres savantes – Dantzig, G.B. (1957), Discrete-Variable Extremum Problems, Opérations Research 5(2):266-288 (knapsack 0/1, relaxation continue fractionnaire borneant l’optimum, fondement de la resolution par branch-and-bound) ; Johnson, D.S. (1974), Fast Algorithms for Bin Packing, Journal of Computer and System Sciences 8(3):272-314 (heuristique First-Fit-Decreasing pour le Bin Packing, garantie de performance 11/9OPT) ; Garey, M.R. & Johnson, D.S. (1979), Computers and Intractability, W.H. Freeman (Bin Packing et Knapsack parmi les 21 problemes NP-complets fondateurs) ; 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, generation de colonnes fondatrice) ; Markowitz, H. (1952), Portfolio Sélection, The Journal of Finance 7(1):77-91 (théorie moderne du portefeuille : frontier efficiente moyenne-variance, déjà nomme ci-dessous).*

# Installation des dépendances
import subprocess
import sys

def install_if_missing(package):
    try:
        __import__(package.replace('-', '_'))
    except ImportError:
        subprocess.check_call([sys.executable, "-m", "pip", "install", "-q", package])

install_if_missing('ortools')
install_if_missing('matplotlib')

from ortools.sat.python import cp_model
import matplotlib.pyplot as plt
import numpy as np
from typing import List, Dict, Tuple, Optional

print("Dépendances prêtes.")
Dépendances prêtes.

1. Bin Packing Problem (BPP)

Le BPP consiste à placer des objets de tailles différentes dans le minimum de bins de capacité fixe.

Définition formelle

  • n objets avec tailles \(w_1, w_2, ..., w_n\)
  • Bins de capacité \(C\)
  • Objectif: Minimiser le nombre de bins utilisés

Complexité

NP-hard, avec plusieurs heuristiques classiques: - First Fit (FF): Premier bin avec assez d’espace - Best Fit (BF): Bin laissant le moins d’espace restant - First Fit Decreasing (FFD): FF après tri décroissant

Application : Bin Packing Problem avec Minimisation du Nombre de Bins

Cette section démontre la résolution du problème de Bin Packing (remplissage de conteneurs) où l’on doit placer des objets de tailles différentes dans un nombre minimum de conteneurs de capacité fixe.

Problème à résoudre : - 6 objets de tailles variées : [2, 2, 2, 3, 5, 6] - Bins de capacité : 10 unités chacun - Contrainte : chaque objet doit être placé dans exactement un bin - Objectif : minimiser le nombre de bins utilisés

Modélisation CP-SAT : - Variables binaires x[i,j] : 1 si l’objet i est placé dans le bin j, 0 sinon - Variables binaires y[j] : 1 si le bin j est utilisé, 0 sinon - Contrainte d’assignation : pour chaque objet i, Σ x[i,j] = 1 (exactement un bin) - Contrainte de capacité : pour chaque bin j, Σ taille[i] × x[i,j] ≤ capacité × y[j] - Symmetry breaking : y[j] ≥ y[j+1] (utiliser les bins dans l’ordre pour réduire les symétries) - Objectif : minimiser Σ y[j]

Le code ci-dessous illustre comment CP-SAT trouve la solution optimale en utilisant des variables binaires d’assignation et des techniques avancées de réduction des symétries pour accélérer la résolution.

def solve_bin_packing_cp(items: List[int], capacity: int) -> Dict:
    """
    Résout le Bin Packing Problem avec OR-Tools CP-SAT.
    
    Args:
        items: Liste des tailles des objets
        capacity: Capacité de chaque bin
    
    Returns:
        Dictionnaire avec nombre de bins, assignations et status
    """
    n = len(items)
    
    # Borne supérieure: chaque objet dans son propre bin
    max_bins = n
    
    model = cp_model.CpModel()
    
    # Variables binaires: x[i,j] = 1 si objet i dans bin j
    x = {}
    for i in range(n):
        for j in range(max_bins):
            x[(i, j)] = model.NewBoolVar(f'x_{i}_{j}')
    
    # Variables: y[j] = 1 si bin j est utilisé
    y = {}
    for j in range(max_bins):
        y[j] = model.NewBoolVar(f'y_{j}')
    
    # Contrainte 1: Chaque objet dans exactement un bin
    for i in range(n):
        model.Add(sum(x[(i, j)] for j in range(max_bins)) == 1)
    
    # Contrainte 2: Capacité des bins
    for j in range(max_bins):
        model.Add(sum(items[i] * x[(i, j)] for i in range(n)) <= capacity * y[j])
    
    # Contrainte 3: Symmetry breaking - utiliser bins dans l'ordre
    for j in range(max_bins - 1):
        model.Add(y[j] >= y[j + 1])
    
    # Objectif: minimiser le nombre de bins
    model.Minimize(sum(y[j] for j in range(max_bins)))
    
    # Résolution
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 30
    status = solver.Solve(model)
    
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        bins = {}
        for i in range(n):
            for j in range(max_bins):
                if solver.Value(x[(i, j)]) == 1:
                    if j not in bins:
                        bins[j] = []
                    bins[j].append(i)
        
        return {
            'num_bins': len(bins),
            'bins': bins,
            'bin_loads': {j: sum(items[i] for i in items_list) for j, items_list in bins.items()},
            'status': 'OPTIMAL' if status == cp_model.OPTIMAL else 'FEASIBLE'
        }
    
    return {'num_bins': None, 'bins': {}, 'status': 'INFEASIBLE'}

print("Fonction solve_bin_packing_cp definie.")
Fonction solve_bin_packing_cp definie.

Exemple Bin Packing

Nous allons résoudre un problème de Bin Packing avec : - 6 objets de tailles variées (2 à 6 unités) : [2, 2, 2, 3, 5, 6] - Bins de capacité : 10 unités - Objectif : minimiser le nombre de bins utilisés

Le solveur CP-SAT utilise des variables binaires pour assigner chaque objet à un bin, avec des contraintes de capacité et des techniques de symmetry breaking pour accélérer la résolution.

# Exemple Bin Packing
items = [2, 2, 2, 3, 5, 6]
capacity = 10

bpp_result = solve_bin_packing_cp(items, capacity)
print(f"Nombre optimal de bins: {bpp_result['num_bins']}")
print(f"Status: {bpp_result['status']}")
print(f"\nDétail des bins:")
for bin_id, bin_items in bpp_result['bins'].items():
    print(f"  Bin {bin_id}: objets {[items[i] for i in bin_items]} (charge: {bpp_result['bin_loads'][bin_id]}/{capacity})")
Nombre optimal de bins: 2
Status: OPTIMAL

Détail des bins:
  Bin 1: objets [2, 2, 6] (charge: 10/10)
  Bin 0: objets [2, 3, 5] (charge: 10/10)

Visualisation du Bin Packing

Le diagramme de visualisation montre pour chaque bin : - Barres colorées : objets placés avec leur taille - Espace grisé : capacité restante (gaspillage) - Ligne rouge : capacité maximale du bin

Cette représentation permet de vérifier l’efficacité de la solution et d’identifier les bins sous-utilisés.

def plot_bin_packing(items: List[int], capacity: int, result: Dict):
    """Visualise le résultat du Bin Packing."""
    if result['status'] == 'INFEASIBLE':
        print("Aucune solution à afficher")
        return
    
    fig, ax = plt.subplots(figsize=(10, 4 + 0.3 * result['num_bins']))
    
    colors = plt.cm.Set3(np.linspace(0, 1, len(result['bins'])))
    
    for bin_id, (j, bin_items) in enumerate(result['bins'].items()):
        left = 0
        for i in bin_items:
            ax.barh(bin_id, items[i], left=left, height=0.6, 
                   color=colors[bin_id], edgecolor='black')
            ax.text(left + items[i]/2, bin_id, str(items[i]), 
                   ha='center', va='center', fontsize=9)
            left += items[i]
        
        # Espace restant
        remaining = capacity - result['bin_loads'][j]
        if remaining > 0:
            ax.barh(bin_id, remaining, left=left, height=0.6, 
                   color='lightgray', edgecolor='gray', alpha=0.5)
            ax.text(left + remaining/2, bin_id, f'-{remaining}', 
                   ha='center', va='center', fontsize=8, color='gray')
    
    ax.axvline(x=capacity, color='red', linestyle='--', label=f'Capacité ({capacity})')
    ax.set_xlim(0, capacity + 1)
    ax.set_yticks(range(result['num_bins']))
    ax.set_yticklabels([f'Bin {j}' for j in result['bins'].keys()])
    ax.set_xlabel('Charge')
    ax.set_title(f'Bin Packing Optimal - {result["num_bins"]} bins')
    ax.legend()
    plt.tight_layout()
    plt.show()

plot_bin_packing(items, capacity, bpp_result)

2. Knapsack Problem

Le Knapsack Problem: sélectionner des objets pour maximiser la valeur sans dépasser la capacité.

Variante 0/1

  • Chaque objet est pris 0 ou 1 fois
  • Variables binaires \(x_i \in \{0,1\}\)

Formulation

\[\max \sum_{i=1}^{n} v_i x_i \quad \text{s.t.} \quad \sum_{i=1}^{n} w_i x_i \leq C\]

Application : Knapsack Problem 0/1 avec Maximisation de Valeur

Cette section illustre le problème classique du sac à dos (Knapsack Problem) dans sa variante 0/1, où chaque objet peut être soit pris entièreme nt, soit laissé.

Problème à résoudre : - 8 objets disponibles, chacun avec un poids et une valeur - Capacité du sac : 20 unités de poids - Contrainte 0/1 : chaque objet est soit pris (1), soit laissé (0) - pas de sélection partielle - Objectif : maximiser la valeur totale des objets sélectionnés

Modélisation mathématique :

Variables : x[i] ∈ {0,1} pour i = 1..n
Contrainte : Σ poids[i] × x[i] ≤ capacité
Objectif   : maximiser Σ valeur[i] × x[i]

Techniques CP-SAT utilisées : - Variables BoolVar : une variable binaire par objet (x[i] = 1 si l’objet i est sélectionné) - Contrainte linéaire : somme des poids ≤ capacité - Optimisation : maximisation d’une fonction linéaire

Le code ci-dessous démontre la résolution exacte du Knapsack 0/1 avec CP-SAT, qui garantit de trouver la solution optimale (contrairement aux heuristiques gloutonnes qui peuvent être sous-optimales).

def solve_knapsack_cp(
    weights: List[int], 
    values: List[int], 
    capacity: int
) -> Dict:
    """
    Résout le Knapsack Problem 0/1 avec CP-SAT.
    
    Args:
        weights: Poids des objets
        values: Valeurs des objets
        capacity: Capacité maximale du sac
    
    Returns:
        Dictionnaire avec valeur totale, objets sélectionnés et status
    """
    n = len(weights)
    model = cp_model.CpModel()
    
    # Variables binaires
    x = [model.NewBoolVar(f'x_{i}') for i in range(n)]
    
    # Contrainte de capacité
    model.Add(sum(weights[i] * x[i] for i in range(n)) <= capacity)
    
    # Objectif: maximiser la valeur
    total_value = sum(values[i] * x[i] for i in range(n))
    model.Maximize(total_value)
    
    # Résolution
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        selected = [i for i in range(n) if solver.Value(x[i]) == 1]
        total_weight = sum(weights[i] for i in selected)
        
        return {
            'total_value': solver.Value(total_value),
            'total_weight': total_weight,
            'selected': selected,
            'status': 'OPTIMAL' if status == cp_model.OPTIMAL else 'FEASIBLE'
        }
    
    return {'total_value': 0, 'total_weight': 0, 'selected': [], 'status': 'INFEASIBLE'}

print("Fonction solve_knapsack_cp definie.")
Fonction solve_knapsack_cp definie.

Exemple Knapsack Problem

Nous allons résoudre un problème de sac à dos avec : - 8 objets ayant des poids et valeurs différents - Capacité du sac : 20 unités - Objectif : maximiser la valeur totale sans dépasser la capacité

C’est un problème classique de sélection où chaque objet peut être pris (1) ou laissé (0), d’où le nom “Knapsack 0/1”.

# Exemple Knapsack
weights = [2, 3, 4, 5, 9, 7, 8, 6]
values = [3, 4, 5, 8, 10, 7, 9, 6]
capacity = 20

kp_result = solve_knapsack_cp(weights, values, capacity)
print(f"Valeur maximale: {kp_result['total_value']}")
print(f"Poids total: {kp_result['total_weight']}/{capacity}")
print(f"Objets sélectionnés: {kp_result['selected']}")
print(f"Status: {kp_result['status']}")
Valeur maximale: 26
Poids total: 20/20
Objets sélectionnés: [0, 1, 2, 3, 7]
Status: OPTIMAL

Interpretation : Knapsack Problem 0/1

Sortie obtenue : Le solveur sélectionne 5 objets (indices 0, 1, 2, 3, 7) pour une valeur totale de 26, en utilisant exactement toute la capacité du sac (20/20).

Objet Poids Valeur Ratio v/w Sélectionné
0 2 3 1.50 Oui
1 3 4 1.33 Oui
2 4 5 1.25 Oui
3 5 8 1.60 Oui
4 9 10 1.11 Non
5 7 7 1.00 Non
6 8 9 1.13 Non
7 6 6 1.00 Oui

Analyse de la sélection : - Poids total : 2 + 3 + 4 + 5 + 6 = 20 (capacité utilisée à 100%) - Valeur totale : 3 + 4 + 5 + 8 + 6 = 26 - Ratio moyen : 26/20 = 1.3 (valeur par unité de poids)

Points cles : 1. Capacité saturée : Le sac est rempli à 100% de sa capacité (20/20) 2. Optimalité garantie : CP-SAT garantit que 26 est la valeur maximale possible 3. Stratégie de sélection : Le choix n’est pas dicté par le seul ratio v/w — les objets 4 (1.11) et 6 (1.13) ont un meilleur ratio que l’objet 7 (1.00) retenu, mais ne tiennent pas dans la combinaison qui sature exactement la capacité (2+3+4+5+6=20). Le Knapsack 0/1 maximise la valeur sous contrainte de capacité, pas le ratio 4. Complexité 0/1 : Chaque objet est soit pris entièrement (1), soit laissé (0) - pas de sélection partielle

Note technique : Le Knapsack 0/1 est NP-hard, mais existe une version “fractionnelle” (où on peut prendre des fractions d’objets) qui est résoluble en O(n log n) par un algorithme glouton basé sur le ratio valeur/poids. La version 0/1 nécessite une approche CP/PLNE ou de programmation dynamique.

3. Cutting Stock Problem

Le Cutting Stock Problem est similaire au Bin Packing avec des demandes multiples: - Commandes: plusieurs pièces de chaque longueur - Stocks: barres de longueur fixe - Objectif: minimiser le nombre de barres utilisées

Applications

  • Industrie du bois/métal
  • Industrie du papier
  • Fabrication de vêtements

Application : Cutting Stock Problem avec Patterns de Coupe Optimaux

Cette section applique la programmation par contraintes au problème industriel de découpe de barres (Cutting Stock Problem), où l’on doit découper des pièces de différentes longueurs à partir de barres de stock en minimisant le gaspillage.

Problème à résoudre : - 4 types de pièces demandées : longueurs de 20cm, 25cm, 30cm, 40cm - Demandes : respectivement 5, 3, 4, 2 pièces de chaque type - Barres en stock : longueur standard de 100cm - Objectif : minimiser le nombre de barres utilisées

Modélisation CP-SAT : - Variables entières y[j,i] : nombre de pièces de type i découpées dans la barre j - Variables binaires z[j] : 1 si la barre j est utilisée, 0 sinon - Contrainte de demande : pour chaque type i, somme(y[j,i]) ≥ demande[i] - Contrainte de capacité : pour chaque barre j, somme(longueur[i] × y[j,i]) ≤ stock_length × z[j] - Symmetry breaking : z[j] ≥ z[j+1] (utiliser les barres dans l’ordre) - Objectif : minimiser somme(z[j])

Le code ci-dessous montre comment CP-SAT trouve automatiquement les patterns de coupe optimaux, c’est-à-dire la combinaison de pièces à découper dans chaque barre pour minimiser le nombre total de barres et le gaspillage.

Application du cutting stock a un ensemble de pieces.

def solve_cutting_stock_cp(piece_lengths: List[int], demands: List[int], stock_length: int) -> Dict:
    """
    Resolve le Cutting Stock Problem avec OR-Tools CP-SAT.
    
    Args:
        piece_lengths: Longueurs des pieces demandees
        demands: Nombre de pieces demandees pour chaque longueur
        stock_length: Longueur des barres en stock
    
    Returns:
        Dictionnaire avec nombre de barres, patterns et status
    """
    n_types = len(piece_lengths)
    max_bars = sum(demands)  # Borne superieure
    
    model = cp_model.CpModel()
    
    # Variables: y[j,i] = nombre de pieces de type i coupees dans la barre j
    y = {}
    for j in range(max_bars):
        for i in range(n_types):
            y[(j, i)] = model.NewIntVar(0, demands[i], f"y_{j}_{i}")
    
    # Variables: z[j] = 1 si la barre j est utilisee
    z = {}
    for j in range(max_bars):
        z[j] = model.NewBoolVar(f"z_{j}")
    
    # Contrainte 1: Satisfaction de la demande
    for i in range(n_types):
        model.Add(sum(y[(j, i)] for j in range(max_bars)) >= demands[i])
    
    # Contrainte 2: Capacite par barre
    for j in range(max_bars):
        model.Add(sum(piece_lengths[i] * y[(j, i)] for i in range(n_types)) <= stock_length * z[j])
    
    # Contrainte 3: Symmetry breaking
    for j in range(max_bars - 1):
        model.Add(z[j] >= z[j + 1])
    
    # Objectif: minimiser le nombre de barres
    model.Minimize(sum(z[j] for j in range(max_bars)))
    
    # Resolution
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 30
    status = solver.Solve(model)
    
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        patterns = []
        for j in range(max_bars):
            if solver.Value(z[j]) == 1:
                pattern = {}
                used = 0
                for i in range(n_types):
                    count = solver.Value(y[(j, i)])
                    if count > 0:
                        pattern[i] = count
                        used += piece_lengths[i] * count
                patterns.append({
                    "bar_id": j,
                    "pattern": pattern,
                    "used_length": used,
                    "waste": stock_length - used
                })
        
        return {
            "num_bars": len(patterns),
            "patterns": patterns,
            "status": "OPTIMAL" if status == cp_model.OPTIMAL else "FEASIBLE"
        }
    
    return {"num_bars": None, "patterns": [], "status": "INFEASIBLE"}

print("Fonction solve_cutting_stock_cp definie.")
Fonction solve_cutting_stock_cp definie.

Exemple Cutting Stock

Nous allons résoudre un problème de découpe avec : - 4 longueurs de pièces demandées : 20cm, 25cm, 30cm, 40cm - Demandes : 5, 3, 4, 2 pièces respectivement - Barres en stock : 100cm de longueur

Le solveur doit trouver les patterns de coupe optimaux qui minimisent le nombre de barres utilisées tout en satisfaisant toutes les demandes.

# Exemple Cutting Stock
piece_lengths = [20, 25, 30, 40]  # cm
demands = [5, 3, 4, 2]  # pièces de chaque longueur
stock_length = 100  # cm

csp_result = solve_cutting_stock_cp(piece_lengths, demands, stock_length)
print(f"Nombre de barres: {csp_result['num_bars']}")
print(f"Status: {csp_result['status']}")
print(f"\nPatterns de coupe:")
for p in csp_result['patterns']:
    pieces = [(piece_lengths[i], c) for i, c in p['pattern'].items()]
    print(f"  Barre {p['bar_id']}: {pieces} - utilisé: {p['used_length']}cm, perte: {p['waste']}cm")
Nombre de barres: 4
Status: OPTIMAL

Patterns de coupe:
  Barre 0: [(20, 1), (25, 1), (30, 1)] - utilisé: 75cm, perte: 25cm
  Barre 1: [(30, 2), (40, 1)] - utilisé: 100cm, perte: 0cm
  Barre 2: [(20, 1), (25, 2), (30, 1)] - utilisé: 100cm, perte: 0cm
  Barre 3: [(20, 3), (40, 1)] - utilisé: 100cm, perte: 0cm

Interpretation : Cutting Stock Problem

Sortie obtenue : Le solveur utilise 4 barres de 100cm pour satisfaire toutes les demandes, avec 3 barres utilisées à 100% et 1 barre avec 25cm de perte (gaspillage).

Barre Pattern de coupe Longueur utilisée Perte Efficacité
Barre 0 1×20cm + 1×25cm + 1×30cm 75cm 25cm 75%
Barre 1 2×30cm + 1×40cm 100cm 0cm 100%
Barre 2 1×20cm + 2×25cm + 1×30cm 100cm 0cm 100%
Barre 3 3×20cm + 1×40cm 100cm 0cm 100%

Analyse des patterns : - Barre 1 : 2×30cm + 1×40cm = 100cm (combinaison parfaite) - Barre 2 : 1×20cm + 2×25cm + 1×30cm = 100cm (combinaison parfaite) - Barre 3 : 3×20cm + 1×40cm = 100cm (combinaison parfaite) - Barre 0 : 1×20cm + 1×25cm + 1×30cm = 75cm (25cm de perte)

Points cles : 1. Optimalité : 4 barres est le minimum théorique pour ces demandes (poids total des pièces : 20×5 + 25×3 + 30×4 + 40×2 = 375cm, donc au moins 4 barres de 100cm) 2. Efficacité globale : 375cm utilisés / 400cm disponibles = 93.75% d’efficacité 3. Gaspillage minimal : Seulement 25cm perdus sur 4 barres (6.25%) 4. Patterns diversifiés : Le solveur trouve 3 patterns optimaux différents pour maximiser l’efficacité

Note technique : Le Cutting Stock Problem est une généralisation du Bin Packing où chaque type d’objet peut être demandé en plusieurs exemplaires. Les industries utilisent souvent des techniques de “column generation” pour les grandes instances, car le nombre de patterns possibles croît exponentiellement.

4. Optimisation de portefeuille

Application : Optimisation de Portefeuille avec Contraintes de Cardinalité

Cette section démontre l’application de la programmation par contraintes à un problème de finance : la sélection optimale d’actifs pour un portefeuille d’investissement.

Problème à résoudre : - 5 actifs disponibles (AAPL, GOOGL, MSFT, AMZN, TSLA) avec historique de prix - Budget total de $50,000 à investir - Contraintes de diversification : sélectionner entre 2 et 3 actifs différents - Objectif : maximiser le rendement attendu du portefeuille

Concepts clés implémentés : - Variables binaires de sélection (selected[i]) : 1 si l’actif i est choisi, 0 sinon - Variables entières de quantité (quantity[i]) : nombre d’unités de l’actif i à acheter - Contrainte de budget : somme(prix[i] × quantité[i]) ≤ budget - Contraintes de cardinalité : min_assets ≤ somme(selected[i]) ≤ max_assets - Lien sélection-quantité : quantity[i] ≥ selected[i] (au moins 1 unité si sélectionné) - Fonction objective : maximiser somme(rendement[i] × quantité[i])

Le code ci-dessous illustre comment modéliser ce problème avec CP-SAT, en utilisant des variables mixtes (binaires et entières) et des contraintes de liaison entre sélection et quantité.

def expected_return(prices):
    """Calcule le rendement attendu simple."""
    if len(prices) < 2:
        return 0
    return (prices[-1] - prices[0]) / prices[0]

def solve_portfolio_optimization(
    assets: List[str],
    prices: List[List[float]],
    budget: float,
    max_assets: int,
    min_assets: int = 1,
    max_per_asset: int = 100
) -> Dict:
    """
    Optimise un portefeuille avec contraintes de cardinalite.
    
    Args:
        assets: Noms des actifs
        prices: Historique des prix pour chaque actif
        budget: Budget total
        max_assets: Nombre maximum d'actifs differents
        min_assets: Nombre minimum d'actifs differents
        max_per_asset: Quantite max par actif
    
    Returns:
        Dictionnaire avec portefeuille optimal et metriques
    """
    n = len(assets)
    current_prices = [p[-1] for p in prices]
    returns = [expected_return(p) for p in prices]
    
    model = cp_model.CpModel()
    
    # Variables
    selected = [model.NewBoolVar(f'sel_{i}') for i in range(n)]
    quantity = [model.NewIntVar(0, max_per_asset, f'q_{i}') for i in range(n)]
    
    # Contrainte 1: Budget
    # Note: on utilise des entiers, on multiplie les prix par 100
    scale = 100
    model.Add(
        sum(int(current_prices[i] * scale) * quantity[i] for i in range(n)) 
        <= int(budget * scale)
    )
    
    # Contrainte 2: Cardinalite
    model.Add(sum(selected) >= min_assets)
    model.Add(sum(selected) <= max_assets)
    
    # Contrainte 3: Quantite > 0 seulement si selectionne
    for i in range(n):
        model.Add(quantity[i] <= max_per_asset * selected[i])
        model.Add(quantity[i] >= selected[i])  # Au moins 1 si selectionne
    
    # Objectif: maximiser le rendement attendu
    # Approximation en entiers
    scaled_returns = [int(r * 1000) for r in returns]
    
    # On maximise sum(return_i * q_i)
    portfolio_value = sum(scaled_returns[i] * quantity[i] for i in range(n))
    model.Maximize(portfolio_value)
    
    # Resolution
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 30
    status = solver.Solve(model)
    
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        portfolio = {}
        total_cost = 0
        for i in range(n):
            q = solver.Value(quantity[i])
            if q > 0:
                cost = q * current_prices[i]
                portfolio[assets[i]] = {
                    'quantity': q,
                    'price': current_prices[i],
                    'cost': cost,
                    'expected_return': returns[i]
                }
                total_cost += cost
        
        return {
            'portfolio': portfolio,
            'total_cost': total_cost,
            'num_assets': len(portfolio),
            'status': 'OPTIMAL' if status == cp_model.OPTIMAL else 'FEASIBLE'
        }
    
    return {'portfolio': {}, 'total_cost': 0, 'num_assets': 0, 'status': 'INFEASIBLE'}

print("Fonction solve_portfolio_optimization definie.")
Fonction solve_portfolio_optimization definie.

Optimisation de portefeuille avec rendement et covariance.

Exemple d’optimisation de portefeuille

Nous allons résoudre un problème de sélection de portefeuille avec : - 5 actifs (AAPL, GOOGL, MSFT, AMZN, TSLA) - Budget total de $50,000 - Cardinalité : entre 2 et 3 actifs maximum - Objectif : maximiser le rendement attendu basé sur l’historique des prix

Le solveur CP-SAT doit trouver la combinaison d’actifs qui maximise le rendement tout en respectant les contraintes de budget et de diversification.

# Exemple Portfolio Optimization
assets = ['AAPL', 'GOOGL', 'MSFT', 'AMZN', 'TSLA']
# Prix historiques simulés (simplifiés)
prices = [
    [150, 155, 160, 158, 165],  # AAPL
    [2800, 2850, 2900, 2880, 2950],  # GOOGL
    [300, 310, 315, 320, 325],  # MSFT
    [3200, 3150, 3300, 3400, 3350],  # AMZN
    [900, 950, 880, 920, 1000],  # TSLA
]

budget = 50000

portfolio_result = solve_portfolio_optimization(
    assets, prices, budget,
    max_assets=3,
    min_assets=2
)

print(f"Status: {portfolio_result['status']}")
print(f"Nombre d'actifs: {portfolio_result['num_assets']}")
print(f"Coût total: ${portfolio_result['total_cost']:.2f}")
print(f"\nPortefeuille:")
for asset, info in portfolio_result['portfolio'].items():
    print(f"  {asset}: {info['quantity']} x ${info['price']:.2f} = ${info['cost']:.2f} (rendement: {info['expected_return']*100:.1f}%)")
Status: OPTIMAL
Nombre d'actifs: 3
Coût total: $50000.00

Portefeuille:
  AAPL: 100 x $165.00 = $16500.00 (rendement: 10.0%)
  MSFT: 100 x $325.00 = $32500.00 (rendement: 8.3%)
  TSLA: 1 x $1000.00 = $1000.00 (rendement: 11.1%)

Interpretation : Optimisation de Portefeuille

Sortie obtenue : Le solveur sélectionne 3 actifs (AAPL, MSFT, TSLA) pour un coût total de $50,000, maximisant le rendement attendu tout en respectant les contraintes de cardinalité (2-3 actifs).

Actif Quantité Coût Rendement Contribution
AAPL 100 $16,500 10.0% 33% du budget
MSFT 100 $32,500 8.3% 65% du budget
TSLA 1 $1,000 11.1% 2% du budget

Points cles : 1. Maximisation du rendement : TSLA (11.1%) et AAPL (10.0%) sont favorisés pour leur rendement élevé 2. Contrainte de cardinalité : Exactement 3 actifs sélectionnés (maximum autorisé) 3. Allocation du budget : Utilisation complète du budget ($50,000/$50,000) 4. Sélection gloutonne : GOOGL et AMZN ne sont pas sélectionnés malgré leur présence, car leur rendement est moins favorable

Note technique : Ce modèle simplifié utilise le rendement historique simple ((prix_final - prix_initial) / prix_initial). En pratique, on utiliserait la moyenne des rendements, la variance (risque), et les corrélations entre actifs pour une optimisation plus robuste (théorie moderne du portefeuille de Markowitz).

5. Comparaison des méthodes

Problème Variables Contraintes Complexité
Bin Packing BoolVar + IntVar Capacité, Symétrie NP-hard
Knapsack BoolVar Capacité NP-hard (pseudo-poly)
Cutting Stock IntVar Demande, Capacité NP-hard
Portfolio BoolVar + IntVar Budget, Cardinalité NP-hard

Heuristiques vs Optimal

  1. Bin Packing: FFD souvent à 11% de l’optimal
  2. Knapsack: Greedy par ratio valeur/poids, bon pour grandes instances
  3. Cutting Stock: Column Generation pour grandes instances
  4. Portfolio: Mean-variance avec relaxation continue
# Benchmark: Heuristique First Fit Decreasing pour Bin Packing
def bin_packing_ffd(items: List[int], capacity: int) -> Dict:
    """
    Heuristique First Fit Decreasing pour Bin Packing.
    """
    sorted_items = sorted(enumerate(items), key=lambda x: -x[1])
    bins = []  # Liste des charges actuelles
    assignments = {}  # item_id -> bin_id
    
    for item_id, size in sorted_items:
        placed = False
        for bin_id, load in enumerate(bins):
            if load + size <= capacity:
                bins[bin_id] += size
                assignments[item_id] = bin_id
                placed = True
                break
        
        if not placed:
            bins.append(size)
            assignments[item_id] = len(bins) - 1
    
    return {
        'num_bins': len(bins),
        'bins': bins,
        'assignments': assignments,
        'status': 'HEURISTIC'
    }

# Comparaison — instance de la section 1 (items [2,2,2,3,5,6], capacité 10)
# La variable globale capacity peut avoir été écrasée par une section ultérieure
# (Knapsack: capacity = 20) — utiliser une variable locale pour FFD afin que la
# comparaison CP-SAT vs FFD porte BIEN sur la même instance.
capacity_local = 10  # capacité de la section 1 Bin Packing
ffd_result = bin_packing_ffd(items, capacity_local)
print(f"CP-SAT optimal: {bpp_result['num_bins']} bins")
print(f"FFD heuristic:  {ffd_result['num_bins']} bins")
if bpp_result['num_bins']:
    gap = (ffd_result['num_bins'] - bpp_result['num_bins']) / bpp_result['num_bins'] * 100
    print(f"Gap: {gap:.1f}%")
CP-SAT optimal: 2 bins
FFD heuristic:  3 bins
Gap: 50.0%

Interpretation : Comparaison CP-SAT vs Heuristique FFD

Sortie obtenue : sur cette instance (objets [2, 2, 2, 3, 5, 6], capacité 10), l’heuristique First Fit Decreasing (FFD) utilise 3 bins alors que CP-SAT prouve l’optimal à 2 bins — un gap de 50 %. C’est précisément le cas où une heuristique gloutonne échoue et où le solveur exact justifie son coût.

Aspect Valeur CP-SAT Valeur FFD Analyse
Nombre de bins 2 3 FFD dépasse l’optimal sur cette instance
Statut OPTIMAL HEURISTIC CP-SAT garantit l’optimalité
Gap - 50.0 % FFD utilise 50 % plus de bins que l’optimal

Pourquoi FFD échoue-t-elle ici ? FFD trie les objets par taille décroissante [6, 5, 3, 2, 2, 2] puis place chaque objet dans le premier bin où il tient : - 6 → Bin 0 (charge 6), 5 → Bin 1 (6+5 > 10), 3 → Bin 0 (charge 9), puis les trois 2 remplissent Bin 1 (5+2+2 = 9) et le dernier 2 doit ouvrir un Bin 2. - FFD gaspille le 3 en le plaçant avec le 6 (charge 9, perte 1) au lieu de le réserver à un bin [5, 3, 2]. L’optimal [6, 2, 2] + [5, 3, 2] remplit parfaitement deux bins (charge 10 chacun), sans aucune perte.

Points clés : 1. Une heuristique ne bat jamais l’optimal : par définition, l’optimum est le nombre minimal de bins. FFD ne peut donc qu’égaler ce minimum (gap 0 %) ou l’excéder (gap > 0 %), jamais faire mieux — ici 50 %. 2. Garantie d’optimalité : CP-SAT prouve que 2 bins est l’optimal (status OPTIMAL) ; FFD s’arrête à 3 sans pouvoir certifier qu’il n’en existe pas moins. 3. Borne théorique : FFD garantit au pire 11/9 × OPT + 1 bins. Avec OPT = 2, cela donne environ 3,4 → au plus 4 bins ; FFD obtient ici 3, conforme à sa garantie mais au-dessus de l’optimal. Cette instance illustre que la borne 11/9 n’est pas qu’un résultat théorique : l’écart se matérialise sur des cas concrets. 4. Quand le solveur exact s’impose : c’est sur ce type d’instance défavorable que CP-SAT apporte sa valeur — il prouve l’optimal (2) là où l’heuristique gloutonne échoue (3). En production, FFD donne une solution rapide non certifiée ; CP-SAT certifie le vrai minimum, au prix d’un temps de calcul supérieur.

Note technique : FFD reste excellente en pratique (souvent à l’optimal ou très proche), mais sa nature gloutonne la rend vulnérable aux instances où un choix localement optimal (3 → Bin 0) empêche le packing globalement optimal. CP-SAT explore l’espace complet et trouve le vrai minimum.

Benchmark de passage a l’echelle : ou la garantie d’optimalite a un cout

La comparaison ci-dessus (n=6, gap 50 %) montre CP-SAT battre FFD sur une instance soigneusement choisie. Mais cette instance est-elle representative ? Et que se passe-t-il quand la taille du probleme augmente ? Mesurons FFD vs CP-SAT sur l’instance du notebook plus des instances aleatoires croissantes (tailles d’objets uniformes dans [10, capacity/2], graine fixee pour la reproductibilite), en chronometrant les deux methodes.

# Benchmark de passage a l'echelle : FFD vs CP-SAT (solve_bin_packing_cp, bin_packing_ffd definis plus haut)
import time
import random

def _scaling_instance(n, seed=42, capacity=100):
    random.seed(seed)
    return [random.randint(10, capacity // 2) for _ in range(n)]

# L'instance adverse du notebook (gap 50 %) + instances reproductibles croissantes
scaling = [(6, [2, 2, 2, 3, 5, 6], 10)]
for _n in [20, 50, 100]:
    scaling.append((_n, _scaling_instance(_n), 100))

print("Scaling : ou la garantie d'optimalite de CP-SAT devient couteuse")
print(f"{'n':>5} {'FFD':>5} {'CP-SAT':>7} {'gap%':>6} {'t(FFD)':>9} {'t(CP-SAT)':>11} {'status':>10}")
print("-" * 60)
for n, items, cap in scaling:
    t0 = time.time()
    f = bin_packing_ffd(items, cap)["num_bins"]
    t_ffd = time.time() - t0
    t0 = time.time()
    r = solve_bin_packing_cp(items, cap)
    t_cp = time.time() - t0
    c = r["num_bins"]
    gap = (f - c) / c * 100 if c else 0.0
    print(f"{n:>5} {f:>5} {c:>7} {gap:>5.1f}% {t_ffd:>7.3f}s {t_cp:>9.2f}s {r['status']:>10}")
Scaling : ou la garantie d'optimalite de CP-SAT devient couteuse
    n   FFD  CP-SAT   gap%    t(FFD)   t(CP-SAT)     status
------------------------------------------------------------
    6     3       2  50.0%   0.000s      0.01s    OPTIMAL
   20     6       6   0.0%   0.000s      0.04s    OPTIMAL
   50    15      14   7.1%   0.000s      0.48s    OPTIMAL
  100    30      30   0.0%   0.000s     30.41s   FEASIBLE

Interpretation : FFD quasi-optimale en pratique, garantie CP-SAT limitee par la taille

Resultat mesure :

  • L’instance du notebook (n=6, gap 50 %) est adversariale : c’est un cas soigneusement choisi pour illustrer l’echec de FFD. Sur des instances aleatoires, FFD est quasi-optimale : gap de 0 % a n=20 et n=100, 7 % a n=50. Une heuristique gloutonne bien concue echoue rarement aussi severement que le suggere l’exemple isole.
  • Le cout de CP-SAT croit avec la taille : de quelques dizaines de millisecondes (n=6) a une demi-seconde (n=50), jusqu’a atteindre la limite du budget temps a n=100 (ordres de grandeur ; mesures exactes : cf la sortie du benchmark ci-dessus). A n=100, CP-SAT retourne le statut FEASIBLE, pas OPTIMAL : il a trouve une bonne solution mais ne peut plus prouver l’optimalite dans le temps imparti. La certification – l’avantage distinctif du solveur exact – disparait donc sur les grandes instances.

Compromis pratique : FFD offre une solution quasi-optimale en temps constant, insensible a la taille (sub-milliseconde : cf mesure ci-dessus) ; CP-SAT certifie l’optimalite seulement quand l’instance est assez petite pour le prouver dans le budget temps. Sur une grande instance, CP-SAT se transforme en une heuristique couteuse (cf la mesure a n=100) sans garantie – souvent moins utile que FFD qui a deja donne une quasi-optimale instantanement. La regle empirique : utiliser le solveur exact pour certifier l’optimal sur des instances de taille moyenne (ici n = 50 se prouve en une fraction de seconde), et s’en remettre a FFD (ou a un CP-SAT avec limite de temps courte comme solution approximee) des que la taille explose.

Note (mandat #9377/#9434) : les durees wall-clock de cette interpretation (anciennement epinglees : 20 ms, 0,5 s, 30 s, < 1 ms) sont machine-dependantes par construction (charge CPU du runner, version OR-Tools) et ont ete drainees. Le rapport d’ordres de grandeur (cout CP-SAT croissant avec la taille, perte de certification OPTIMAL -> FEASIBLE a n=100, FFD sub-milliseconde insensible a la taille) est reproductible d’une execution a l’autre (instances seedes, seed = 42) et conserve. Les mesures exactes restent visibles dans la sortie du benchmark de la cellule ci-dessus. Les resultats algorithmiques (gaps 50 % / 0 % / 7 %, statuts OPTIMAL / FEASIBLE) sont deterministes et conserves.

6. Dominance Breaking

Dominance Breaking est une technique d’optimisation qui elimine les solutions dominees avant même de les explorer. Une solution \(s_1\) domine \(s_2\) si :

  1. \(s_1\) est au moins aussi bonne que \(s_2\) sur tous les critères
  2. \(s_1\) est strictement meilleure sur au moins un critere

En eliminant les solutions dominees, on reduit l’espace de recherche sans perdre la solution optimale.

Definition de la dominance

Definition : Une solution \(s_1\) domine \(s_2\) si : 1. \(s_1\) est au moins aussi bonne que \(s_2\) sur tous les objectifs 2. \(s_1\) est strictement meilleure sur au moins un objectif

Dans ce cas, explorer \(s_2\) est inutile car \(s_1\) sera toujours preferee.

# Implementation du Dominance Breaking
from typing import List, Tuple
import numpy as np

class DominanceAnalyzer:
    """
    Analyse et detection des relations de dominance dans les solutions.
    Utile pour post-traitement ou pour guider la recherche.
    """
    
    def __init__(self, num_objectives: int = 1):
        self.num_objectives = num_objectives
        self.solutions: List[Tuple] = []  # (values, solution_data)
    
    def add_solution(self, objective_values: List[float], solution_data: any):
        """Ajoute une solution candidate."""
        self.solutions.append((objective_values, solution_data))
    
    def check_dominance(self, sol1_idx: int, sol2_idx: int) -> bool:
        """
        Verifie si sol1 domine sol2.
        
        Pour un probleme de minimisation :
        - sol1 domine sol2 si sol1[i] <= sol2[i] pour tout i
        - et sol1[j] < sol2[j] pour au moins un j
        """
        obj1, _ = self.solutions[sol1_idx]
        obj2, _ = self.solutions[sol2_idx]
        
        # Verifier la dominance Pareto
        at_least_one_better = False
        all_at_least_equal = True
        
        for i in range(len(obj1)):
            if obj1[i] > obj2[i]:  # Minimisation
                all_at_least_equal = False
                break
            if obj1[i] < obj2[i]:
                at_least_one_better = True
        
        return all_at_least_equal and at_least_one_better
    
    def find_pareto_front(self) -> List[int]:
        """Trouve les indices des solutions non-dominees (front de Pareto)."""
        pareto_indices = []
        
        for i in range(len(self.solutions)):
            dominated = False
            for j in range(len(self.solutions)):
                if i != j and self.check_dominance(j, i):
                    dominated = True
                    break
            if not dominated:
                pareto_indices.append(i)
        
        return pareto_indices


# Exemple : Dominance dans le Bin Packing
print("=== Dominance Breaking dans le Bin Packing ===\n")

# Simulons plusieurs solutions pour un probleme de bin packing
analyzer = DominanceAnalyzer(num_objectives=2)  # Objectifs: nombre de bins, gaspillage max

solutions = [
    ([3, 2.5], "Solution A: 3 bins, gaspillage 2.5"),  # 3 bins, some waste
    ([3, 1.0], "Solution B: 3 bins, gaspillage 1.0"),  # 3 bins, less waste - DOMINE A
    ([4, 0.0], "Solution C: 4 bins, gaspillage 0.0"),  # 4 bins, no waste - DOMINEE par B
    ([2, 5.0], "Solution D: 2 bins, gaspillage 5.0"),  # 2 bins, much waste - peut-etre optimal
]

for obj_vals, desc in solutions:
    analyzer.add_solution(obj_vals, desc)

print("Solutions candidates:")
for i, (obj_vals, desc) in enumerate(solutions):
    print(f"  {i}: {desc} - Objectifs: {obj_vals}")

pareto_front = analyzer.find_pareto_front()
print(f"\nFront de Pareto (solutions non-dominees):")
for idx in pareto_front:
    obj_vals, desc = solutions[idx]
    print(f"  {idx}: {desc}")
=== Dominance Breaking dans le Bin Packing ===

Solutions candidates:
  0: Solution A: 3 bins, gaspillage 2.5 - Objectifs: [3, 2.5]
  1: Solution B: 3 bins, gaspillage 1.0 - Objectifs: [3, 1.0]
  2: Solution C: 4 bins, gaspillage 0.0 - Objectifs: [4, 0.0]
  3: Solution D: 2 bins, gaspillage 5.0 - Objectifs: [2, 5.0]

Front de Pareto (solutions non-dominees):
  1: Solution B: 3 bins, gaspillage 1.0
  2: Solution C: 4 bins, gaspillage 0.0
  3: Solution D: 2 bins, gaspillage 5.0

Interpretation : Dominance Breaking

Pourquoi le dominance breaking est important ?

  1. Reduction de l’espace de recherche : Elimine les branches de l’arbre de recherche qui menent a des solutions dominees.

  2. Acceleration de la convergence : Le solveur se concentre sur les solutions potentiellement optimales.

  3. Multi-objectif : Particulierement utile en optimisation multi-objectif ou le front de Pareto peut etre grand.

Implementation pratique :

  • OR-Tools CP-SAT integre automatiquement certaines formes de dominance breaking.
  • Pour des problemes spécifiques, des contraintes de dominance peuvent etre ajoutees manuellement.
  • Combine avec le cassage de symetries pour un effet maximal.

Attention : Le dominance breaking doit etre prouve correct. Une dominance incorrecte peut eliminer des solutions optimales !

7. Exemple guide

Exemple guide 1: Multi-Knapsack

Généralisez le Knapsack à plusieurs sacs avec capacités différentes.

Exemple guide 2: Bin Packing avec contraintes de conflit

Certains objets ne peuvent pas être dans le même bin. Ajoutez cette contrainte.

Exemple guide 3: Portfolio avec contraintes de risque

Ajoutez une contrainte de variance maximale du portefeuille.

Exemple guide 4: Cutting Stock avec chutes réutilisables

Les chutes de longueur > seuil peuvent être réutilisées comme nouvelles barres.

# Exemple resolu : Multi-Knapsack (plusieurs sacs)

def solve_multi_knapsack(weights: List[int],
                        values: List[int],
                        capacities: List[int]) -> Dict:
    """Multi-Knapsack : chaque objet va dans au plus un sac.

    Variables : x[i, k] = 1 ssi l'objet i est place dans le sac k.
    Contraintes :
      - sum_k x[i, k] <= 1  (chaque objet dans au plus un sac)
      - sum_i w_i * x[i, k] <= C_k  (capacite de chaque sac)
    Objectif : maximiser la valeur totale des objets places.
    """
    n = len(weights)
    K = len(capacities)
    assert len(values) == n, "values et weights de meme taille"

    model = cp_model.CpModel()
    x = {(i, k): model.NewBoolVar(f"x_{i}_{k}")
         for i in range(n) for k in range(K)}

    for i in range(n):
        model.Add(sum(x[i, k] for k in range(K)) <= 1)

    for k in range(K):
        model.Add(sum(weights[i] * x[i, k] for i in range(n)) <= capacities[k])

    model.Maximize(sum(values[i] * x[i, k] for i in range(n) for k in range(K)))

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 30
    status = solver.Solve(model)

    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        bags = {k: [] for k in range(K)}
        loads = {k: 0 for k in range(K)}
        for i in range(n):
            for k in range(K):
                if solver.Value(x[i, k]) == 1:
                    bags[k].append(i)
                    loads[k] += weights[i]
        return {
            "total_value": int(solver.ObjectiveValue()),
            "bags": bags,
            "loads": loads,
            "capacities": capacities,
            "status": "OPTIMAL" if status == cp_model.OPTIMAL else "FEASIBLE",
        }
    return {"total_value": 0, "bags": {}, "status": "INFEASIBLE"}


# Test avec 8 objets et 2 sacs de capacites differentes
result_mk = solve_multi_knapsack(weights, values, capacities=[10, 15])
print(f"Status      : {result_mk['status']}")
print(f"Valeur tot  : {result_mk['total_value']}")
for k, items_in_bag in result_mk["bags"].items():
    load = result_mk["loads"][k]; cap = result_mk["capacities"][k]
    val = sum(values[i] for i in items_in_bag)
    print(f"  Sac {k} ({load}/{cap}) : objets {items_in_bag}  valeur = {val}")
Status      : OPTIMAL
Valeur tot  : 31
  Sac 0 (10/10) : objets [0, 6]  valeur = 12
  Sac 1 (15/15) : objets [2, 3, 7]  valeur = 19

Exercice 1b : Multi-Knapsack avec 3 sacs

Enonce : Resolvez un problème de Multi-Knapsack avec 12 objets et 3 sacs de capacites [12, 18, 10].

Données : - Poids : [3, 6, 2, 4, 8, 5, 7, 1, 9, 3, 4, 6] - Valeurs: [5, 9, 3, 7, 12, 8, 10, 2, 14, 4, 6, 11] - Capacites des 3 sacs : [12, 18, 10]

Consignes : 1. Utilisez solve_multi_knapsack définie dans l’exemple ci-dessus 2. Affichez le contenu de chaque sac, sa charge et sa valeur 3. Verifiez qu’aucun objet n’est place dans plus d’un sac

# Exercice 1b : Multi-Knapsack avec 3 sacs

# Exercice: definissez les nouvelles donnees (12 objets, 3 sacs)
new_weights = [3, 6, 2, 4, 8, 5, 7, 1, 9, 3, 4, 6]
new_values  = [5, 9, 3, 7, 12, 8, 10, 2, 14, 4, 6, 11]
new_caps    = [12, 18, 10]

# Exercice: appelez solve_multi_knapsack et affichez les resultats
# Indice : utilisez la meme fonction que dans l'exemple

# Votre code ici
print("Exercice a completer")
Exercice a completer

Exemple guide 2 : Bin Packing avec contraintes de conflit

Certaines paires d’objets ne peuvent pas cohabiter dans le même bin (produits chimiques incompatibles, allergies alimentaires, etc.). On ajoute une contrainte x[i, j] + x[k, j] <= 1 pour chaque paire en conflit.

# Exemple resolu : Bin Packing avec conflits

def solve_bin_packing_conflicts(items: List[int],
                                 capacity: int,
                                 conflicts: List[Tuple[int, int]]) -> Dict:
    """Bin Packing avec paires d'objets interdites dans le meme bin."""
    n = len(items)
    max_bins = n
    model = cp_model.CpModel()

    x = {(i, j): model.NewBoolVar(f"x_{i}_{j}")
         for i in range(n) for j in range(max_bins)}
    y = [model.NewBoolVar(f"y_{j}") for j in range(max_bins)]

    for i in range(n):
        model.Add(sum(x[i, j] for j in range(max_bins)) == 1)

    for j in range(max_bins):
        model.Add(sum(items[i] * x[i, j] for i in range(n)) <= capacity * y[j])

    # Symmetry breaking : bins utilises dans l'ordre
    for j in range(max_bins - 1):
        model.Add(y[j] >= y[j + 1])

    # Contraintes de conflit
    for (a, b) in conflicts:
        for j in range(max_bins):
            model.Add(x[a, j] + x[b, j] <= 1)

    model.Minimize(sum(y))

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 30
    status = solver.Solve(model)

    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        bins = {}
        for i in range(n):
            for j in range(max_bins):
                if solver.Value(x[i, j]) == 1:
                    bins.setdefault(j, []).append(i)
        return {
            "num_bins": int(solver.ObjectiveValue()),
            "bins": bins,
            "bin_loads": {j: sum(items[i] for i in it) for j, it in bins.items()},
            "status": "OPTIMAL" if status == cp_model.OPTIMAL else "FEASIBLE",
        }
    return {"num_bins": None, "bins": {}, "status": "INFEASIBLE"}


# Avec conflits : (0, 2), (3, 7) ne peuvent pas etre ensemble
conflicts = [(0, 2), (3, 7), (1, 4)]
res_base  = solve_bin_packing_cp(items, capacity)
res_conf  = solve_bin_packing_conflicts(items, capacity, conflicts)
print(f"Bin packing sans conflits : {res_base['num_bins']} bins")
print(f"Bin packing avec conflits : {res_conf['num_bins']} bins (conflits={conflicts})")
for bid, it in res_conf["bins"].items():
    print(f"  Bin {bid} ({res_conf['bin_loads'][bid]}/{capacity}) : objets {it} tailles {[items[i] for i in it]}")

# Verification qu'aucun conflit n'est viole
for (a, b) in conflicts:
    same = [bid for bid, it in res_conf["bins"].items() if a in it and b in it]
    assert not same, f"Conflit ({a}, {b}) viole dans les bins {same}"
print("Tous les conflits sont respectes.")
Bin packing sans conflits : None bins
Bin packing avec conflits : None bins (conflits=[(0, 2), (3, 7), (1, 4)])
Tous les conflits sont respectes.

Exercice 2b : Bin Packing avec conflits etendus

Enonce : Resolvez un Bin Packing avec 12 objets et des conflits plus nombreux.

Données : - Tailles : [5, 3, 7, 2, 8, 4, 6, 1, 9, 3, 5, 2] - Capacite des bins : 15 - Conflits : [(0, 3), (1, 6), (2, 5), (4, 8), (7, 10), (0, 9)]

Consignes : 1. Utilisez solve_bin_packing_conflicts définie dans l’exemple ci-dessus 2. Comparez le nombre de bins avec et sans conflits 3. Verifiez qu’aucune paire en conflit ne partage le même bin

# Exercice 2b : Bin Packing avec conflits etendus

# Exercice: definissez les nouvelles donnees
new_items    = [5, 3, 7, 2, 8, 4, 6, 1, 9, 3, 5, 2]
new_capacity = 15
new_conflicts = [(0, 3), (1, 6), (2, 5), (4, 8), (7, 10), (0, 9)]

# Exercice: resolvez avec solve_bin_packing_conflicts
# Exercice: comparez avec solve_bin_packing_cp (sans conflits)
# Indice : les conflits forcent souvent un bin supplementaire

# Votre code ici
print("Exercice a completer")
Exercice a completer

Exemple guide 3 : Portfolio avec contrainte de risque (variance bornee)

On ajoute une borne superieure sur la variance du portefeuille. La variance quadratique n’est pas lineaire ; on la lineariseau par la somme des variances individuelles ponderees (diagonale de la matrice de covariance), ce qui est une approximation couramment utilisee pour un premier modèle.

# Exemple resolu : Portfolio avec contrainte de risque

def solve_portfolio_with_risk(
    assets: List[str],
    prices: List[List[float]],
    budget: float,
    max_assets: int,
    min_assets: int,
    max_per_asset: int,
    max_variance_per_euro: float,
) -> Dict:
    """Portefeuille avec contrainte de risque.

    Approximation : la variance du portefeuille est approximee par
        sum_i q_i * var(actif_i)
    (diagonale de la matrice de covariance). On borne cette somme par
    max_variance_per_euro * cout_total.
    """
    n = len(assets)
    current_prices = [p[-1] for p in prices]
    returns = [expected_return(p) for p in prices]
    variances = [float(np.var(p)) for p in prices]

    scale = 100
    scaled_prices   = [int(p * scale) for p in current_prices]
    scaled_returns  = [int(r * 1000) for r in returns]
    scaled_var      = [int(v * scale) for v in variances]
    scaled_var_limit = int(max_variance_per_euro * scale * scale)

    model = cp_model.CpModel()
    sel = [model.NewBoolVar(f"s_{i}") for i in range(n)]
    q   = [model.NewIntVar(0, max_per_asset, f"q_{i}") for i in range(n)]

    total_cost = sum(scaled_prices[i] * q[i] for i in range(n))
    model.Add(total_cost <= int(budget * scale))

    model.Add(sum(sel) >= min_assets)
    model.Add(sum(sel) <= max_assets)
    for i in range(n):
        model.Add(q[i] <= max_per_asset * sel[i])
        model.Add(q[i] >= sel[i])

    # Contrainte de variance : sum_i var_i * q_i <= max_var_per_euro * cout
    # (var_i * q_i approxime la variance associee a la position i)
    lhs = sum(scaled_var[i] * q[i] for i in range(n))
    model.Add(lhs * scale <= scaled_var_limit * total_cost)

    model.Maximize(sum(scaled_returns[i] * q[i] for i in range(n)))

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 30
    status = solver.Solve(model)
    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        portfolio = {}; cost = 0.0; variance = 0.0
        for i in range(n):
            qv = solver.Value(q[i])
            if qv > 0:
                c = qv * current_prices[i]
                portfolio[assets[i]] = {"quantity": qv, "price": current_prices[i],
                                         "cost": c, "expected_return": returns[i],
                                         "variance": variances[i]}
                cost += c
                variance += variances[i] * qv
        return {"portfolio": portfolio, "total_cost": cost,
                "estimated_variance_per_euro": variance / cost if cost else 0,
                "status": "OPTIMAL" if status == cp_model.OPTIMAL else "FEASIBLE"}
    return {"portfolio": {}, "status": "INFEASIBLE"}


res = solve_portfolio_with_risk(
    assets, prices, budget=50000,
    max_assets=3, min_assets=2, max_per_asset=100,
    max_variance_per_euro=10.0,
)
print(f"Status : {res['status']}")
if res["status"] != "INFEASIBLE":
    print(f"Cout total : ${res['total_cost']:.2f}")
    print(f"Variance estimee par euro : {res['estimated_variance_per_euro']:.3f}")
    for a, info in res["portfolio"].items():
        print(f"  {a}: {info['quantity']} x ${info['price']:.2f} "
              f"(var = {info['variance']:.1f}, rendement = {info['expected_return']*100:.1f}%)")
Status : OPTIMAL
Cout total : $50000.00
Variance estimee par euro : 0.233
  AAPL: 100 x $165.00 (var = 25.0, rendement = 10.0%)
  MSFT: 100 x $325.00 (var = 74.0, rendement = 8.3%)
  TSLA: 1 x $1000.00 (var = 1760.0, rendement = 11.1%)

Exercice 3b : Portefeuille conservative

Enonce : Construisez un portefeuille conservatif avec une contrainte de variance plus stricte (max_variance_per_euro = 3.0 au lieu de 10.0).

Données :

assets = ['AAPL', 'GOOGL', 'MSFT', 'AMZN', 'TSLA', 'NVDA']
prices = [
    [150, 155, 160, 158, 165],   # AAPL
    [2800, 2850, 2900, 2880, 2950],  # GOOGL
    [300, 310, 315, 320, 325],   # MSFT
    [3200, 3150, 3300, 3400, 3350],  # AMZN
    [900, 950, 880, 920, 1000],   # TSLA
    [450, 480, 510, 490, 520],    # NVDA
]
budget = 60000

Consignes : 1. Utilisez solve_portfolio_with_risk définie dans l’exemple ci-dessus 2. Selectionnez entre 2 et 4 actifs avec une variance max par euro de 3.0 3. Comparez le rendement avec le portefeuille moins contraint de l’exemple

# Exercice 3b : Portefeuille conservative

# Exercice: definissez les 6 actifs avec leurs historiques de prix
assets_conservative = ['AAPL', 'GOOGL', 'MSFT', 'AMZN', 'TSLA', 'NVDA']
prices_conservative = [
    [150, 155, 160, 158, 165],
    [2800, 2850, 2900, 2880, 2950],
    [300, 310, 315, 320, 325],
    [3200, 3150, 3300, 3400, 3350],
    [900, 950, 880, 920, 1000],
    [450, 480, 510, 490, 520],
]

# Exercice: appelez solve_portfolio_with_risk avec max_variance_per_euro=3.0
# Indice : avec 6 actifs au lieu de 5, vous avez plus de choix

# Votre code ici
print("Exercice a completer")
Exercice a completer

Exemple guide 4 : Cutting Stock avec chutes reutilisables

Les chutes de longueur superieure a un seuil reuse_threshold peuvent etre considerees comme de nouvelles barres. On modelise ceci en creant une deuxieme catégorie de barres de longueur dynamique (capturee par une variable bornee par l’ensemble des longueurs de chutes possibles) ; une approche plus simple suffit ici : on accepte deux longueurs de stock et on force les barres du deuxieme type a provenir d’une chute (via un petit cout d’usage différent).

# Exemple resolu : Cutting Stock avec chutes reutilisables
#
# Idee : on utilise deux "niveaux" de barres :
#   - niveau 0 : barres neuves de longueur stock_length
#   - niveau 1 : barres issues des chutes (longueur <= stock_length - reuse_threshold
#     pour modeliser le fait qu'une chute courte ne merite pas d'etre gardee)
# On minimise le nombre de barres neuves, puis le gaspillage total en second critere.

def solve_cutting_stock_reuse(piece_lengths: List[int],
                              demands: List[int],
                              stock_length: int,
                              reuse_threshold: int) -> Dict:
    """Cutting Stock ou chaque barre neuve peut ceder sa chute comme nouvelle barre.

    Modele : chaque barre neuve j peut creer au plus 1 barre "chute" j', dont
    la longueur est l'espace restant de j s'il depasse reuse_threshold, 0 sinon.
    """
    n_types = len(piece_lengths)
    max_bars = sum(demands)
    model = cp_model.CpModel()

    # y[b, i] : nombre de pieces de type i coupees dans la barre (neuve) b
    y = {(b, i): model.NewIntVar(0, demands[i], f"y_{b}_{i}")
         for b in range(max_bars) for i in range(n_types)}
    # yc[b, i] : nombre de pieces de type i coupees dans la chute de la barre b
    yc = {(b, i): model.NewIntVar(0, demands[i], f"yc_{b}_{i}")
          for b in range(max_bars) for i in range(n_types)}
    z  = [model.NewBoolVar(f"z_{b}") for b in range(max_bars)]       # barre neuve utilisee ?
    zc = [model.NewBoolVar(f"zc_{b}") for b in range(max_bars)]       # chute reutilisee ?

    # Demande : total des coupes (barre + chute) >= demande
    for i in range(n_types):
        model.Add(sum(y[b, i] + yc[b, i] for b in range(max_bars)) >= demands[i])

    # Capacite : longueur utilisee par la barre neuve <= stock_length * z[b]
    for b in range(max_bars):
        used  = sum(piece_lengths[i] * y[b, i]  for i in range(n_types))
        usedc = sum(piece_lengths[i] * yc[b, i] for i in range(n_types))
        model.Add(used + usedc <= stock_length * z[b])
        # Une chute ne peut etre reutilisee que si la barre neuve est utilisee
        model.Add(zc[b] <= z[b])
        # Une chute reutilisee doit contenir au moins une piece (sinon zc reste 0)
        model.Add(usedc <= stock_length * zc[b])
        # Interdire l'utilisation d'une chute si la longueur restante < reuse_threshold
        # (chute nette = stock_length - used), donc usedc <= stock_length - used ;
        # on veut que la chute soit "significative" : si usedc > 0, on veut reuse.
        model.Add(usedc >= zc[b])  # au moins 1 (ou 0 si zc = 0)

    # Symmetry breaking : ordre des barres neuves
    for b in range(max_bars - 1):
        model.Add(z[b] >= z[b + 1])

    # Objectif : minimiser le nombre de barres neuves. Bonus : penaliser les chutes reutilisees
    # avec un poids plus faible (ce sont des barres gratuites si elles permettent d'economiser).
    model.Minimize(sum(z) * 1000 - sum(zc))

    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 30
    status = solver.Solve(model)

    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        patterns = []
        for b in range(max_bars):
            if solver.Value(z[b]) == 1:
                main = {i: solver.Value(y[b, i]) for i in range(n_types)
                        if solver.Value(y[b, i]) > 0}
                chute = {i: solver.Value(yc[b, i]) for i in range(n_types)
                         if solver.Value(yc[b, i]) > 0}
                used_main  = sum(piece_lengths[i] * c for i, c in main.items())
                used_chute = sum(piece_lengths[i] * c for i, c in chute.items())
                patterns.append({
                    "bar_id": b,
                    "main": main, "main_length": used_main,
                    "reused_chute": bool(chute),
                    "chute_pieces": chute, "chute_length": used_chute,
                    "waste": stock_length - used_main - used_chute,
                })
        num_new    = sum(1 for p in patterns)
        num_reused = sum(1 for p in patterns if p["reused_chute"])
        return {
            "num_new_bars": num_new,
            "num_reused_chutes": num_reused,
            "patterns": patterns,
            "status": "OPTIMAL" if status == cp_model.OPTIMAL else "FEASIBLE",
        }
    return {"num_new_bars": None, "patterns": [], "status": "INFEASIBLE"}


res = solve_cutting_stock_reuse(piece_lengths, demands,
                                stock_length=100, reuse_threshold=20)
print(f"Status : {res['status']}")
print(f"Barres neuves : {res['num_new_bars']}  |  Chutes reutilisees : {res['num_reused_chutes']}")
for p in res["patterns"]:
    tag = " (+ chute)" if p["reused_chute"] else ""
    pieces_main = [(piece_lengths[i], c) for i, c in p["main"].items()]
    print(f"  Barre {p['bar_id']}{tag} : coupe {pieces_main}  len={p['main_length']}")
    if p["reused_chute"]:
        pieces_chute = [(piece_lengths[i], c) for i, c in p["chute_pieces"].items()]
        print(f"      chute : {pieces_chute}  len={p['chute_length']}  reste={p['waste']}")
Status : OPTIMAL
Barres neuves : 4  |  Chutes reutilisees : 4
  Barre 0 (+ chute) : coupe []  len=0
      chute : [(25, 3)]  len=75  reste=25
  Barre 1 (+ chute) : coupe [(30, 2)]  len=60
      chute : [(40, 1)]  len=40  reste=0
  Barre 2 (+ chute) : coupe []  len=0
      chute : [(30, 2), (40, 1)]  len=100  reste=0
  Barre 3 (+ chute) : coupe []  len=0
      chute : [(20, 5)]  len=100  reste=0

Exercice 4b : Cutting Stock avec seuil de reutilisation eleve

Enonce : Resolvez un Cutting Stock avec des demandes plus elevees et un seuil de reutilisation plus strict (30 cm au lieu de 20 cm).

Données : - Longueurs de pieces : [15, 22, 35, 40] cm - Demandes : [8, 6, 5, 3] - Longueur des barres : 120 cm - Seuil de reutilisation : 30 cm

Consignes : 1. Utilisez solve_cutting_stock_reuse définie dans l’exemple ci-dessus 2. Comparez avec solve_cutting_stock_cp (sans reutilisation des chutes) 3. Affichez le nombre de barres neuves et le nombre de chutes reutilisees

# Exercice 4b : Cutting Stock avec seuil de reutilisation eleve

# Exercice: definissez les nouvelles donnees
new_piece_lengths = [15, 22, 35, 40]
new_demands       = [8, 6, 5, 3]
new_stock_length  = 120
new_reuse_thresh  = 30

# Exercice: resolvez avec solve_cutting_stock_reuse
# Exercice: comparez avec solve_cutting_stock_cp (sans chutes)
# Indice : un seuil plus eleve signifie moins de chutes reutilisables

# Votre code ici
print("Exercice a completer")
Exercice a completer

Annexe : parité lib-vs-lib — le même moteur Choco que le jumeau C

Les sections précédentes ont résolu les quatre problèmes d’optimisation avec OR-Tools CP-SAT (moteur C++ de Google). Le jumeau C# de ce notebook (CSP-5-Optimization-CSharp.ipynb) résout les mêmes familles de problèmes sur Choco-solver 4.10.17 via IKVM. Les deux moteurs sont SOTA-tier, mais différents : c’est l’asymétrie de machinerie documentée dans le registre de parité (#8057/#10382). Avec pychoco — le binding Python officiel de Choco (PyPI, MIT) — le jumeau Python peut rejouer les modèles du jumeau C# sur le même moteur industriel : c’est la parité lib-vs-lib, plus fine que la parité concept-vs-concept.

Chaque démonstration ci-dessous reprend l’instance exacte du jumeau C# (cellules 6/8/10/12) — instances volontairement distinctes de celles des sections 1 à 4, pour que l’annexe mesure la convergence des moteurs sans biaiser la comparaison du corps du notebook.

# Parite lib-vs-lib : le meme moteur Choco que le jumeau C# (pychoco)
# pychoco = binding Python officiel de Choco-solver (PyPI, MIT) -- meme moteur
# que le Choco 4.10.17/IKVM du jumeau C#. Instances = cellules 6/8/10/12 du twin C#.
import time
install_if_missing('pychoco')
try:
    import pychoco as pc
    HAS_PYCHOCO = True
except ImportError:
    HAS_PYCHOCO = False
    print("pychoco non disponible. Installer avec : pip install pychoco")

# --- Demo 1 (twin C# cell 6) : Bin Packing [2, 5, 4, 7, 2], capacite 10 ---
#   Borne inferieure ceil(20/10) = 2 bins INFAISABLE (le 7 ne partage avec
#   rien d'autre qu'un 2 : 7+4=11, 7+5=12). Optimum reel : 3 bins.
if HAS_PYCHOCO:
    sizes5 = [2, 5, 4, 7, 2]
    n5, cap5 = len(sizes5), 10
    nbins5 = n5  # majorant : chaque objet dans son propre bin
    m1 = pc.Model()
    bin_of5 = [m1.intvar(0, nbins5 - 1, name=f"b_{i}") for i in range(n5)]
    loads5 = [m1.intvar(0, cap5, name=f"load_{j}") for j in range(nbins5)]
    # eq[i][j] = 1 ssi objet i dans bin j (reification iff, comme le bEqJ du C#)
    eq5 = [[m1.boolvar(name=f"eq_{i}_{j}") for j in range(nbins5)] for i in range(n5)]
    for i in range(n5):
        for j in range(nbins5):
            m1.arithm(bin_of5[i], "=", j).reify_with(eq5[i][j])
    # Charge du bin j = somme des tailles des objets qui y sont (scalar)
    for j in range(nbins5):
        m1.scalar([eq5[i][j] for i in range(n5)], sizes5, "=", loads5[j]).post()
    # Symetrie brisee (compacite) : les bins vides en queue -- pattern Choco
    # "C1 => C2" : reifier C1 puis if_then(reif, C2), comme le C#.
    for j in range(nbins5 - 1):
        rj = m1.boolvar(name=f"cmp_{j}")
        m1.arithm(loads5[j], "=", 0).reify_with(rj)
        m1.if_then(rj, m1.arithm(loads5[j + 1], "=", 0))
    nb_used5 = m1.intvar(1, nbins5, name="nb_used")
    used5 = [m1.boolvar(name=f"used_{j}") for j in range(nbins5)]
    for j in range(nbins5):
        m1.arithm(loads5[j], ">", 0).reify_with(used5[j])  # iff
    m1.sum(used5, "=", nb_used5).post()
    m1.set_objective(nb_used5, maximize=False)  # MINIMIZE

    t0 = time.perf_counter()
    best5, best_assign5 = 0, None
    while m1.get_solver().solve():
        best5 = nb_used5.get_value()
        best_assign5 = [bin_of5[i].get_value() for i in range(n5)]
    dt1 = (time.perf_counter() - t0) * 1000
    print(f"Bin Packing : nombre optimal de bins = {best5} (capacite {cap5}) [{dt1:.0f} ms]")
    for j in range(nbins5):
        inbin = [i for i in range(n5) if best_assign5[i] == j]
        if inbin:
            ld = sum(sizes5[i] for i in inbin)
            print(f"  Bin {j} (charge {ld}/{cap5}) : objets {inbin} tailles {[sizes5[i] for i in inbin]}")
Bin Packing : nombre optimal de bins = 3 (capacite 10) [1 ms]
  Bin 0 (charge 2/10) : objets [4] tailles [2]
  Bin 1 (charge 9/10) : objets [1, 2] tailles [5, 4]
  Bin 2 (charge 9/10) : objets [0, 3] tailles [2, 7]

Interprétation : Bin Packing — le même optimum que le jumeau C

Sortie obtenue : 3 bins — le même optimum que la cellule BPP du jumeau C# sur la même instance [2, 5, 4, 7, 2]. La borne inférieure ceil(20/10) = 2 est inatteignable (le 7 ne peut partager qu’avec un 2) : les deux moteurs prouvent l’optimum à 3. L’assignation peut différer parmi les optima équivalents — ce qui converge ici, c’est la grandeur optimale certifiée, pas le choix de branche à qualité égale.

Le modèle est ligne à ligne celui du C# : réification eq[i,j] = (b[i] = j) puis scalar pour les charges (le C# décompose de la même façon, faute de contrainte globale sur ce premier modèle), symétrie brisée par compacité (if_then sur « bin vide ⇒ suivant vide »), objectif nb_used minimisé par la boucle solve() jusqu’à épuisement — le pattern branch-and-bound natif de Choco.

# --- Demo 2 (twin C# cell 8) : Knapsack 0/1, 5 objets, capacite 10 ---
#   Poids [2,3,4,5,1], valeurs [6,10,12,15,1]. Optimum connu : 31 (objets {0,1,3}).
if HAS_PYCHOCO:
    w5 = [2, 3, 4, 5, 1]
    v5 = [6, 10, 12, 15, 1]
    kcap5 = 10
    m2 = pc.Model()
    take5 = [m2.boolvar(name=f"take_{i}") for i in range(5)]
    tw5 = m2.intvar(0, sum(w5), name="total_weight")
    tv5 = m2.intvar(0, sum(v5), name="total_value")
    m2.scalar(take5, w5, "=", tw5).post()
    m2.arithm(tw5, "<=", kcap5).post()
    m2.scalar(take5, v5, "=", tv5).post()
    m2.set_objective(tv5, maximize=True)  # MAXIMIZE

    t0 = time.perf_counter()
    best_v5, best_w5, best_t5 = 0, 0, None
    while m2.get_solver().solve():
        best_v5, best_w5 = tv5.get_value(), tw5.get_value()
        best_t5 = [t.get_value() for t in take5]
    dt2 = (time.perf_counter() - t0) * 1000
    sel5 = [i for i in range(5) if best_t5[i] == 1]
    print(f"Knapsack : valeur optimale = {best_v5} (poids {best_w5}/{kcap5}) [{dt2:.0f} ms]")
    print(f"  Objets selectionnes : {sel5}")
    print(f"  Poids : {[w5[i] for i in sel5]}, Valeurs : {[v5[i] for i in sel5]}")
Knapsack : valeur optimale = 31 (poids 10/10) [0 ms]
  Objets selectionnes : [0, 1, 3]
  Poids : [2, 3, 5], Valeurs : [6, 10, 15]

Interprétation : Knapsack — convergence totale avec le jumeau C

Sortie obtenue : valeur optimale 31, poids exactement saturé 10/10, objets sélectionnés {0, 1, 3} — identiques à la cellule Knapsack du jumeau C#, jusqu’au choix d’optimum. L’instance n’admet qu’un seul optimum à 31 ({2,3,5} = 10 de poids, valeur 6+10+15) : la convergence des grandeurs et de la sélection matérialise ce que « même moteur » signifie — la modélisation scalar + set_objective(maximize=True) + boucle solve() est le miroir exact du setObjective(true, totalValue) du C#.

À rapprocher de la section 2 ci-dessus : CP-SAT (moteur C++) et Choco (moteur Java) trouvent chacun l’optimum sur leurs instances respectives — ici, les deux jumeaux exécutent le même bytecode Choco sous deux bindings (pychoco côté Python, IKVM côté .NET).

# --- Demo 3 (twin C# cell 10) : Cutting Stock, barres de longueur 10 ---
#   Pieces : 6x4, 4x7, 3x9. Optimum : 10 barres (aucun groupement inter-type
#   possible : 9+*>10 et 7+*>10 ; seules deux 4 tiennent ensemble : 4+4=8).
#   Contrainte GLOBALE bin_packing : l'idiome Choco natif, miroir direct du
#   modelCs.binPacking(barOf, pieceLengths, loadsCs, 0) du twin C#.
if HAS_PYCHOCO:
    pl5 = [4, 4, 4, 4, 4, 4, 7, 7, 7, 7, 9, 9, 9]
    stock5 = 10
    npcs5 = len(pl5)
    m3 = pc.Model()
    bar_of5 = [m3.intvar(0, npcs5 - 1, name=f"bar_{i}") for i in range(npcs5)]
    loads3 = [m3.intvar(0, stock5, name=f"load_{j}") for j in range(npcs5)]
    m3.bin_packing(bar_of5, pl5, loads3, 0).post()  # (item_bin, item_size, bin_load, offset)
    for j in range(npcs5):
        m3.arithm(loads3[j], "<=", stock5).post()
    for j in range(npcs5 - 1):
        rj = m3.boolvar(name=f"cmp_{j}")
        m3.arithm(loads3[j], "=", 0).reify_with(rj)
        m3.if_then(rj, m3.arithm(loads3[j + 1], "=", 0))
    nb_bars5 = m3.intvar(1, npcs5, name="nb_bars_used")
    act5 = [m3.boolvar(name=f"active_{j}") for j in range(npcs5)]
    for j in range(npcs5):
        m3.arithm(loads3[j], ">", 0).reify_with(act5[j])
    m3.sum(act5, "=", nb_bars5).post()
    m3.set_objective(nb_bars5, maximize=False)

    t0 = time.perf_counter()
    best3, best_bar5 = 0, None
    while m3.get_solver().solve():
        best3 = nb_bars5.get_value()
        best_bar5 = [bar_of5[i].get_value() for i in range(npcs5)]
    dt3 = time.perf_counter() - t0
    print(f"Cutting Stock : nombre optimal de barres = {best3} (longueur stock {stock5}) [{dt3:.1f} s]")
    bybar5 = {}
    for i, b in enumerate(best_bar5):
        bybar5.setdefault(b, []).append(pl5[i])
    for j in sorted(bybar5):
        print(f"  Barre {j} ({sum(bybar5[j])}/{stock5}) : longueurs {bybar5[j]}")
Cutting Stock : nombre optimal de barres = 10 (longueur stock 10) [10.9 s]
  Barre 0 (9/10) : longueurs [9]
  Barre 1 (9/10) : longueurs [9]
  Barre 2 (9/10) : longueurs [9]
  Barre 3 (8/10) : longueurs [4, 4]
  Barre 4 (7/10) : longueurs [7]
  Barre 5 (8/10) : longueurs [4, 4]
  Barre 6 (7/10) : longueurs [7]
  Barre 7 (8/10) : longueurs [4, 4]
  Barre 8 (7/10) : longueurs [7]
  Barre 9 (7/10) : longueurs [7]

Interprétation : Cutting Stock — la même décomposition optimale que le jumeau C

Sortie obtenue : 10 barres, avec exactement la structure prédite par l’analyse d’instance : 3 barres [9] isolées, 4 barres [7] isolées, 3 barres [4, 4] — la même décomposition que la cellule Cutting Stock du jumeau C#. L’instance force la solution (aucun groupement inter-type n’est possible), donc l’optimum est unique en structure : les deux moteurs convergent sur le multiset complet des patterns.

Le point lib-vs-lib de cette démo : la contrainte globale bin_packing du C# (modelCs.binPacking(...)) existe à l’identique côté pychoco (m3.bin_packing(...)). C’est l’idiome natif de Choco pour le Bin Packing / Cutting Stock : la propagation intégrée au solveur est plus forte que la décomposition scalar de la démo 1. À comparer à la section 3 ci-dessus, où CP-SAT modélise le Cutting Stock en variables de comptage par pattern (y[j,i]) : deux modélisations distinctes du même problème, un même optimum — la contrainte globale encode la structure du domaine directement dans le solveur.

# --- Demo 4 (twin C# cell 12) : Portefeuille lineaire, 5 actifs ---
#   Rendements [5,12,8,15,10], risques [10,20,15,30,18], max 3 actifs,
#   risque total <= 50. Deux optima a 27 : {1,3} (risque 50) et {0,1,4} (risque 48).
if HAS_PYCHOCO:
    r5 = [5, 12, 8, 15, 10]
    k5 = [10, 20, 15, 30, 18]
    maxa5, riskcap5 = 3, 50
    m4 = pc.Model()
    hold5 = [m4.boolvar(name=f"hold_{i}") for i in range(5)]
    tr5 = m4.intvar(0, sum(r5), name="total_return")
    tk5 = m4.intvar(0, sum(k5), name="total_risk")
    nh5 = m4.intvar(0, 5, name="nb_hold")
    m4.scalar(hold5, r5, "=", tr5).post()
    m4.scalar(hold5, k5, "=", tk5).post()
    m4.sum(hold5, "=", nh5).post()
    m4.arithm(nh5, "<=", maxa5).post()
    m4.arithm(tk5, "<=", riskcap5).post()
    m4.set_objective(tr5, maximize=True)

    t0 = time.perf_counter()
    best_r5, best_k5, best_h5 = 0, 0, None
    while m4.get_solver().solve():
        best_r5, best_k5 = tr5.get_value(), tk5.get_value()
        best_h5 = [h.get_value() for h in hold5]
    dt4 = (time.perf_counter() - t0) * 1000
    sel4 = [i for i in range(5) if best_h5[i] == 1]
    print(f"Portfolio : rendement optimal = {best_r5} (risque {best_k5}/{riskcap5}, {len(sel4)}/{maxa5} actifs) [{dt4:.0f} ms]")
    print(f"  Actifs selectionnes : {sel4}")
    print(f"  Rendements : {[r5[i] for i in sel4]}, Risques : {[k5[i] for i in sel4]}")
Portfolio : rendement optimal = 27 (risque 48/50, 3/3 actifs) [0 ms]
  Actifs selectionnes : [0, 1, 4]
  Rendements : [5, 12, 10], Risques : [10, 20, 18]

Interprétation : Portfolio — le même optimum, le même choix parmi les exqua-optima

Sortie obtenue : rendement optimal 27, risque 48/50, actifs {0, 1, 4} — exactement la solution de la cellule Portfolio du jumeau C#. L’instance admet deux optima à 27 ({1,3} au risque 50 exact, {0,1,4} au risque 48) : les deux jumeaux retombent sur le même. La version CP reste linéaire (proxy de risque = somme des risques marginaux, cf section 4) : le solveur par contraintes ne gère pas les produits de variables — la frontière complète moyenne-variance de Markowitz exigerait un solveur quadratique.

Bilan de l’annexe — parité lib-vs-lib mesurée sur les 4 démonstrations du jumeau C# :

Démonstration Observable Python (pychoco) Jumeau C# (Choco/IKVM) Convergence
Bin Packing [2,5,4,7,2]/10 bins optimaux 3 3 optimum identique
Knapsack 5 objets cap 10 valeur / sélection 31 / {0,1,3} 31 / {0,1,3} totale
Cutting Stock 13 pièces barres / patterns 10 / 3×[9] + 4×[7] + 3×[4,4] 10 / idem structure identique
Portfolio 5 actifs rendement / actifs 27 / {0,1,4} 27 / {0,1,4} totale

Avec cette annexe, le jumeau Python exécute le même moteur industriel (Choco-solver) que le jumeau C# — la parité passe de concept-vs-concept (sections 1-4 : CP-SAT d’un côté, Choco de l’autre) à lib-vs-lib (registre de parité #8057/#10382) : verdict SOTA-OK.

Références

  1. OR-Tools Bin Packing: https://developers.google.com/optimization/bin

  2. Knapsack Problems (2004): H. Kellerer, U. Pferschy, D. Pisinger

  3. Integer Programming (1998): L. Wolsey

  4. Modern Portfolio Theory: H. Markowitz (1952)

  5. Dantzig, G.B. (1957). Discrete-Variable Extremum Problems. Opérations Research 5(2):266-288.

  6. Johnson, D.S. (1974). Fast Algorithms for Bin Packing. Journal of Computer and System Sciences 8(3):272-314.

  7. Gilmore, P.C. & Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Opérations Research 9(6):849-859.

  8. Markowitz, H. (1952). Portfolio Sélection. The Journal of Finance 7(1):77-91.

Conclusion

Ce notebook a exploré les problèmes d’optimisation combinatoire où l’on cherche la meilleure solution parmi toutes les solutions valides.

Concepts clés

Concept Description
CSP d’optimisation CSP avec fonction objective à minimiser/maximiser
Branch & Bound Recherche avec bornes pour élaguer les sous-optimaux
Programmation linéaire Relaxation continue pour les bornes
Méthodes exactes Garantissent l’optimalité (mais coûteuses)
Méthodes approchées Heuristiques/Métaheuristiques (rapides mais sans garantie)

Approches pour l’optimisation

Approche Principe Garantie Coût
Branch & Bound Arbre de recherche + bornes Oui (optimale) Exponentiel
PLNE Programmation linéaire en nombres entiers Oui Très élevé
Recherche locale Voisinage + hill climbing Non Faible
Métaheuristiques Population, essaims, recuit Non Moyen

Points clés à retenir

  1. L’optimisation ajoute une couche de complexité aux CSP standards
  2. Branch & Bound est la base des solveurs d’optimisation exacts
  3. Les bornes (LP relaxation) sont cruciales pour l’efficacité
  4. Pour les problèmes NP-durs, les méthodes approchées sont souvent préférées
  5. Le choix de la méthode dépend du compromis temps/qualité souhaité

Voir aussi : - CSP-4-Scheduling.ipynb pour la recherche locale - CSP-6-Hybridization.ipynb pour les métaheuristiques

Retour au sommet