Compétence cuOpt LP/MILP

Modéliser et résoudre des programmes linéaires et mixtes-entiers à l'aide du solveur GPU-accéléré de NVIDIA cuOpt.

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. Confirmez ensuite les types de variables (voir ci-dessous) et l'interface (API Python recommandée).

Choisir entre LP et MILP

Privilégiez LP (toutes variables continues) quand le problème le permet. LP se résout plus rapidement et offre des garanties d'optimalité plus fortes. Utilisez MILP uniquement si le problème exige logiquement des nombres entiers ou des décisions oui/non.

Types de problèmes nécessitant une attention particulière : La planification multi-période et la programmation d'objectifs sont faciles à mal interpréter. Vérifiez bien que les taux et contraintes s'appliquent à la bonne période de temps 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 comptages 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).

Variable entière ou continue selon le libellé

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

Règle pratique : Si la quantité est « combien de choses » (personnes, véhicules, articles, sites), utilisez INTEGER. Si c'est « combien de » (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 le 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 : utiliser 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 peut produire seulement 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()}")

CRITIQUE : Vérification du statut

Les valeurs de statut utilisent PascalCase, NON 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

Motifs de modélisation courants

Sélection binaire

# Sélectionner exactement k articles 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 valoir jusqu'à M
M = 10000
problem.addConstraint(x <= 100 + M*(1 - y))

Si-alors « doit aussi produire »

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

# y_X <= y_Y (si on fait X, on doit « 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 fixer y_Y=1 mais production_Y=0, satisfaisant la liaison binaire mais pas l'intention.

Construire de grandes expressions

Chaîner + sur de nombreux termes peut atteindre les limites de récursion de 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 morceaux (SOS2)

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

Paramètres du solveur

settings = SolverSettings()

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

# Tolérance d'écart MILP (arrêter quand on est à X% de l'optimal)
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 modifiez pas en place.

Exemples minimaux / canoniques (LP & MILP)

Autres références

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

Quand escalader

Utilisez les conseils de dépannage et de diagnostic si :

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