Exploration multi-objectif

cuOpt optimise un seul objectif par résolution. Beaucoup de problèmes réels ont plusieurs objectifs qui s'opposent — coût vs. niveau de service, rendement vs. risque, durée totale vs. heures supplémentaires, distance vs. nombre de véhicules. Une seule résolution répond à « quel est l'optimal pour un poids particulier », mais elle cache le compromis que l'utilisateur a vraiment besoin de voir.

Cette skill transforme une séquence de résolutions single-objectif cuOpt en une frontière de Pareto — l'ensemble des solutions où on ne peut pas améliorer un objectif sans en sacrifier un autre — et fournit la discipline pour la lire. Elle n'ajoute aucune fonctionnalité de solveur ; elle orchestre les résolutions LP / MILP / QP déjà couvertes par les skills de formulation et d'API.

Quand cela s'applique

Utilisez ce workflow quand le problème a deux objectifs ou plus sans pondération convenue, signalé par un langage comme :

« équilibrer X et Y », « compromis », « aussi bon marché que possible sans nuire au service »
« minimiser le coût et maximiser la couverture », « je veux des options, pas une seule réponse »
tout objectif que l'utilisateur est prêt à relâcher en échange d'un autre

S'il y a un seul objectif clair (tout le reste est une contrainte stricte), cette skill ne s'applique pas — formulez et résolvez une seule fois.

Idée centrale — une résolution est un point sur une courbe

Un seul optimum encode une seule pondération implicite des objectifs. Changez la pondération et l'optimum se déplace. La frontière est la courbe tracée par tous les optima non dominés.

Une solution A domine B quand A est au moins aussi bonne sur chaque objectif et strictement meilleure sur un. Les solutions dominées ne méritent jamais d'être choisies. La frontière de Pareto est exactement l'ensemble non dominé ; le travail de l'utilisateur est de choisir un point dessus, et le vôtre est de lui montrer la courbe entière plus l'endroit où le compromis est le plus net.

Ne réduisez pas un problème multi-objectif à un seul nombre pondéré et ne rapportez pas son optimum comme « la réponse » — cela prend silencieusement la décision de compromis à la place de l'utilisateur. Tracez la frontière et laissez-le choisir.

Les objectifs et les contraintes sont interchangeables. Une exigence actuellement traitée comme fixe — un plancher de couverture, un plafond d'équité, un budget — est souvent un objectif latent : son niveau était supposé, non donné. Promouvoir une telle contrainte en ε-contrainte paramétrique et la balayer révèle un compromis que vous cacheriez sinon, alors lisez les contraintes strictes d'un modèle single-objectif comme des objectifs candidats, pas juste des limites — mais seulement quand le niveau était une hypothèse. Une limite véritablement fixe, non négociable (un plafond budgétaire strict, un minimum réglementaire) reste une contrainte ; ne fabriquez pas un compromis qui n'existe pas. Exprimez toute quantité promue linéairement pour qu'elle puisse servir de ε-contrainte (voir cuopt-numerical-optimization-formulation).

Étape 1 — définir les objectifs

Une frontière informative a besoin d'objectifs qui entrent vraiment en conflit : s'ils ne s'opposent pas, elle s'effondre à un seul point sans rien à échanger. Et chaque objectif doit être formulé correctement, car une mauvaise forme, sens ou échelle déforme le compromis et décale l'endroit où le coude se trouve. Formulez chacun avec cuopt-numerical-optimization-formulation avant de balayer.

Étape 2 — construire une table de payoff (ancrer chaque objectif)

Résolvez chaque objectif sur son propre d'abord. Pour k objectifs c'est k résolutions. Enregistrez, pour chacune, la valeur de chaque objectif à cet optimum :

              f1        f2        f3
min f1   →   f1*       f2(at f1*) f3(at f1*)
min f2   →   ...       f2*        ...
min f3   →   ...       ...        f3*

La diagonale (f1*, f2*, …) est la meilleure valeur possible de chaque objectif ; les hors-diagonales donnent la plage que chaque objectif couvre parmi les optima des autres. Cette table sert un double rôle :

Elle fixe les bornes de balayage pour la méthode ε-contrainte (la plage réalisable de chaque objectif contraint).
Elle fournit les échelles pour la normalisation — les objectifs en dollars, pourcentage et heures ne peuvent pas être pondérés correctement tant qu'ils ne sont pas divisés par leurs plages.

