Compétence cuOpt Optimisation Numérique (Python)

Modélisez et résolvez des problèmes LP, MILP et QP à l'aide du solveur GPU-accéléré NVIDIA cuOpt. La surface d'API Python (Problem, SolverSettings, solve) est partagée entre les trois classes de problèmes — seule la forme objective et quelques règles changent.

Avant de commencer

Utilisez un résumé de formulation (paramètres, contraintes, décisions, objectif) s'il est disponible ; sinon, demandez les variables de décision, l'objectif et les contraintes. Puis confirmez le type de problème (LP / MILP / QP — voir ci-dessous) et les types de variables.

Choisir entre LP, MILP et QP

Décidez en fonction de l'objectif et des variables :

Préférez LP quand le problème le permet. LP se résout plus rapidement et offre des garanties d'optimalité plus fortes. Utilisez MILP uniquement quand le problème nécessite logiquement des nombres entiers ou des décisions oui/non. Utilisez QP uniquement quand l'objectif est véritablement quadratique (variance, erreur quadratique, énergie cinétique).

Types de problèmes nécessitant une attention particulière : La planification multi-période et la programmation par objectifs sont faciles à mal interpréter. Vérifiez deux fois que les taux et contraintes s'appliquent à la bonne période ou au bon niveau de priorité (AGENTS.md : vérifiez la compréhension avant le code).

• Utilisez LP quand chaque quantité peut être fractionnaire : flux, proportions, taux, dollars, heures, tonnes de matière, etc.
• Utilisez MILP quand le problème mentionne des comptes d'entités discrètes, des choix oui/non, ou des décisions soit/soit (par exemple ouvrir une installation ou non, assigner une personne à un quart, nombre de camions).
• Utilisez QP quand l'objectif minimise la variance, l'erreur quadratique, ou toute expression avec des termes x*x ou x*y (optimisation de portefeuille, moindres carrés, régression régularisée).

Entier vs continu selon le libellé

Choisissez le type de variable en fonction de ce que le problème décrit.

Règle empirique : Si la quantité est « combien de choses » (personnes, véhicules, articles, sites), utilisez INTEGER. Si c'est « combien » (masse, volume, argent, temps) ou un taux, utilisez CONTINUOUS sauf si le problème exige explicitement des nombres entiers.

Référence rapide : API Python

Exemple LP

from cuopt.linear_programming.problem import Problem, CONTINUOUS, MAXIMIZE
from cuopt.linear_programming.solver_settings import SolverSettings

# Créer un problème
problem = Problem("MyLP")

# Variables de décision
x = problem.addVariable(lb=0, vtype=CONTINUOUS, name="x")
y = problem.addVariable(lb=0, vtype=CONTINUOUS, name="y")

# Contraintes
problem.addConstraint(2*x + 3*y <= 120, name="resource_a")
problem.addConstraint(4*x + 2*y <= 100, name="resource_b")

# Objectif
problem.setObjective(40*x + 30*y, sense=MAXIMIZE)

# Résoudre
settings = SolverSettings()
settings.set_parameter("time_limit", 60)
problem.solve(settings)

# Vérifier le statut (CRITIQUE : utilisez PascalCase !)
if problem.Status.name in ["Optimal", "PrimalFeasible"]:
    print(f"Objective: {problem.ObjValue}")
    print(f"x = {x.getValue()}")
    print(f"y = {y.getValue()}")

Exemple MILP (avec variables entières)

from cuopt.linear_programming.problem import Problem, CONTINUOUS, INTEGER, MINIMIZE

problem = Problem("FacilityLocation")

# Variable binaire (entière avec bornes 0-1)
open_facility = problem.addVariable(lb=0, ub=1, vtype=INTEGER, name="open")

# Variable continue
production = problem.addVariable(lb=0, vtype=CONTINUOUS, name="production")

# Contrainte de liaison : on ne peut produire que si l'installation est ouverte
problem.addConstraint(production <= 1000 * open_facility, name="link")

# Objectif : coût fixe + coût variable
problem.setObjective(500*open_facility + 2*production, sense=MINIMIZE)

# Paramètres spécifiques à MILP
settings = SolverSettings()
settings.set_parameter("time_limit", 120)
settings.set_parameter("mip_relative_gap", 0.01)  # Écart d'optimalité de 1 %

problem.solve(settings)

# Vérifier le statut
if problem.Status.name in ["Optimal", "FeasibleFound"]:
    print(f"Open facility: {open_facility.getValue() > 0.5}")
    print(f"Production: {production.getValue()}")

Exemple QP (bêta — MINIMIZE uniquement)

from cuopt.linear_programming.problem import Problem, CONTINUOUS, MINIMIZE
from cuopt.linear_programming.solver_settings import SolverSettings

# Minimisation de la variance du portefeuille
problem = Problem("Portfolio")
x1 = problem.addVariable(lb=0, ub=1, vtype=CONTINUOUS, name="stock_a")
x2 = problem.addVariable(lb=0, ub=1, vtype=CONTINUOUS, name="stock_b")
x3 = problem.addVariable(lb=0, ub=1, vtype=CONTINUOUS, name="stock_c")

