Formulation d'optimisation numérique

Concepts et workflow pour passer d'une description de problème à une formulation claire en LP, MILP et QP. Aucun code API ici.

Qu'est-ce que LP / MILP / QP

• LP : objectif linéaire, contraintes linéaires, variables continues.
• MILP : comme LP plus certaines variables entières ou binaires (p. ex., planification, localisation d'installations, sélection).
• QP : objectif quadratique (p. ex., x², x·y — variance de portefeuille, moindres carrés), contraintes linéaires. Le support QP dans cuOpt est actuellement en bêta.

Identifier le type de problème

Si l'objectif est purement linéaire, préférez LP/MILP — n'introduisez pas artificiellement de termes quadratiques. Si une variable est entière ou binaire, le problème est MILP indépendamment du reste.

Questions de formulation obligatoires

Posez-les si ce n'est pas déjà clair :

1. Variables de décision — Qu'est-ce que c'est ? Bornes ?
2. Objectif — Minimiser ou maximiser ? Linéaire ou quadratique ? Pour QP : y a-t-il des termes au carré ou croisés (x², x·y) ? Si maximiser une fonction quadratique, l'utilisateur doit la nier et minimiser.
3. Contraintes — Inégalités/égalités linéaires ? (Les contraintes quadratiques ne sont pas supportées.)
4. Types de variables — Tout continu (LP / QP) ou certaines entières/binaires (MILP) ?
5. Convexité (QP uniquement) — Pour la minimisation, la forme quadratique (matrice Q) doit être semi-définie positive pour que les problèmes soient bien posés.

Éléments de modélisation typiques

• Variables continues — quantités de production, flux, allocations, poids de portefeuille.
• Variables binaires — ouverture/fermeture, oui/non (p. ex., installation ouverte, article sélectionné).
• Contraintes de liaison — p. ex., production seulement si installation ouverte (Big-M ou indicateur).
• Contraintes de ressources — limite linéaire sur l'utilisation (matériaux, temps, capacité).
• Termes objectifs quadratiques — variance (xᵀQx), erreur au carré (‖Ax − b‖²), termes d'interaction.

Cas d'usage typiques de QP

• Optimisation de portefeuille — minimiser la variance sous contrainte de rendement et budget.
• Moindres carrés — minimiser ‖Ax − b‖² sous contraintes linéaires.
• Autres objectifs quadratiques avec contraintes linéaires.

Analyse d'énoncé de problème

Quand l'utilisateur donne un texte de problème, classez chaque phrase, puis résumez avant de formuler. Le framework d'analyse ci-dessous s'applique indépendamment de LP / MILP / QP.

Classez chaque phrase comme paramètre/donnée, contrainte, décision, ou objectif. Attention aux contraintes implicites (p. ex., formulation engagée vs optionnelle) et objectifs implicites (p. ex., « déterminer le plan » + coûts → minimiser le coût total).

Ambiguïté : Si quelque chose reste ambigu, demandez à l'utilisateur ou résolvez toutes les interprétations plausibles et rapportez tous les résultats ; ne supposez pas une interprétation unique.

🔒 OBLIGATOIRE : En cas de doute — Demander

• S'il y a un quelconque doute sur le fait qu'une contrainte ou valeur doit être incluse, posez la question à l'utilisateur et énoncez les interprétations possibles.

🔒 OBLIGATOIRE : Exécutions complètes — Essayer toutes les variantes

• Quand l'utilisateur demande d'exécuter le chemin complet (p. ex., de bout en bout, pipeline complet), lancez toutes les variantes plausibles et rapportez tous les résultats afin que l'utilisateur puisse choisir ; ne supposez pas une interprétation unique.

Trois labels

Contraintes implicites : formulation engagée vs optionnelle

Formulation engagée/fixe → traiter comme paramètre ou contrainte implicite (tout ce qui est mentionné est donné ou doit arriver). Pas une décision.

Formulation optionnelle/décision → traiter comme décision.

Objectifs implicites — ne pas manquer

Si le problème demande de « déterminer le plan » (ou similaire) mais n'énonce pas explicitement « minimiser » ou « maximiser », l'objectif est souvent implicite. Vous DEVEZ l'identifier et l'énoncer avant de formuler ; ne construisez pas un modèle sans objectif.

Règle : Quand le problème donne des données de coût (ou de coût et revenu) et demande de « déterminer », « trouver », ou « établir » le plan, énoncez toujours l'objectif explicitement (p. ex., « Je traite l'objectif comme minimiser le coût total, puisque seuls les coûts sont donnés. »). Si coût et revenu sont tous deux présents, énoncez si vous utilisez « minimiser le coût » ou « maximiser le profit ». Demandez à l'utilisateur si c'est ambigu.