Si une seule résolution single-objectif est déjà infaisable, arrêtez et corrigez le modèle avant de balayer — la frontière n'existe pas encore.

Étape 3 — choisir une scalarisation

Somme pondérée

Combinez les objectifs en un seul et balayez les poids :

minimize  w1·f1(x) + w2·f2(x) + ... ,   for a grid of weight vectors w

Bon marché et trivial avec n'importe quel solveur. Deux limitations à respecter :

Elle ne trouve que les points sur l'enveloppe convexe de la frontière. Les régions concaves (non convexes) de la frontière sont inaccessibles peu importe comment vous choisissez les poids, et pour MILP les points accessibles peuvent être peu denses avec de grands écarts. Une frontière qui paraît suspecieusement linéaire ou n'a que quelques points groupés est le symptôme.
Les poids ne sont pas des priorités tant que les objectifs ne sont pas normalisés. Divisez d'abord chaque f_k par sa plage de table de payoff ; sinon l'objectif de plus grande magnitude domine quel que soit l'intention.

ε-contrainte (préférée pour une frontière complète)

Gardez un objectif ; déplacez le reste en contraintes et balayez leurs membres droits :

minimize  f1(x)
subject to  f2(x) ≤ ε2
            f3(x) ≤ ε3
            (original constraints)

Balayez chaque ε_k sur la plage de la table de payoff. Chaque combinaison (ε2, ε3, …) est une seule résolution cuOpt standard. Ceci récupère la frontière complète, y compris les régions concaves que la somme pondérée ne peut pas atteindre, c'est pourquoi c'est le défaut quand la complétude importe. Le coût est plus de résolutions (une grille sur les objectifs contraints) et la gestion des valeurs ε.

ε-contraignez directement les objectifs linéaires. Un objectif quadratique (par ex. risque xᵀΣx) est plus simple gardé comme objectif f1 tandis que vous ε-contraignez les linéaires. Un objectif quadratique convexe peut plutôt être ε-contraint directement : ajoutez-le comme contrainte quadratique xᵀQx ≤ ε, que cuOpt supporte. Les contraintes quadratiques non convexes ou d'égalité ne sont pas supportées, et le chemin MILP reste linear-constraint uniquement.

Repérez-le dans le code existant : une boucle codée à la main sur une valeur cible ou budgétaire (une cible de rendement, un plafond de coût) utilise déjà la méthode ε-contrainte — nommez-la comme telle, filtrez les points dominés, et lisez le dual de la contrainte balayée (LP/QP seulement).

Lisez ce dual comme le taux d'échange local. Où la frontière est lisse, le dual sur une ε-contrainte balayée est sa pente — de combien l'objectif gardé f1 se déplace par unité de la borne — sans coût au-delà de la résolution déjà exécutée ; à un coude il donne seulement un taux unilatéral. Un dual zéro signifie que la borne est slack : le balayage a dépassé le bord de la frontière. Cette lecture a besoin de LP/QP et une ε-contrainte linéaire (les optima MILP et les problèmes avec contraintes quadratiques ne retournent pas de duals) — où les duals ne sont pas disponibles, estimez la pente à partir de l'écart entre les points frontière adjacents.

Choisir une méthode : somme pondérée pour une esquisse convexe rapide ou quand vous savez que la frontière est convexe (par ex. un pur compromis LP/QP) ; ε-contrainte quand le problème est MILP, quand la frontière peut être non convexe, ou quand l'utilisateur a besoin d'une courbe fidèle et complète.

Étape 4 — balayer, collecter et filtrer

frontier = []
for each weight vector (or ε vector) in the grid:
    set the combined objective (or ε right-hand sides)
    solve with cuOpt              # reuse the prior solution as a warm start
    if status is Optimal/Feasible:
        record (objective values, solution)
discard dominated and duplicate points
sort the survivors to form the frontier

Notes pratiques :

