Programmation stochastique à variables mixtes entières — Optimisation sous incertitude avec décisions discrètes et continues
- Introduite par
- Birge, J. R.; Louveaux, F.; Sen, S.
- Année
- 1990s–2000s
- Type
- Stochastic optimization model
- Famille
- Simulation / optimization
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
La programmation stochastique à variables mixtes entières (SMIP) est un cadre d'optimisation qui trouve le meilleur mélange de décisions binaires, entières et continues lorsque les paramètres clés — coûts, demandes, capacités — sont incertains et modélisés comme des distributions de probabilité sur un ensemble de scénarios.
Elle étend la programmation linéaire entière (MIP) classique en intégrant des arbres de scénarios ou des objectifs de valeur espérée qui se prémunissent contre l'incertitude tout en respectant les contraintes combinatoires.
L’intuition derrière la méthode
De nombreux problèmes de planification réels imposent des choix oui/non ou des nombres entiers — construire une installation ou non, affecter un nombre entier de véhicules — alors que l'avenir est incertain. La SMIP formalise cela en considérant une collection de scénarios futurs plausibles et en choisissant des engagements de premier stade (avant que l'incertitude ne soit révélée) qui minimisent le coût attendu ou maximisent le bénéfice attendu sur tous les scénarios. Les contraintes d'intégrité rendent le problème combinatoirement difficile, mais les algorithmes de décomposition exploitent la structure des scénarios pour rendre les grandes instances traitables.
Histoire
La programmation stochastique est née avec Dantzig (1955) et Beale (1955) sous forme de PL à deux stades. L'extension à variables mixtes entières a émergé de manière proéminente dans les années 1990 avec les adaptations de la méthode en L pour le recours entier par Laporte et Louveaux (1993) et le traitement complet dans le manuel de Birge et Louveaux (1997). L'algorithme C3/D2 de Sen et Higle (2005) a fait progresser les solveurs SMIP évolutifs, établissant le domaine comme une discipline mature au sein de la recherche opérationnelle.
Quand l’utiliser
Utiliser la SMIP lorsque les décisions impliquent des choix discrets ou binaires (investir/ne pas investir, nombre d'unités à ouvrir) et que les paramètres d'entrée clés sont réellement incertains avec des distributions de probabilité quantifiables. Idéal pour la conception de réseaux de chaîne d'approvisionnement sous incertitude de demande, l'expansion de la capacité énergétique, la planification des installations de santé et le pré-positionnement pour la réponse aux catastrophes. Ne pas utiliser lorsque toutes les décisions sont continues (utiliser la programmation linéaire stochastique à la place), lorsque l'incertitude ne peut pas être quantifiée de manière significative sous forme de distributions, lorsque le nombre de scénarios requis pour représenter l'incertitude conduit à des tailles de modèle intraitable et que la décomposition n'est pas disponible, ou lorsqu'une heuristique basée sur la simulation suffit pour la qualité de décision requise.
Limites et points d’attention
- La complexité de calcul croît de manière combinatoire avec le nombre de scénarios et de variables entières ; les grandes instances peuvent être intraitable sans décomposition efficace.
- Nécessite des distributions de probabilité explicites ou des ensembles de scénarios — les modèles d'incertitude mal spécifiés conduisent à des solutions qui performent mal hors échantillon.
- Les formulations à deux stades peuvent simplifier à l'excès les décisions multi-périodes ; la SMIP multi-étapes est significativement plus difficile.
- Le recours entier au second stade détruit la convexité exploitée par les coupes de Benders standard, nécessitant des coupes en L entières spécialisées.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Gère les décisions discrètes combinatoires sous incertitude dans un modèle d'optimisation cohérent unique.
- Produit des plans de premier stade protégés qui équilibrent la performance attendue sur tous les scénarios.
- Les métriques VSS et EVPI fournissent une justification transparente de la valeur de la modélisation stochastique.
- Les algorithmes de décomposition (en L, progressive hedging) s'adaptent à de grands ensembles de scénarios.
- Largement pris en charge par les solveurs commerciaux (CPLEX, Gurobi) et les langages de modélisation (AMPL, Pyomo).
Applications
- Conception de réseaux de chaîne d'approvisionnement avec des demandes clients incertaines et des décisions binaires de localisation d'installations.
- Planification de l'expansion de la capacité de production d'électricité sous l'incertitude de la production renouvelable et de la croissance de la demande.
- Allocation des ressources du système de santé (personnel entier, ouvertures de cliniques binaires) sous incertitude épidémiologique.
- Pré-positionnement logistique humanitaire de fournitures de secours discrètes avant des scénarios de catastrophe.
- Optimisation de portefeuille financier avec coûts de transaction et contraintes de taille de lot entière sous incertitude de marché.
- Planification des équipages de compagnies aériennes sous l'incertitude des retards de vol avec variables d'affectation binaires.
Comment ça marche
Comment ça marche
Identifier les variables de décision : décisions de premier stade x prises avant que l'incertitude ne soit révélée (entières et/ou binaires parmi elles), et variables de recours de second stade y(xi) prises après que le scénario xi se matérialise. Spécifier les coefficients de l'objectif, les matrices de contraintes et la distribution de probabilité ou l'ensemble discret de scénarios pour les paramètres incertains.
Construire un ensemble fini de scénarios {xi_1, ..., xi_S} avec des probabilités associées {p_1, ..., p_S} approximant la distribution sous-jacente. Les scénarios peuvent être dérivés de données historiques, d'avis d'experts, d'échantillonnage par hypercube latin ou de méthodes d'ajustement de moments. La qualité des scénarios affecte directement la qualité de la solution.
Formuler l'équivalent déterministe : minimiser c'x + somme_s p_s Q(x, xi_s) sous contrainte des contraintes de premier stade et de l'intégrité. Q(x, xi_s) est la fonction de valeur de second stade — le coût optimal des actions de recours étant donné x et le scénario xi_s. Le programme combiné est un grand MIP dont la taille croît avec le nombre de scénarios.
Formule
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}Résoudre à l'aide d'algorithmes de décomposition — méthode en L (décomposition de Benders) pour les seconds stades convexes, méthode branch-and-cut avec sous-problèmes de scénarios, ou progressive hedging pour la décomposition parallèle par scénarios. L'intégrité au second stade nécessite des coupes supplémentaires (coupes en L entières, lift-and-project). Les solveurs modernes (CPLEX, Gurobi avec callbacks, ou bibliothèques spécifiques à la SMIP) implémentent ces routines.
Évaluer la solution via la Valeur de la Solution Stochastique (VSS = EEV - RP) et la Valeur Attendue de l'Information Parfaite (EVPI = RP - WS), où RP est la valeur optimale du problème de recours, EEV est le coût attendu de l'utilisation de la solution moyenne déterministe, et WS est la valeur de l'attente et de la voir. Ces métriques quantifient le bénéfice de la modélisation explicite de l'incertitude.
Pièges courants
- Utiliser trop peu de scénarios sous-représente l'incertitude, produisant des solutions trop confiantes ; trop de scénarios rendent le modèle informatiquement infaisable.
- Confondre les rôles des variables de premier et de second stade conduit à des formulations qui ne respectent pas le calendrier de révélation de l'information.
- Se fier à la solution de valeur espérée (ignorant la stochasticité) peut être significativement sous-optimal — toujours calculer la VSS pour justifier l'effort de SMIP.
- Négliger l'intégrité au stade du recours lorsqu'elle est réellement présente produit une relaxation dont la solution peut être infaisable en pratique.
- Les paramètres par défaut des solveurs pour MIP nécessitent souvent un réglage (priorités de branchement, stratégies de coupe) dans les cadres de décomposition SMIP.
Questions fréquentes
Quelle est la différence entre la SMIP et la programmation linéaire entière (MIP) classique ?
La MIP classique optimise sous des paramètres fixes et connus. La SMIP modélise explicitement les paramètres incertains comme un ensemble de scénarios avec des probabilités, optimise la performance attendue sur tous les scénarios tout en garantissant que les décisions de premier stade sont prises avant que l'incertitude ne soit révélée.
Combien de scénarios sont nécessaires ?
Il n'y a pas de règle universelle. Aussi peu que 10 à 50 scénarios peuvent suffire pour des décisions de premier stade stables dans certains problèmes ; d'autres en nécessitent des milliers. Les techniques de réduction de scénarios et les tests de stabilité (vérifiant que la solution optimale ne change pas lorsque l'on ajoute plus de scénarios) aident à déterminer l'adéquation.
Qu'est-ce que la méthode en L ?
La méthode en L est une décomposition de Benders adaptée aux programmes stochastiques. Elle résout itérativement un MIP maître sur les variables de premier stade et des sous-problèmes de scénarios, ajoutant des coupes d'optimalité et de faisabilité au maître jusqu'à convergence. Pour le recours entier, des coupes en L entières remplacent les coupes de Benders standard.
Quand faut-il utiliser progressive hedging plutôt que la méthode en L ?
Progressive hedging se décompose par scénario plutôt que par structure de sous-problème, ce qui la rend bien adaptée au calcul parallèle. Elle est préférée lorsque les scénarios sont nombreux et les sous-problèmes importants, et lorsque l'algorithme peut être exécuté sur un cluster. La méthode en L est généralement préférée pour un nombre plus restreint de scénarios bien structurés.
La SMIP peut-elle gérer plus de deux stades ?
Oui, mais la SMIP multi-étapes nécessite un arbre de scénarios qui croît exponentiellement avec le nombre d'étapes, et la décomposition devient considérablement plus complexe. En pratique, la plupart des modèles SMIP appliqués utilisent deux stades, approximant les dynamiques multi-périodes par horizon roulant ou agrégation.
Méthodes associées
Sources
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.
ISBN : 9780387982175Copié.Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.
Ouvrir la référence DOICopié.