Formulation LP/MILP

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

Qu'est-ce que LP / MILP

• LP : objectif linéaire, contraintes linéaires, variables continues.
• MILP : pareil plus quelques variables entières ou binaires (ex. planification, localisation d'installations, sélection).

Questions requises (formulation du problème)

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

1. Variables de décision — Quelles sont-elles ? Bornes ?
2. Objectif — Minimiser ou maximiser ? Expression linéaire en les variables ?
3. Contraintes — Inégalités/égalités linéaires ? Noms et signification ?
4. Types de variables — Toutes continues (LP) ou certaines entières/binaires (MILP) ?

Éléments de modélisation typiques

• Variables continues — quantités de production, flux, etc.
• Variables binaires — ouvert/fermé, oui/non (ex. installation ouverte, article sélectionné).
• Contraintes de liaison — ex. production uniquement si l'installation est ouverte (Big-M ou indicatrice).
• Contraintes de ressources — limitation linéaire d'utilisation (matériaux, temps, capacité).

Analyse du énoncé du problème

Lorsque l'utilisateur fournit du texte de problème, classifiez chaque phrase puis résumez avant de formuler.

Classifiez chaque phrase comme paramètre/donnée, contrainte, décision ou objectif. Guettez les contraintes implicites (ex. phrasing engagé vs optionnel) et les objectifs implicites (ex. « déterminer le plan » + coûts → minimiser le coût total).

Ambiguïté : Si quelque chose reste ambigu, posez la question à l'utilisateur ou résolvez toutes les interprétations plausibles et rapportez tous les résultats ; ne présumez pas une seule interprétation.

🔒 OBLIGATOIRE : En cas de doute — Posez la question

• S'il y a le moindre 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 du chemin complet — Essayez toutes les variantes

• Lorsque l'utilisateur demande d'exécuter le chemin complet (ex. bout en bout, pipeline complet), exécutez toutes les variantes plausibles et rapportez tous les résultats pour que l'utilisateur choisisse ; ne présumez pas une seule interprétation.

Trois étiquettes

Contraintes implicites : phrasing engagé vs optionnel

Phrasing engagé/fixé → traiter comme paramètre ou contrainte implicite (tout ce qui est mentionné est donné ou doit se produire). Pas une décision.

Phrasing optionnel/décision → traiter comme décision.

Objectifs implicites — à ne pas manquer

Si le problème demande de « déterminer le plan » (ou similaire) mais ne stipule pas « minimiser » ou « maximiser » explicitement, 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 : Lorsque le problème fournit 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 (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 présents, précisez si vous utilisez « minimiser le coût » ou « maximiser le profit ». Demandez à l'utilisateur si c'est peu clair.

Workflow d'analyse

1. Divisez le texte du problème en phrases ou clauses logiques.
2. Étiquetez 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 des coûts (et possiblement des revenus), l'objectif est implicite — énoncez-le (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 modaux :
   • « est », « a », « opère », « emploie », « prévoit de » (fixé/engagé) → paramètre ou contrainte implicite.
   • « peut », « peut choisir », « envisage », « décide », « veut » (optionnel) → décision ou objectif.
6. 🔒 OBLIGATOIRE — Si quelque chose est encore ambigu (ex. une valeur ou contrainte pourrait être lue de deux façons) : posez la question à l'utilisateur quelle interprétation est correcte, ou résolvez toutes les interprétations plausibles et rapportez tous les résultats. Ne présumez pas une seule interprétation.
7. Résumez pour l'utilisateur : listez les paramètres, contraintes (explicites + signalées implicites), décisions, et objectif (explicite ou inféré) avant d'écrire la formulation mathématique.

Checklist d'analyse

• [ ] Chaque phrase a une étiquette (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 formulez jamais sans énoncer l'objectif.
• [ ] Phrasing engagé (« prévoit de », « opère », « emploie ») → pas des décisions.
• [ ] Phrasing optionnel (« peut », « peut choisir », « envisage ») → décisions.
• [ ] Les contraintes implicites du phrasing engagé sont écrites (ex. « tous les X doivent être produits »).
• [ ] 🔒 OBLIGATOIRE — Ambiguïté : Toute phrase qui pourrait être lue de deux façons → j'ai posé la question à l'utilisateur ou je vais résoudre toutes les interprétations et rapporter tous les résultats (pas d'interprétation unique silencieuse).
• [ ] Un résumé est produit avant de formuler (paramètres, contraintes, décisions, objectif).

Exemple

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

Résultat : Paramètres = 3 usines, cible de 500 unités. Contraintes = produire exactement 500 (implicite de « prévoit de produire »). Décisions = allocation de 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 des composants de coût (ex. atelier, inspection, vente) mais ne stipule 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. »

Objectifs linéaires par morceaux avec totaux entiers en production

Lors de la modélisation de fonctions de profit/coût linéaires par morceaux concaves (ex. profit marginal décroissant pour les ventes en gros), 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 d'abord les segments à plus haut profit.

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 produisant un objectif différent (supérieur ou inférieur) que le vrai optimum entier.

Schéma

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)

Lien : x_total = s1 + s2 + …
Les contraintes de ressources utilisent x_total.
L'objectif utilise les 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 comprend à 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 uniquement 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 les déchets est équivalent à minimiser la surface totale de matériau consommé :

minimiser  somme_j (largeur_bobine_j × x_j)

où x_j est la longueur dé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 = somme_i (largeur_commande_i × longueur_commande_i).

Piège

Utiliser somme_j (largeur_déchet_j × x_j) comme objectif ne capture que la perte de coupe — la bande inutilisée dans chaque motif. Cela ne pénalise pas la surproduction d'une commande. Le solveur surproduira les commandes étroites pour remplir les motifs efficacement, mais cet excédent de matériau est quand même un déchet. Utilisez toujours la surface totale de matériau comme objectif.

Programmation par objectifs (préemptive / lexicographique)

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

Schéma de formulation

1. Contraintes dures — limites de capacité, non-négativité, etc. Elles s'appliquent à chaque phase.
2. Contraintes d'objectif — pour chaque objectif, introduisez des variables de déviation (d⁻ pour le sous-accomplissement, d⁺ pour le suraccomplissement) et écrivez une égalité : expression + d⁻ − d⁺ = cible.
3. Résolvez séquentiellement par priorité :
   • Phase 1 : minimiser (ou maximiser) la déviation pertinente pour l'objectif de plus haute priorité.
   • Phase k : fixez toutes les déviations de priorité supérieure à leurs valeurs optimales, puis optimisez la déviation de la priorité k.

Types de variables en programmation par objectifs

Les variables de déviation (d⁻, d⁺) et les variables de slack/temps inactif sont toujours continues. Cependant, les variables de décision doivent rester ENTIÈRES lorsqu'elles représentent des quantités discrètes/dénombrables (unités produites, véhicules, travailleurs, etc.). Ne laissez pas la présence de variables de déviation continues vous faire rendre toutes les variables continues — l'intégrité des variables de décision affecte directement la faisabilité et les valeurs d'objectif.

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

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.

Schéma

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

• Capacité en fin de période (borne 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 ce que l'entrepôt peut contenir avant toute vente dans la période.

Quand inclure la contrainte de capacité après achat

• Incluez-la lorsque le problème énonce ou implique que les achats sont reçus avant les ventes dans une période (opérations séquentielles), ou lorsque l'entrepôt ne peut physiquement pas dépasser la capacité à aucun instant.
• Omettez-la lorsque l'achat et la vente sont concurrents dans une période (courant dans les problèmes de trading/inventaire de manuel) et la capacité s'applique uniquement au stock en fin de période. Beaucoup de problèmes classiques ne contraignent que l'inventaire en 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 prévient le 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é en fin de période (stock[t] <= capacité). Ajoutez la contrainte de capacité après achat uniquement si le problème l'exige explicitement.

Mélange avec réservoir de 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 (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 allouer indépendamment différentes matières premières à différents produits.

Pourquoi le LP de mélange standard est erroné 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. Lorsque 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 dans une LP.

Stratégies de linéarisation

1. Allocation mono-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 trivialement satisfaite. C'est le cas le plus courant — vérifiez la rentabilité de l'intermédiaire dans chaque produit avant de tenter un partage général.

2. Paramétrique sur la concentration intermédiaire : Fixez la concentration de soufre/qualité de l'intermédiaire en tant que paramètre σ. Pour chaque σ fixé, le problème est une LP standard (l'intermédiaire devient une matière première virtuelle aux 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 : Lorsque seulement 2–3 produits existent, énumérez quels produits reçoivent l'intermédiaire (tout-à-A, tout-à-B, partage). Pour chaque scénario avec un seul destinataire, la LP est standard. Pour les scénarios de partage, utilisez la stratégie 2.

Vérification de rentabilité

Avant de formuler, vérifiez si l'utilisation de l'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) 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 autres entrées directes) peut aussi être non rentable si coût_C > prix_vente[j].
• Cette analyse élimine souvent la nécessité d'un partage bilinéaire entièrement.