Workflow d'analyse

1. Divisez le texte du problème en phrases ou clauses logiques.
2. Labelisez chacune : paramètre/donnée | contrainte | décision | objectif (si énoncé).
3. Identifiez l'objectif (explicite ou implicite) : Si le problème dit « minimiser/maximiser X », c'est l'objectif. S'il dit seulement « déterminer le plan » (ou « trouver », « établir ») mais donne les coûts (et possiblement revenus), l'objectif est implicite — énoncez-le (p. ex., minimiser le coût total, ou maximiser le profit) et confirmez avec l'utilisateur si ambigu.
4. Signalez les contraintes implicites : Pour chaque phrase, demandez-vous — « Énonce-t-elle un fait fixe ou une exigence (→ paramètre/contrainte), ou quelque chose que nous choisissons (→ décision) ? »
5. Résolvez l'ambiguïté en vérifiant les verbes et les modaux :
   • « est », « a », « exploite », « emploie », « plans de » (fixe/engagé) → paramètre ou contrainte implicite.
   • « peut », « peut choisir », « envisage », « décide », « veut » (optionnel) → décision ou objectif.
6. 🔒 OBLIGATOIRE — Si quelque chose reste ambigu (p. ex., une valeur ou contrainte pourrait être lue de deux manières) : demandez à l'utilisateur quelle interprétation est correcte, ou résolvez toutes les interprétations plausibles et rapportez tous les résultats. Ne supposez pas une interprétation unique.
7. Résumez pour l'utilisateur : listez paramètres, contraintes (explicites + signalées implicites), décisions, et objectif (explicite ou déduit) avant d'écrire la formulation mathématique.

Checklist d'analyse

