Skip to content
Retour aux résultats

Programmation Linéaire en Nombres Entiers Stochastique — Optimisation des Décisions Discrètes sous Incertitude

Introduite par
Dantzig, G. B.; Beale, E. M. L.
Année
1955
Type
Optimization under uncertainty with discrete decisions
Famille
Simulation / optimization

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La Programmation Linéaire en Nombres Entiers Stochastique (PLNES) est un cadre d'optimisation qui combine des variables de décision entières (discrètes) avec une modélisation probabiliste explicite de l'incertitude.

Elle recherche la meilleure décision prise ici et maintenant qui minimise le coût attendu (ou maximise le bénéfice attendu) sur une distribution de scénarios futurs, en tenant compte du fait que certaines décisions doivent être prises avant que l'incertitude ne soit résolue.

L’intuition derrière la méthode

De nombreuses décisions réelles sont à la fois discrètes (construire une installation ou non ; affecter un travailleur ou non) et incertaines (la demande, les coûts et les contraintes ne sont pas connus au moment de la décision). La PLNES gère ces deux défis simultanément. Elle modélise le futur incertain comme un ensemble de scénarios avec des probabilités associées, puis trouve la solution entière qui performe le mieux en moyenne — ou qui se protège contre les résultats les plus défavorables. Contrairement à la programmation linéaire stochastique, la structure discrète rend le problème combinatoirement plus difficile, mais les décisions produites sont directement implémentables sans arrondi ni approximation.

Histoire

La programmation stochastique remonte à Dantzig (1955) et Beale (1955), qui ont indépendamment proposé des modèles de recours à deux étapes pour les programmes linéaires sous incertitude. L'extension entière a émergé avec la maturation de la programmation entière dans les années 1960-1980. Le manuel de Birge et Louveaux (1997) a codifié le domaine, et Kleywegt et al. (2002) ont établi l'Approximation par la Moyenne des Échantillons comme l'approche computationnelle standard pour l'optimisation discrète stochastique à grande échelle.

Quand l’utiliser

Utiliser la Programmation Linéaire en Nombres Entiers Stochastique lorsque les décisions sont intrinsèquement discrètes (choix binaires, affectations d'unités entières, affectations de routage) et que les paramètres clés sont incertains au moment de la décision. Elle est bien adaptée à la planification de capacité, à la conception de réseaux de chaîne d'approvisionnement, à la planification sous incertitude de demande, à la gestion de l'énergie, et à l'allocation de ressources avec des rendements aléatoires. NE PAS l'utiliser lorsque toutes les variables sont continues (la programmation linéaire stochastique suffit), lorsque l'incertitude est négligeable ou entièrement observable avant la décision, lorsque l'échelle du problème rend l'énumération des scénarios calculatoirement intraitable sans infrastructure de décomposition, ou lorsqu'un seul scénario déterministe est pertinent.

Limites et points d’attention

  • La complexité de calcul augmente rapidement avec le nombre de scénarios et de variables entières ; les instances de grande taille sont NP-difficiles.
  • La génération de scénarios nécessite des distributions de probabilité crédibles, qui peuvent être difficiles à obtenir ou à estimer à partir de données limitées.
  • Les extensions multi-étapes (plus de deux étapes) font face à une croissance exponentielle des arbres de scénarios et sont rarement traitables au-delà de trois étapes.
  • Des compétences en modélisation sont nécessaires pour spécifier correctement la faisabilité du recours, les contraintes de non-anticipation et les structures de pénalité.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Modélise explicitement l'incertitude plutôt que d'utiliser des estimations ponctuelles, produisant des solutions robustes aux scénarios réalisés.
  • Gère nativement les décisions discrètes et binaires, de sorte que les solutions sont directement implémentables sans arrondi post-hoc.
  • Le cadre à deux étapes sépare clairement les décisions stratégiques de premier étage des actions de recours opérationnelles de deuxième étape.
  • Prend en charge des structures de recours riches, y compris l'approvisionnement en ressources, les coûts de pénalité et la planification corrective.
  • Les bornes de qualité statistiques (via SAA) permettent aux praticiens de certifier la quasi-optimalité avec une confiance quantifiée.

Applications

  • Conception de réseaux de chaîne d'approvisionnement sous demande et délais stochastiques
  • Planification de l'expansion de la production d'électricité avec une production renouvelable incertaine
  • Planification des salles d'opération hospitalières sous des durées de procédure variables
  • Planification des équipages de compagnies aériennes avec des retards de vol stochastiques
  • Pré-positionnement logistique humanitaire de fournitures de secours avant les catastrophes
  • Optimisation de portefeuille financier avec sélection discrète d'actifs et rendements basés sur des scénarios

Comment ça marche

Comment ça marche

1

Formuler le problème de premier étage : choisir des variables de décision entières (ou mixtes) x avant que l'incertitude ne soit révélée. Définir un objectif qui inclut à la fois le coût immédiat et le coût de recours attendu sur tous les scénarios. Les contraintes liant x aux conditions de faisabilité sont spécifiées ici.

Formule
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]
2

Représenter l'incertitude par un ensemble fini de scénarios. Chaque scénario attribue des valeurs spécifiques aux paramètres aléatoires (niveaux de demande, coûts, disponibilité des ressources). Les scénarios peuvent être générés par échantillonnage historique, tirages de Monte-Carlo à partir de distributions ajustées, ou cas représentatifs définis par des experts. Chaque scénario porte un poids de probabilité dont la somme est égale à un.