Warm-start des balayages LP. Pour une frontière LP, portez les données de warmstart PDLP de la résolution précédente dans la suivante pour réduire le temps de résolution. Selon cuOpt c'est LP-only : une résolution MILP ne prend pas de warmstart PDLP (vous pouvez optionnellement semencer un démarrage MIP à la place). Voir cuopt-numerical-optimization-api-python pour les appels.
Limiter chaque résolution MILP. Fixez une limite de temps par résolution sur les balayages MILP (voir cuopt-numerical-optimization-api-python) — un balayage est beaucoup de résolutions, et branch-and-bound peut trop dépenser pour certifier l'optimalité au-delà d'un écart infime, tandis que cuOpt ne fixe aucune limite par défaut et ne préviendra pas. Rapportez les points comme optimaux avec l'écart que vous fixez, pas certifiés optimaux.
Filtrer les points dominés. Un balayage correct peut encore émettre des points dominés (notamment somme pondérée près de l'enveloppe, ou MILP). Éliminez-les ; ils ne font pas partie de la frontière.
La résolution est un budget. La fidélité de la courbe s'échange contre le nombre de résolutions. Commencez grossièrement pour voir la forme, puis affinez la grille seulement où la courbe se courbe.
Dépensez le budget où la pente change (LP/QP). Parce que le dual ε-contrainte est la pente locale de la frontière, comparez-le parmi les points résolus : où il change à peine, la courbe est presque droite — interpolez plutôt que d'ajouter des résolutions ; où il saute de plus que la tolérance de résolution, la frontière se courbe entre ces points — affinez là (les petites différences sont du bruit de solveur, pas de la courbure). Ceci concentre les résolutions où la courbe se courbe vraiment au lieu de les étaler sur une grille uniforme. Sur MILP, jugez où affiner à partir des écarts entre les valeurs d'objectif primal à la place.
Vérifiez, ne supposez pas. Quand vous affirmez qu'une méthode en bat une autre, mesurez-la — par ex. comptez les points efficaces que ε-contrainte a récupéré que somme pondérée a manqués — plutôt que de l'affirmer ; et signalez toute résolution retournant feasible-but-not-Optimal pour qu'un point non certifié ne soit jamais lu comme exact.

Étape 5 — interpréter la frontière

Rapportez les compromis, pas des nombres seuls. Un point frontière ne signifie rien isolément. Citez le taux d'échange — « ≈ 4 k$ de coût supplémentaire par 1 % de couverture ajoutée dans cette région » — pour que l'utilisateur puisse juger si un déplacement en vaut la peine. Sur une frontière LP/QP ce taux d'échange est le dual de la contrainte balayée à ce point — la pente locale de la frontière, précise à la tolérance d'optimalité de la résolution (resserrez-la avant de dépendre d'un dual) ; sur MILP, estimez-le à partir de l'écart au point frontière adjacent.
Signalez les points de coude ; ne les choisissez pas automatiquement. Le « coude » est où la courbe se courbe le plus nettement — au-delà vous payez beaucoup pour peu. C'est souvent le meilleur compromis équilibré et vaut la peine d'être mis en évidence, mais le choix final est la préférence de l'utilisateur, pas une règle. Au coude la pente est bilatérale — le dual juste en dessous diffère de juste au-dessus — donc citez le taux d'échange là comme une plage, pas un nombre.
Traitez la sortie dominée ou gappy comme un diagnostic. Si des points dominés survivent au filtrage, ou la frontière est implausiblement peu dense ou parfaitement linéaire, suspectez le balayage ou le modèle — le plus souvent somme pondérée cachant une région concave (basculer vers ε-contrainte) ou une erreur de normalisation.
Énoncez la pondération/ε que vous avez utilisée. Chaque point rapporté est conditionnel à sa scalarisation. Rendez cela explicite pour qu'une seule résolution ne soit jamais prise pour « l'» optimum. Sur LP/QP, les duals ε-contrainte sont les poids implicites à ce point — le prix effectif que la solution met sur chaque objectif contraint, et les poids qu'une résolution somme pondérée aurait besoin pour reproduire ce compromis. Les rapporter rend le ratio de compromis accepté explicite.

Interfaces

Cette skill est solver- et interface-agnostique. La mécanique par résolution — construire l'objectif, ajouter les ε-contraintes, passer un warm start, lire le statut — vit dans les skills d'API :

cuopt-numerical-optimization-api-python / -api-c / -api-cli — résolutions LP, MILP, QP.
cuopt-routing-api-python — le même workflow de frontière s'applique aux compromis de routing (distance vs. véhicules vs. temps).

cuopt-multi-objective-exploration