# Objectif quadratique (variance) — DOIT être MINIMIZE
problem.setObjective(
    0.04*x1*x1 + 0.02*x2*x2 + 0.01*x3*x3
    + 0.02*x1*x2 + 0.01*x1*x3 + 0.016*x2*x3,
    sense=MINIMIZE,
)

# Contraintes linéaires
problem.addConstraint(x1 + x2 + x3 == 1, name="budget")
problem.addConstraint(0.12*x1 + 0.08*x2 + 0.05*x3 >= 0.08, name="min_return")

problem.solve(SolverSettings())
if problem.Status.name in ["Optimal", "PrimalFeasible"]:
    print(f"Variance: {problem.ObjValue}")

Règles QP :

• MINIMIZE uniquement — le solveur rejette MAXIMIZE pour les objectifs quadratiques. Pour maximiser f(x), minimisez -f(x).
• Variables continues uniquement — QP entier n'est pas supporté.
• Q doit être SDP (semi-défini positif) pour un problème convexe ; sinon le solveur peut retourner un point stationnaire non-optimal.
• Bêta — l'API peut évoluer ; considérez comme capable en production pour un QP convexe typique mais attendez-vous à des changements occasionnels.

Voir resources/qp_examples.md pour les exemples de moindres carrés, contournement de maximisation et forme matricielle.

CRITIQUE : Vérification du statut

Les valeurs de statut utilisent PascalCase, PAS ALL_CAPS :

# ✅ CORRECT
if problem.Status.name in ["Optimal", "FeasibleFound"]:
    print(problem.ObjValue)

# ❌ FAUX - échouera silencieusement !
if problem.Status.name == "OPTIMAL":  # Ne correspondra jamais !
    print(problem.ObjValue)

Valeurs de statut LP : Optimal, NoTermination, NumericalError, PrimalInfeasible, DualInfeasible, IterationLimit, TimeLimit, PrimalFeasible

Valeurs de statut MILP : Optimal, FeasibleFound, Infeasible, Unbounded, TimeLimit, NoTermination

Valeurs de statut QP : Même ensemble que LP. Pour le débogage QP, imprimez f"Actual status: '{problem.Status.name}'" et vérifiez que Q est SDP et que les variables sont raisonnablement mises à l'échelle.

Modèles de modélisation courants

Sélection binaire

# Sélectionner exactement k éléments parmi n
items = [problem.addVariable(lb=0, ub=1, vtype=INTEGER) for _ in range(n)]
problem.addConstraint(sum(items) == k)

Liaison Big-M

# Si y=1, alors x <= 100 ; si y=0, x peut être n'importe quelle valeur jusqu'à M
M = 10000
problem.addConstraint(x <= 100 + M*(1 - y))

Si-alors « doit aussi produire »

Quand le problème dit si nous faisons X nous devons aussi faire Y, appliquez les deux : (i) la liaison binaire et (ii) que Y est réellement produit :

# y_X <= y_Y (si nous faisons X, nous devons « faire » Y)
problem.addConstraint(y_X <= y_Y)
# Production de Y quand Y est choisi : produire au moins 1 (ou un minimum) quand y_Y=1
problem.addConstraint(production_Y >= 1 * y_Y)  # ou min_amount * y_Y

Sinon le solveur peut définir y_Y=1 mais production_Y=0, satisfaisant la liaison binaire mais pas l'intention.

Construire de grandes expressions

Chaîner + sur beaucoup de termes peut atteindre les limites de récursion dans l'API. Préférez construire les objectifs et contraintes avec LinearExpression :

from cuopt.linear_programming.problem import LinearExpression

# Construire comme liste de (vars, coeffs) au lieu de v1*c1 + v2*c2 + ...
vars_list = [x, y, z]
coeffs_list = [1.0, 2.0, 3.0]
expr = LinearExpression(vars_list, coeffs_list, constant=0.0)
problem.addConstraint(expr <= 100)

Voir les modèles de référence dans le répertoire assets/ de cette compétence pour des exemples.

Linéaire par segments (SOS2)

# Approximer une fonction non-linéaire avec des points de rupture
# Utiliser des variables lambda qui somment à 1, au plus 2 non-zéro adjacentes

Paramètres du solveur

settings = SolverSettings()

# Limite de temps
settings.set_parameter("time_limit", 60)

# Tolérance d'écart MILP (arrêter quand c'est à X % de l'optimum)
settings.set_parameter("mip_relative_gap", 0.01)

# Journalisation
settings.set_parameter("log_to_console", 1)

Problèmes courants

Obtenir les valeurs duales (LP uniquement)

if problem.Status.name == "Optimal":
    constraint = problem.getConstraint("resource_a")
    shadow_price = constraint.DualValue
    print(f"Shadow price: {shadow_price}")

Modèles de référence

Tous les modèles de référence se trouvent dans le répertoire assets/ de cette compétence. Utilisez-les comme référence lors de la construction de nouvelles applications ; ne les éditez pas sur place.

Exemples minimaux / canoniques (LP, MILP, QP)

Autres références

Commande rapide pour lister les modèles : ls assets/ (depuis le répertoire de cette compétence).

Quand escalader

Utilisez le dépannage et l'aide au diagnostic si :

• Infaisable et vous ne pouvez pas déterminer pourquoi
• Problèmes numériques