3

Dans la formulation standard à deux étapes, après que x est fixé et que le scénario xi est réalisé, un problème de recours (deuxième étape) détermine les actions correctives y. Le problème de recours est souvent un programme linéaire ou entier. Le modèle complet minimise c^T x plus le coût de recours attendu E[Q(x, xi)].

Formule
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)x
4

Résoudre les sous-problèmes de scénarios pour évaluer le coût de recours pour chaque scénario étant donné x. Les techniques incluent la méthode de branche et borne, la décomposition de Benders, la relaxation Lagrangienne et la méthode d'approximation par la moyenne des échantillons (SAA). Pour les grands arbres de scénarios, les algorithmes de décomposition exploitent la structure par blocs à travers les scénarios.

5

Agréger les résultats des sous-problèmes pour estimer le coût de recours attendu. En SAA, il s'agit de la moyenne sur S scénarios échantillonnés. L'approximation résultante converge vers l'espérance réelle lorsque S augmente. Des bornes statistiques sur la qualité de la solution peuvent être calculées à partir de la variance de l'échantillon.

Formule
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)
6

Vérifier l'optimalité ou la quasi-optimalité via les écarts d'optimalité, les critères de convergence, ou les intervalles de confiance statistiques de la SAA. Si l'écart n'est pas acceptable, affiner l'ensemble des scénarios, augmenter la taille de l'échantillon, ou resserrer les relaxations. Rapporter la solution de premier étage x* et son coût total attendu.

Pièges courants

  • Utiliser trop peu de scénarios produit des solutions trop confiantes ; en utiliser trop rend le problème calculatoirement infaisable — trouver un équilibre via les diagnostics de convergence SAA.
  • Ignorer l'intégralité dans la deuxième étape alors qu'elle est réellement requise conduit à des estimations de coûts optimistes et à des actions de recours infaisables.
  • Supposer l'indépendance des scénarios lorsque les paramètres sont corrélés (par exemple, demande et prix corrélés) introduit un biais systématique dans l'estimation du coût attendu.
  • Oublier les contraintes de non-anticipation dans les problèmes multi-étapes permet au modèle d'exploiter des informations futures qui ne seraient pas disponibles en pratique.

Questions fréquentes

En quoi la Programmation Linéaire en Nombres Entiers Stochastique diffère-t-elle de l'optimisation robuste ?

La PLNES minimise le coût attendu sur un ensemble de scénarios pondérés par probabilité, acceptant que certains scénarios puissent entraîner des coûts élevés s'ils sont peu probables. L'optimisation robuste minimise le coût du pire cas sur un ensemble d'incertitude, sans faire d'hypothèses probabilistes. La PLNES nécessite une distribution de probabilité ; l'optimisation robuste ne nécessite qu'un ensemble d'incertitude. La PLNES est généralement moins conservatrice mais plus gourmande en données.

Combien de scénarios sont nécessaires en pratique ?

Cela dépend de la dimension du problème et de la précision souhaitée. L'approche d'Approximation par la Moyenne des Échantillons (SAA) fournit des intervalles de confiance statistiques sur l'écart d'optimalité. Les études appliquées typiques utilisent des dizaines à des milliers de scénarios ; les diagnostics de convergence (variance de l'estimateur de la borne) guident le choix. Pour les problèmes structurés, les techniques de réduction de scénarios (par exemple, Heitsch-Romisch) peuvent réduire considérablement le nombre de scénarios.

La Programmation Linéaire en Nombres Entiers Stochastique peut-elle gérer plus de deux étapes ?

Oui, mais la PLNES multi-étapes est significativement plus difficile. L'arbre de scénarios croît exponentiellement avec le nombre d'étapes, et les contraintes de non-anticipation doivent être appliquées à chaque nœud. En pratique, les modèles à trois étapes sont la norme pour les applications traitables ; au-delà, des approximations telles que l'horizon glissant ou la réduction de l'arbre de scénarios sont généralement nécessaires.

Quels logiciels peuvent résoudre des modèles de Programmation Linéaire en Nombres Entiers Stochastique ?

Les solveurs courants incluent CPLEX et Gurobi (via des langages de modélisation algébrique tels que AMPL, JuMP en Julia, ou PuLP/Pyomo en Python), qui prennent en charge la décomposition par scénarios. Les cadres spécialisés de programmation stochastique incluent PySP (Python), les solveurs au format SMPS, et le package Julia StochasticPrograms.jl, qui implémente SAA et le 'progressive hedging'.

La Programmation Linéaire en Nombres Entiers Stochastique est-elle identique à la Programmation Mixte en Nombres Entiers Stochastique ?

La Programmation Linéaire en Nombres Entiers Stochastique est la classe la plus large ; la Programmation Mixte en Nombres Entiers Stochastique (PMNES) fait spécifiquement référence aux modèles où certaines variables sont continues et d'autres sont entières dans une ou deux étapes. La PMNES est la forme la plus générale et la plus fréquemment rencontrée en pratique.

Méthodes associées

Sources

  1. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN : 978-1-4614-0237-4
    Copié.
  2. Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.

    Ouvrir la référence DOI
    Copié.