• [ ] Chaque phrase a un label (paramètre | contrainte | décision | objectif si énoncé).
• [ ] L'objectif est identifié : Explicite (« minimiser/maximiser X ») ou implicite (« déterminer le plan » + coûts → minimiser le coût total ; + revenus → maximiser le profit). Ne jamais formuler sans énoncer l'objectif.
• [ ] Formulation engagée (« plans de », « exploite », « emploie ») → pas des décisions.
• [ ] Formulation optionnelle (« peut », « peut choisir », « envisage ») → décisions.
• [ ] Les contraintes implicites de formulation engagée sont écrites (p. ex., « tout X doit être produit »).
• [ ] 🔒 OBLIGATOIRE — Ambiguïté : Toute phrase qui pourrait être lue de deux manières → J'ai demandé à l'utilisateur ou je résoudrai toutes les interprétations et rapporterai tous les résultats (pas d'interprétation unique silencieuse).
• [ ] Un résumé est produit avant la formulation (paramètres, contraintes, décisions, objectif).

Exemple

Texte : « L'entreprise exploite 3 usines et prévoit de produire 500 unités. Elle peut utiliser des heures supplémentaires à un coût supplémentaire. Minimiser le coût total. »

Résultat : Paramètres = 3 usines, objectif de 500 unités. Contraintes = produire exactement 500 (implicite de « prévoit de produire »). Décisions = allocation de la production entre usines, montants d'heures supplémentaires. Objectif = minimiser le coût.

Exemple d'objectif implicite : Un problème qui demande de « déterminer le plan de production » (ou similaire) et donne les éléments de coût (p. ex., atelier, inspection, ventes) mais n'énonce pas « minimiser » ou « maximiser » → L'objectif est implicite : minimiser le coût total. Énoncez-le toujours explicitement : « L'objectif est de minimiser le coût total. »

Règle QP : minimisation uniquement

Les objectifs QP doivent être minimisation. Pour maximiser une expression quadratique, niez-la et minimisez ; puis niez la valeur optimale.

Pour que la minimisation soit bien posée, la forme quadratique Q doit être semi-définie positive. Si Q est indéfinie, le problème est non-convexe et peut ne pas avoir un optimum fini.

Motifs courants

Les sections suivantes couvrent des motifs de modélisation spécifiques pour LP/MILP. Chacun est indépendant — lisez celui qui correspond à votre problème.

Objectifs par morceaux linéaires avec production entière

Pour modéliser les fonctions de profit/coût concaves par morceaux (p. ex., profit marginal décroissant pour ventes en vrac), l'approche standard utilise des variables de segment continues avec bornes supérieures égales à la largeur de chaque segment. Pour une maximisation avec profit concave, le solveur remplit naturellement les segments à profit supérieur en premier.

Piège : Si la quantité produite est discrète (pièces, unités, articles), la variable de production totale doit être ENTIÈRE, même si les variables de segment peuvent rester CONTINUES. Sans cela, la relaxation LP peut donner un total fractionnaire qui produit un objectif différent (supérieur ou inférieur) que l'optimum entier vrai.

Motif

x_total  — ENTIÈRE (production totale d'un produit)
s1, s2, … — CONTINUES (quantité vendue dans chaque segment de prix, bornée par la largeur du segment)

Liaison : x_total = s1 + s2 + …
Contraintes de ressources utilisent x_total.
Objectif utilise variables de segment × taux de profit du segment.

Problèmes de découpe / perte de coupe

Dans les problèmes de découpe, la zone de déchet inclut à la fois la perte de coupe (largeur inutilisée dans chaque motif de découpe) et la surproduction (bandes excédentaires produites au-delà de la demande). Minimiser seulement la perte de coupe (largeur de déchet × longueur par motif) ignore la surproduction et donne un objectif incorrect.

Objectif correct

Puisque la surface utile totale demandée est une constante, minimiser le déchet est équivalent à minimiser la surface de matériau total consommé :

minimiser  sum_j (roll_width_j × x_j)

où x_j est la longueur coupée selon le motif j. La surface de déchet est alors :

déchet = surface_matériau_total − surface_utile_requise

où surface_utile_requise = sum_i (order_width_i × order_length_i).

Piège

Utiliser sum_j (waste_width_j × x_j) comme objectif ne capture que la perte de coupe — la bande inutilisée dans chaque motif. Il ne pénalise pas la surproduction d'une commande. Le solveur surproduira les commandes étroites pour remplir les motifs efficacement, mais ce matériau excédentaire est toujours du déchet. Utilisez toujours la surface de matériau total comme objectif.

Programmation par objectifs (préemptive / lexicographique)

La programmation par objectifs optimise plusieurs objectifs par ordre de priorité. Implémentez-la comme des résolutions séquentielles — une par niveau de priorité.

Motif de formulation

1. Contraintes dures — limites de capacité, non-négativité, etc. Elles tiennent dans chaque phase.
2. Contraintes d'objectif — pour chaque objectif, introduisez des variables d'écart (d⁻ pour sous-performance, d⁺ pour surperformance) et écrivez une égalité : expression + d⁻ − d⁺ = cible.
3. Résolvez séquentiellement par priorité :
   • Phase 1 : minimiser (ou maximiser) l'écart pertinent pour l'objectif de plus haute priorité.
   • Phase k : fixez tous les écarts de priorité supérieure à leurs valeurs optimales, puis optimisez l'écart de priorité k.

Types de variables en programmation par objectifs

Les variables d'écart (d⁻, d⁺) et les variables de jeu/temps mort sont toujours continues. Cependant, les variables de décision doivent toujours être ENTIÈRES quand elles représentent des quantités discrètes/comptables (unités produites, véhicules, travailleurs, etc.). Ne laissez pas la présence de variables d'écart continues vous faire traiter toutes les variables comme continues — l'intégrité des variables de décision affecte directement la faisabilité et les valeurs d'objectif.

Modèles d'inventaire / achat multi-période

Dans les problèmes d'achat, vente et capacité d'entrepôt sur plusieurs périodes, décidez quelles contraintes de capacité inclure en fonction des hypothèses de timing du problème.

Motif

Pour chaque période t avec bilan d'inventaire stock[t] = stock[t-1] + achat[t] - vente[t] :

• Capacité de fin de période (borne de variable) : stock[t] <= capacité — toujours nécessaire.
• Capacité après achat (contrainte explicite) : stock[t-1] + achat[t] <= capacité — empêche d'acheter plus que l'entrepôt ne peut contenir avant toute vente dans la période.

Quand inclure la contrainte de capacité après achat

• L'inclure quand le problème énonce ou implique que les achats sont reçus avant les ventes dans une période (opérations séquentielles), ou quand l'entrepôt ne peut physiquement pas dépasser la capacité à tout instant.
• L'omettre quand achats et ventes sont concurrents dans une période (courant dans les problèmes de trading/inventaire de manuels) et la capacité s'applique seulement à l'inventaire de fin de période. De nombreux problèmes classiques ne contraignent que l'inventaire de fin de période.

Interaction clé avec la contrainte de vente : Si le modèle a déjà vente[t] <= stock[t-1] (le grain acheté cette période ne peut être vendu cette période), le modèle est borné même sans la contrainte de capacité après achat. La contrainte de vente empêche un cycle achat-vente non borné. La contrainte de capacité après achat est alors une restriction physique supplémentaire, pas une nécessité mathématique.

Par défaut : Si le problème ne spécifie pas le timing dans une période, utilisez uniquement la capacité de fin de période (stock[t] <= capacité). Ajoutez la contrainte de capacité après achat seulement si le problème l'exige explicitement.

Mélange avec mélange partagé / traitement intermédiaire

Dans certains problèmes de mélange, un sous-ensemble de matières premières doit être mélangé d'abord (p. ex., dans un réservoir de mélange) avant d'être alloué à différents produits. L'intermédiaire résultant a une composition uniforme — vous ne pouvez pas assigner indépendamment différentes matières premières à différents produits.

Pourquoi le LP de mélange standard est incorrect ici

Le LP de mélange standard utilise des variables x[i][j] (quantité de matière première i dans le produit j) et alloue librement chaque matière première à chaque produit. Quand les matières premières partagent une étape de mélange, les proportions de ces matières premières doivent être identiques dans chaque produit qui reçoit l'intermédiaire. Cette contrainte de proportionnalité est bilinéaire (x[A,1]*x[B,2] = x[B,1]*x[A,2]) et ne peut pas être directement exprimée en LP.

Stratégies de linéarisation

1. Allocation à un seul produit : Si l'analyse montre que l'intermédiaire est rentable dans un seul produit, allouez tout l'intermédiaire à ce produit (fixez l'allocation d'intermédiaire aux autres produits à zéro). La contrainte de proportionnalité devient triviale. C'est le cas le plus courant — vérifiez la rentabilité d'intermédiaire dans chaque produit avant de tenter une division générale.

2. Paramétrage sur la concentration intermédiaire : Fixez la concentration en soufre/qualité de l'intermédiaire comme un paramètre σ. Pour chaque σ fixe, le problème est un LP standard (l'intermédiaire devient une matière première virtuelle avec propriétés connues). Résolvez pour une grille de valeurs σ ou utilisez la structure pour trouver l'optimum analytiquement.

3. Énumération de scénarios : Quand seulement 2–3 produits existent, énumérez quels produits reçoivent l'intermédiaire (tout-à-A, tout-à-B, division). Pour chaque scénario avec un seul destinataire, le LP est standard. Pour les scénarios de division, utilisez la stratégie 2.

Vérification de rentabilité

Avant de formuler, vérifiez si l'utilisation d'intermédiaire dans chaque produit est rentable :

• Comparez le coût minimum par tonne de l'intermédiaire (en utilisant le mélange de matière première réalisable le moins cher) par rapport au prix de vente de chaque produit.
• Si coût_intermédiaire > prix_vente[j] pour un produit j, l'intermédiaire ne doit pas être alloué au produit j. La matière première C (ou d'autres entrées directes) seule peut aussi être non rentable si coût_C > prix_vente[j].
• Cette analyse élimine souvent complètement le besoin d'une division bilinéaire.