Décisions séquentielles dans l'incertain : nouvelles approches par

Decisions sequentielles dans l’incertain :nouvelles approches par la programmation

stochastique et applications

These presentee a la Faculte des sciences economiques et socialesde l’Universite de Geneve par

Julien Theniepour l’obtention du grade de

Docteur es sciences economiques et socialesmention gestion d’entreprise

Membres du jury de these :M. Jean-Paul DE BLASIS, Universite de Geneve, president du jury,M. Manfred GILLI, Universite de Geneve,M. Alain HAURIE, Universite de Geneve,M. Christian VAN DELFT, HEC Paris,M. Jean-Philippe VIAL, Universite de Geneve, directeur de these,Mme. Maria-Pia VICTORIA-FESER, Universite de Geneve.

These no 674Geneve, 2008

3

La faculte des sciences economiques et sociales, sur preavis du jury, a auto-rise l’impression de la presente these, sans entendre, par la, emettre aucuneopinion sur les propositions qui s’y trouvent enoncees et qui n’engagent quela responsabilite de leur auteur.

Geneve, le 19 Septembre 2008

Le doyenBernard MORARD

Impression d’apres le manuscrit de l’auteur

Preface

Je voudrais commencer par remercier toutes les personnes m’ayant faitdecouvrir le monde de la recherche operationnelle. Tout d’abord les profes-seurs de l’Institut des Mathematiques Appliquees d’Angers (France) ou j’aifait mon DESS, et notamment le Prof. Eric Pinson. Ensuite mes collegues del’entreprise Optilogistic avec lesquels j’ai appris a utiliser les mathematiquesappliquees pour repondre aux besoins concrets d’entreprises. Enfin, tous lesmembres du Logilab que j’ai pu rencontrer, et avec lesquels le travail etla recherche ont toujours ete faits dans la bonne humeur. Merci a Jean-Philippe Vial pour sa proposition de these, et pour son accompagnementtout au long de ses cinq annees. Merci aux membres du jury d’avoir ac-cepte d’evaluer mon travail. Je finis par remercier mes proches pour leurcomprehension, ma famille pour son soutien continu. Merci enfin a Carolineet Jeanne d’avoir bien voulu partager cette aventure avec moi.

i

Resume

La presente these propose une methode heuristique pour des problemesd’optimisation convexe sous incertitude a variables d’etat non-contraintes :la programmation stochastique avec regles de decision constantes par mor-ceaux, dont l’abreviation anglaise est SPSDR. Cette methode est baseesur l’adaptation du concept de regles de decision a la programmation sto-chastique standard. L’utilisation de regles de decision constantes par mor-ceaux permet de formuler un probleme sans pour autant posseder un arbred’evenements. L’interet principal de cette approche est qu’elle permet lecontournement du fleau de la dimension. Afin d’ameliorer les performancesde la methode, il est propose de travailler en utilisant le concept d’avisd’experts, qui permet, en plus de paralleliser la resolution, d’ameliorer lasolution finale, c’est du moins ce qui a pu etre observe sur les exemples quenous traitons. Cette methode heuristique est proposee comme une contribu-tion methodologique a la mise en œuvre de la programmation stochastiquesur des problemes comptant de nombreuses etapes.

Cette technique est appliquee sur un probleme de gestion de chaınesd’approvisionnement a 12 etapes. Des methodes de programmation sto-chastique standard et de programmation robuste ont ete developpees afinde comparer, grace a une validation a posteriori sur un large ensemble descenarios, les performances de notre heuristique.

De plus, un outil informatique libre nomme DET2STO est propose. Ilpermet, sur base de problemes formules grace a un langage de modelisationalgebrique qu’est GMPL, de formuler automatiquement la version stochas-tique d’un probleme deterministe. Cet outil est integre a un site appeleAML4SP qui permet la resolution et la transformation en ligne des pro-blemes d’un internaute, et ce, uniquement avec des outils libres. Ces deuxapplications sont proposees comme une contribution technologique a la miseen œuvre de la programmation stochastique.

Enfin, une amelioration de la methode heuristique est proposee dans lecadre d’une utilisation de la mesure de defaillance dans la fonction objectif.

iii

Abstract

This thesis proposes a heuristic method to approximate multistage sto-chastic convex optimization problem with unconstrained state variables.This is called the stochastic programming with step decision rules method(SPSDR). This method is based on the concept of decision rule being adap-ted to the standard stochastic programming method. The use of step de-cision rules allows the formulation of an optimisation problem without thesupport of an event tree. The main advantage being an approach to over-come the curse of dimensionality. To involve performances we adapt theexpert advice method. The resulting formulation is well suited to parallelcomputations. The expert advice method formulation involves the perfor-mance of the method on the studied numerical examples. This heuristicapproach is proposed as a methodological contribution to the use of themassive multistage stochastic programming method.

SPSDR is applied on a 12-stages supply chain optimization problem.Plain stochastic programming and robust optimization methods have beendeveloped to be able to evaluate performances of the approach. A validationphase is used to determine posteriori knowledge on a large set of scenarios.

Then, the DET2STO software is used, which is permitted to automati-cally generate the stochastic version of a deterministic problem and formu-late with the GMPL algebraic modeling language. This tool is integratedinto a website that permits the user to solve and transform their own pro-blems online, using only free softwares. The two applications are proposedas a technological contribution to the use of stochastic programming.

The SPSDR approach is involved in cases of a risk measure objectivefunctions.

v

Contexte de la recherche

J’ai realise ma these de Mai 2003 a Avril 2008 a l’Universite de Geneve,au sein de la section HEC. J’etais en charge d’assister le Prof. Vial pour sescours de gestion des operations aux niveaux bachelor et master en gestiond’entreprise.

Durant ces cinq annees, nous avons ecrit deux articles :– [85] : J. Thenie, Ch. van Delft et J.-Ph. Vial, Automatic formulation

of stochastic programs via an algebraic modeling language, Compu-tational Management Science, 4, 17-40, 2007.

– [87] : J. Thenie et J.-Ph. Vial, Step decision rules for multistage sto-chastic programming : a heuristic approach, Automatica, 44 : 6, 1569-1584, 2008.

Au cours de la preparation de ces articles, nous avons presente nos tra-vaux a differentes conferences :

– J. Thenie, J.-Ph. Vial, Une approche heuristique pour les problemesstochastiques multi-etapes : programmation stochastique avec reglesde decision constantes par morceaux, Presentation departement R&DEDF, Paris, France, 17 Avril 2007.

– J. Thenie, J.-Ph. Vial, Une approche heuristique pour les problemesstochastiques multi-etapes : programmation stochastique avec reglesde decision constantes par morceaux, Conference conjointe FRAN-CORO V / ROADEF 2007, Grenoble, France, 20-23 Fevrier 2007.

– J. Thenie, J.-Ph. Vial, Stochastic programming with step decisionrules : a heuristic approach, 4th Joint Operations Research Days,EPFL, Lausanne, Suisse, 14-15 Septembre 2006.

– J. Thenie, J.-Ph. Vial, Programmation stochastique avec regles dedecision lineaires, ROADEF’05, Tours, France, 14-16 Fevrier 2005.

– J. Thenie, J.-Ph. Vial, Stochastic Programming with linear DecisionRules, an application to the evaluation of option contracts, 10th Inter-national Conference on Stochastic Programming, Tucson, AZ, USA,9-15 Octobre 2004.

– J. Thenie, J.-Ph. Vial, Stochastic Programming with linear Decision

vii

viii

Rules, an application to the evaluation of option contracts, FRAN-CORO IV, Fribourg, Suisse, 19-21 Aout 2004.

– J. Thenie, J.-Ph. Vial, Stochastic Programming with linear DecisionRules, ICCOPT I, Rensselaer Polytechnic Institute, Troy, U.S.A., 2-4Aout 2004.

– J. Thenie, J.-Ph. Vial, Stochastic Programming with linear DecisionRules, Computational Management Science Conference, Neuchatel,Suisse, 2-4 Avril 2004.

Apres mes etudes a l’institut des mathematiques appliquees (IMA, An-gers, France) ou j’ai obtenu un DESS M.A.I. et le diplome de l’IMA (ni-veau I), j’ai travaille deux ans au sein de l’entreprise Optilogistic (Lesponts-de-Ce, France) ou j’occupais le poste d’ingenieur developpement audepartement optimisation. J’etais aussi en charge du suivi de deux clients.Durant cette periode, j’ai notamment travaille avec le conseiller scientifiquede l’entreprise, le Prof. Eric Pinson, qui etait mon professeur de rechercheoperationnelle a l’IMA. Avec lui, j’ai travaille sur des projets de plus enplus techniques, eveillant mes interets pour la recherche.

Table des matieres

I Introduction 1

1 Gestion industrielle et Logistique 51.1 Un bref historique . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Les concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Gestion locale . . . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Gestion globale . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Etat de l’art 172.1 Les modeles . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2 Les methodes . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3 Les outils . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3 Contributions 233.1 Contribution technologique . . . . . . . . . . . . . . . . . . . 233.2 Contribution methodologique . . . . . . . . . . . . . . . . . 23

4 Organisation de la these 25

II Optimisation multi-etapes dans l’incertain 27

5 Une classe de problemes d’optimisation 315.1 Probleme deterministe . . . . . . . . . . . . . . . . . . . . . 315.2 Notations des donnees incertaines . . . . . . . . . . . . . . . 335.3 Probleme stochastique . . . . . . . . . . . . . . . . . . . . . 34

6 L’approche par la programmation stochastique 396.1 Deux etapes . . . . . . . . . . . . . . . . . . . . . . . . . . . 406.2 Plus de 2 etapes . . . . . . . . . . . . . . . . . . . . . . . . . 436.3 Generation d’un arbre d’evenements pour processus multi-

etapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466.4 Application de la politique de decision . . . . . . . . . . . . 55

ix

x Table des matieres

7 Les obstacles a la mise en œuvre 577.1 Une difficulte technologique . . . . . . . . . . . . . . . . . . 587.2 Une difficulte methodologique . . . . . . . . . . . . . . . . . 58

III Contribution a la mise en œuvre de la program-mation stochastique grace a DET2STO 61

8 Introduction 63

9 Automatic formulation of SP programs via an AML 679.1 Stochastic programming formulation . . . . . . . . . . . . . 709.2 The event tree formulation . . . . . . . . . . . . . . . . . . . 729.3 An illustrative example . . . . . . . . . . . . . . . . . . . . . 749.4 Primitives on the event tree . . . . . . . . . . . . . . . . . . 789.5 Automatic generation of the deterministic equivalent in ampl 879.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

IV Programmation stochastique avec regle de de-cision 95

10 La programmation stochastique avec regle de decisionconstante par morceaux 9910.1 Un probleme multi-etapes sur un peigne . . . . . . . . . . . 10010.2 Un processus decisionnel a memoire imparfaite . . . . . . . . 10310.3 Combinaison de regles de decision . . . . . . . . . . . . . . . 107

11 Procedure d’amelioration avec un objectif CVaR 11111.1 Prise en compte du risque . . . . . . . . . . . . . . . . . . . 11111.2 Creation de nouveaux ensembles Se : type 1 . . . . . . . . . 11511.3 Creation de nouveaux ensembles Se : type 2 . . . . . . . . . 116

V Etude empirique 117

12 Le probleme de contrat d’approvisionnement 11912.1 Le modele RSFC . . . . . . . . . . . . . . . . . . . . . . . . 11912.2 Methodes developpees . . . . . . . . . . . . . . . . . . . . . 12212.3 CVaR applique au modele RSFC . . . . . . . . . . . . . . . 131

13 Les resultats numeriques 133

Table des matieres xi

13.1 Ensemble de calcul de 2000 scenarios . . . . . . . . . . . . . 13413.2 Ensemble de calcul de 5000 scenarios . . . . . . . . . . . . . 13913.3 Les decisions de premiere periode . . . . . . . . . . . . . . . 14213.4 Les politiques de recours . . . . . . . . . . . . . . . . . . . . 14513.5 Gestion du risque avec SPSDR . . . . . . . . . . . . . . . . . 14613.6 Temps de calcul . . . . . . . . . . . . . . . . . . . . . . . . . 147

VI Conclusion 149

14 Synthese 151

15 Perspectives 153

Annexes 157

A Le programme DET2STO 159

B Illustrations de l’outil interactif en ligne AML4SP 175

Liste des figures 183

Liste des tableaux 185

Bibliographie 187

Partie I

Introduction

1

Introduction

La gestion des operations est un des pans de la gestion qui s’interesseaux problemes industriels faisant appel notamment a des techniques quanti-tatives pour etre resolus. Nous introduisons ces concepts dans la presentepartie, qui se veut introductive, generaliste.

Dans le premier chapitre, apres un bref historique de la logistique, nousparlons de la gestion des chaınes d’approvisionnement, sous ensemble de lagestion des operations, et plus particulierement de la problematique d’ap-provisionnement entre un client et son fournisseur. Puis nous introduisonsdifferents modeles permettant de prendre en compte les problematiques dufournisseur dans le probleme de gestion du client grace a l’ajout de ce quel’on nomme les contrats d’approvisionnement. Dans le second chapitre, nousfaisons un etat de l’art des modeles concernant les problemes d’optimisa-tion sous incertitude incluant des contrats d’approvisionnement, puis desmethodes et outils permettant de les resoudre. Dans le troisieme chapitre,nous presentons les contributions a la mise en place de la programmationstochastique de la presente these. Enfin, dans le quatrieme chapitre, nousdecrivons brievement l’organisation de la suite de la these.

3

Chapitre 1

Gestion industrielle etLogistique

Sommaire1.1 Un bref historique . . . . . . . . . . . . . . . . . . . . . 5

La logistique militaire . . . . . . . . . . . . . . . . . . . 5La logistique d’entreprise . . . . . . . . . . . . . . . . . 6La logistique etendue : la chaıne d’approvisionnement . 7

1.2 Les concepts . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Gestion locale . . . . . . . . . . . . . . . . . . . . . . . 9

Arbitrage sur les couts . . . . . . . . . . . . . . . . . . 9Le probleme du marchand de journaux . . . . . . . . . 10

1.4 Gestion globale . . . . . . . . . . . . . . . . . . . . . . . 11L’effet Forrester . . . . . . . . . . . . . . . . . . . . . . 12Les causes . . . . . . . . . . . . . . . . . . . . . . . . . 12Des propositions . . . . . . . . . . . . . . . . . . . . . . 14L’information reduit la variabilite . . . . . . . . . . . . 15

1.1 Un bref historique

La logistique militaire

La logistique trouve son origine dans les armees, bien avant d’apparaıtredans l’industrie. Des le VIeme siecle avant J.C., le general chinois Sun Zi dansL’art de la guerre [98], considere comme l’ouvrage de strategie militaire leplus ancien connu, explique qu’ une armee sans chariots d’approvisionne-ment, ni cereales, ni provisions, est perdue. Une armee en campagne est

5

1. Gestion industrielle et Logistique

en mouvement, elle a besoin de se loger, de se nourrir, et de la presencede nombreux corps de metiers militaires. La reussite d’une campagne peutresider dans sa bonne organisation logistique. Et inversement, une mauvaiseorganisation logistique peut etre a l’origine d’un echec.

Selon les auteurs de [8], la logistique est d’abord presentee comme lapartie de l’art militaire qui groupe les activites coherentes permettant auxarmees en campagne de vivre, se deplacer et combattre dans les meilleuresconditions d’efficacite. La logistique militaire connaıt son avenement lorsde la seconde guerre mondiale aidee par la recherche operationnelle nais-sante. Le deplacement de nombreuses troupes nord-americaines sur le solbritannique, et la preparation du debarquement ne pouvaient souffrir d’unemauvaise organisation logistique :

Sans le travail magnifique effectue par le personnel des services de l’arriere,en resolvant le difficile probleme d’acheminement de l’approvisionnement,la victoire foudroyante qui libera la France n’aurait pas ete possible.

General D. Eisenhower.

La logistique militaire regroupe les problemes de transport, de mise adisposition de biens, d’implantations de depots, mais aussi d’ameliorationde la circulation de l’information...

Apres la seconde guerre mondiale, il faut reconstruire et relancer l’eco-nomie. La logistique militaire devient civile, puis industrielle.

La logistique d’entreprise

Au milieu du vingtieme siecle, la logistique devient le domaine concernepar tous les problemes relatifs au ravitaillement de toutes natures, a leuracheminement ainsi qu’a leur distribution par l’intermediaire de bases detransit et d’operations selon les auteurs de [8]. La logistique se dessine, maiselle n’est pas encore centrale, elle est subie.

Dans les annees 70, Heskell isole la logistique comme un domaine a partentiere de la gestion, et dans [46] lui donne la definition suivante :

Definition 1. La logistique est l’ensemble des activites qui participe a lamaitrise des flux physiques de produits, a la coordination des ressources etdes debouches, en realisant un niveau de service donne, au moindre cout.

Dans les annees 80, Porter, dans ses travaux sur la chaıne de valeur[66], place la logistique au cœur de la strategie d’entreprise. Il identifie lalogistique comme un avantage concurrentiel possible pour les entreprises.

6

Un bref historique

Fig. 1.1: La chaıne de valeur de Porter

La figure 1.1 propose une illustration de la chaıne de valeur. Le produitde l’entreprise passe par cinq activites cles qui lui apporte une plus-value, etnotamment l’approvisionnement (inbound logistics) et la distribution (out-bound logistics).

La logistique s’interesse au choix d’implantation des usines, des en-trepots, a la facon d’organiser le transport entre ces lieux, au stockage desproduits intermediaires et finaux, a la politique de gestion de stock, a lapolitique de production, etc.

La logistique etendue : la chaıne d’approvisionnement

L’idee est ensuite etendue a l’ensemble des acteurs de la chaıne logis-tique : du fournisseur de la matiere premiere jusqu’au client final. C’est cequ’on appelle la chaıne d’approvisionnement. Le Council of Supply ChainManagement Professionals, qui a remplace le Council of Logistic Mana-gement en 2004, donne la definition suivante de la gestion de la chaıned’approvisionnement :

Definition 2. La gestion de la chaıne d’approvisionnement regroupe la pla-nification et la gestion de toutes les activites impliquees dans l’approvision-nement, la fourniture, la conversion, et la logistique de biens. Elle inclutegalement la coordination et la collaboration des associes de la chaıne : lesfournisseurs, les intermediaires, les prestataires de service, et les clients.La gestion de chaıne d’approvisionnements integre la gestion de l’offre etde la demande au sein des entreprises, et entre elles.

7


La logistique s’interesse aux flux de matiere au sein d’une unique entre-prise alors que la chaıne d’approvisionnement s’interesse aux flux de matiereet d’information entre les acteurs successifs de la chaıne. C’est une visionglobale de la logistique. Voila pourquoi nous l’appelons aussi la logistiqueetendue, ou encore logistique globale.

1.2 Les concepts

Nous introduisons ici les concepts principaux de la gestion de la chaıned’approvisionnement. Nous nous limitons au secteur industriel (productionde biens).

– La chaıne logistique est une succession d’agents ou acteurs dont latrame centrale peut etre representee comme en figure 1.2.

Fournisseur

F

Producteur

P

Client

C

Fig. 1.2: Une partie de la chaıne logistique

Bien sur, une chaıne logistique peut etre beaucoup plus etendue, lefournisseur F pouvant avoir lui-meme des fournisseurs, et le client Cpouvant avoir lui meme des clients. La notion de client et fournisseurest donc relative a tout acteur de la chaıne.

– Les acteurs echangent entre eux des flux de 3 types [89] : des fluxd’information, de matiere (produits) et financier. La figure 1.3 preciseles types de flux echanges entre les acteurs de la chaıne logistique.

Fournisseur

F

Producteur

P

Client

C

F

P

C

Information

produit

Information

produit

Fournisseur

F

Producteur

P

Client

C

flux d’information, flux de matière

flux d’information, flux financier

Fig. 1.3: Les differents types de flux au sein de la chaıne logistique

– L’echange de produits resulte d’une demande finale exprimee ici parla demande du client C. Pour fournir cette demande, le producteur Pcree une autre demande en produits (intermediaires) que le fournisseurF devra satisfaire.

8

Gestion locale

– La demande exprimee par P n’est pas identique a celle qu’il recoitde C etant donne qu’il opere une transformation de produits sur basede composants fournis par F. De plus, P peut posseder des stocksde produits finaux et de composants. Le producteur P fournit desproduits a C. Il consomme des composants dont il devra assurer lereapprovisionnement, en passant des commandes a F, en fonction del’evolution de ses stocks.

– Les delais de livraison d’une demande de la part de C (resp. de lapart de P) n’etant pas nuls, le producteur P (le fournisseur F) doitanticiper la demande de C (de P) afin de ne pas etre en rupture destock.

– Faire face a une demande de son client alors que nous sommes en rup-ture de stock a un cout. Ce cout represente la perte d’une vente, ou leprix d’une livraison en retard. Le cout de rupture de stock est propor-tionnel au nombre d’unites non livrees a temps. Le stock aussi a sonpropre cout : le cout de stockage est proportionnel au nombre d’unitesde produits stockees. Enfin, passer une commande a un fournisseur aun cout fixe par commande : le cout de passation de commande.

On peut entrevoir la problematique centrale de gestion locale de stockqui consiste a faire un arbitrage entre trop de stock (augmentation descouts de stockage) et trop peu (augmentation des couts de passation decommande, des couts de rupture). Ce probleme classique a fait l’objet denombreuses publications depuis la theorie de la commande optimale [97] ins-piree de [42]. Ce probleme est simple pour une demande connue et constante.

1.3 Gestion locale

Dans cette section, nous nous interessons a la gestion de stock dans unevision de la logistique locale, c’est a dire a la problematique de gestion destock du producteur faisant face a une demande de son unique client. Laquestion centrale est : comment s’approvisionner aupres de son fournisseurd’une maniere optimale1 ?

Arbitrage sur les couts

Historiquement, les premieres etudes portent sur des problemes de ges-tion statique ou la demande est connue, et constante. On peut retrouverces caracteristiques dans des systemes de production de masse par exemple.Supposons que les couts de stockage h, de passation de commande k et

1a moindre cout

9


d’achat d’une unite p soient connus, ainsi que la demande annuelle D. Notreobjectif est de trouver une taille de lot q (nombre d’unites commandees)de telle sorte que le cout resultant soit minimum. Nous ne considerons pasles couts de rupture puisque la solution optimale proposee ci-apres est unesolution qui permet de repondre a la demande a tout moment.

Soit la fonction de cout total annuel :

CT(q) =qh

2+kD

q(1.1)

Le minimum de cette fonction convexe est trouve grace a la condition dupremier ordre :

CT′(q) = 0 (1.2a)

h

2− kD

q2= 0 (1.2b)

q∗ =

√2kD

h(1.2c)

On appelle cette formule la formule de Wilson [42, 97]. On parle aussi deEOQ2 ou taille de lot economique. Sur cette base, de nombreuses extensionsont ete proposees comme notamment celles gerant des demandes aleatoires,des temps de livraisons aleatoires, etc. Cette formule est l’une des premieresde la theorie relative a la gestion de stock comme le remarquent les auteursde [81].

La suite naturelle de l’etude des problemes statiques de gestion de stockest l’etude des problemes dynamiques. Cette classe de problemes regroupedes versions canoniques d’un probleme central, simple, qui a fait l’objet denombreuses publications : il s’agit du probleme de marchand de journaux.

Le probleme du marchand de journaux

Le probleme du marchand de journaux3 est lui aussi un pilier de latheorie sur la gestion de stock. Le probleme concerne un vendeur de jour-naux qui fait face a une demande incertaine. Il achete ces journaux audebut de journee, et doit les ecouler au court de celle-ci. Dans sa version laplus simple, il ne peut recommander de journaux en milieu de journee. Unjournal est achete au prix de c et est vendu p > c. Il doit commander unequantite q, et fait face a une demande D. Si la demande est plus grande que

2pour economic order quantity3En anglais, on parle de newsboy problem ou de newsvendor problem.

10

Gestion globale

q, il ne vend que q unites, si la demande est plus faible, il peut revendre lesjournaux non ecoules (soit q−D > 0) a un prix s < c pouvant correspondrea la valeur intrinseque du papier.

Le probleme central, avec une quantite a commander q ≥ 0, est definicomme suit :

min CT(q) = cq − E[pmin(q,D) + smax(0, D − q)] (1.3)

De nombreuses techniques ont ete proposees. Historiquement, on s’inte-resse d’abord aux methodes de recompletement4, comme dans [76], consis-tant a definir un couple (S, s). Lorsque le stock descend en dessous du seuils, on fait une commande de S− q unites pour revenir au niveau de stock S.On utilise alors la programmation dynamique comme methode d’optimisa-tion. Par la suite les modeles etudies devenant de plus en plus complexes,d’autres solutions que les politiques (S, s) sont recherchees, et notammentgrace a d’autres techniques d’optimisation que la programmation dyna-mique, comme la programmation stochastique, la programmation robuste,etc.

Il existe bien sur des extensions au modele du marchand de journauxavec des produits non perissables, plusieurs produits, la possibilite de com-mander une seconde fois, voire plusieurs fois, une gestion sur plusieursperiodes temporelles avec report des stocks ou non, la possibilite d’avoirplusieurs clients, plusieurs politiques de prix, des rabais, etc. La litteraturesur le sujet est telle que Veinott dans [92] faisant une revue de la litteraturesur les techniques de gestion de stock proposant des politiques optimales ades problemes dynamiques liste pres de 120 articles des le milieu des annees1960.

Dans la suite de la these, nous allons nous interesser aux problemescomportant plusieurs etapes, gerant un unique produit, avec report de stock,et dont la demande est aleatoire. C’est alors que nous entrerons plus endetail dans la formulation.

Une solution au probleme (1.3) est optimale du point de vue de l’agentqui nous interesse. Mais qu’en est-il d’un point de vue plus global ?

1.4 Gestion globale

L’approche globale consiste a regarder la chaıne logistique dans son en-semble. La premiere question legitime que l’on est en droit de se poser est : laconjonction des solutions optimales individuelles est-elle la meilleure facon

4en anglais on parle de (S, s) policy

11


de gerer la chaıne logistique ? D’un point de vue des formulations, la reponseest sans hesitation oui. Cependant, cette vision est extremement cloisonnee.Chaque acteur a son objectif propre, et partage un minimum d’informationavec ses clients et fournisseurs.

L’effet Forrester

L’etude des echanges d’informations et de matieres entre les acteurs dela chaıne d’approvisionnement a permis de mettre en lumiere des compor-tements etonnants. L’un des comportements les plus etudies est tres certai-nement l’effet Forrester, du nom de l’auteur qui en a montre les effets lepremier dans [28]. On parle aussi d’effet coup de fouet5, terme propose parles auteurs de [57, 58]. Ce comportement est une amplification des variationsde la demande au sein de la chaıne d’approvisionnement. On s’y interessebeaucoup a partir du milieu des annees 90 apres qu’une importante entre-prise se rende compte qu’elle en est victime. Cette entreprise produit desbiens dont la demande finale est tres peu variable au cours de l’annee. Pour-tant, au sein de la chaıne d’approvisionnement, plus on s’eloigne du clientfinal, et plus les demandes qui sont faites aux fournisseurs sont irregulieres.Ces consequences sont dues a l’absence de regard global sur la chaıne d’ap-provisionnement. Chaque acteur ne connaıt que la demande de son client, etpasse commande a ses fournisseurs en fonction de sa gestion propre. Ainsi,si la demande finale augmente subitement, elle est repercutee sur le premierdes fournisseurs (le plus a gauche dans une chaıne du type de celle de lafigure 1.2) uniquement apres avoir traversee toute la chaıne. Alors que s’ilavait ete informe des le depart, l’adaptabilite aurait ete plus rapide.

La figure 1.4, tiree de [88], illustre la propagation de l’effet Forresterdans une chaıne d’approvisionnement de fabrication de vetements.

Plus on s’eloigne du client final, et plus les variations dans les com-mandes aux acteurs de la chaıne augmentent. Dans cet exemple, on passed’une variation de 5% a une variation de 40%.

Les causes

D’apres [82], les causes des effets Forrester peuvent etre multiples :– La prevision de la demande : les techniques de prevision de la demande

se calibrent sur les informations passees. Plus celles-ci sont variables(rapportees a leur nombre) et moins il sera aise de faire une previsionvalable. On a alors tendance a prendre plus de donnees pour le cali-

5pour bullwhip effect

12

Gestion globale

Fig. 1.4: Propagation de l’effet Forrester dans une chaıne d’approvisionne-ment de vetements [88]

brage. Il en resulte une prevision meilleure en moyenne, mais dont lavariabilite est masquee.

– La duree de production : lorsque celle-ci est importante, elle a unegrande influence sur les calculs de stock de securite et de taille de lot.Plus la duree de production est grande, et plus une variation dans lademande sera amplifiee au fournisseur.

– La production par lot : cette derniere permet de repondre a une de-mande constante, par utilisation de stocks, mais entraıne des com-mandes au fournisseur qui sont irregulieres, puisque l’agent produitpar sequence. Il alterne les phases de commandes a son fournisseuravec des phases sans commande.

– La fluctuation des prix : elle entraıne des effets de sur-production etsous-production en fonction des couts des matieres premieres et desprix de vente du produit final. Les agents ont alors tendance a fairedu stock ou, a l’inverse, a utiliser leur stocks. Ce qui bien sur a desconsequences sur la variabilite des commandes.

13


– Des commandes gonflees : lors de periodes de penurie, les clients vontavoir tendance a gonfler les commandes afin de pouvoir continuer aproduire. Cela a tendance a accelerer la variabilite.

Des propositions

D’apres [20], il y a deux possibilites pour reduire ces effets. Tout d’abords’attaquer directement aux causes. Par exemple :

– Adapter les techniques de previsions : en ne mettant pas a jour lecalibrage des techniques, il y a possibilite d’effacer l’augmentationde la variabilite des demandes. Une preuve de cette proposition estfaite dans [20] sur le cas simple d’une demande normale avec delai delivraison fixe. Bien sur, cette proposition peut parfois etre tres delicatevoire dangereuse a mettre en place car pour effacer la variabilite, onperd de l’adaptabilite.

– Reduire la variabilite : cela peut passer par une politique de prix basquotidien. On efface alors les effets des promotions et rabais.

– Reduire la duree de production : cela aura un effet direct sur la va-riabilite comme explique precedemment mais aussi sur la quantite dedonnees necessaires pour les techniques de prevision, et la aussi celareduira les effets Forrester.

Ces solutions sont decentralisees, mais demandent un investissement dechaque acteur pour servir un but commun. Cela reste possible uniquements’il y a un pilotage centralise.

La seconde possibilite est de centraliser l’information. Par exemple :– Reduire l’incertitude : centraliser la demande du client final, et les

modes de gestion des differents acteurs de la chaıne.– Mettre en place des partenariats strategiques : cela permet d’augmen-

ter la quantite d’information echangee, d’augmenter la visibilite. Biensur ce type de partenariat peut etre lourd a mettre en place, et celarequiert une grande confiance mutuelle.

En regle generale, une centralisation de l’information est difficile a mettre enplace, il faut donc trouver des moyens decentralises pour reduire ces effets.De plus, une centralisation de l’information ne fera pas disparaıtre les effetsForrester, comme l’affirme les auteurs de [20] : The bullwhip effect existseven when demand information is completely centralized and all stages ofthe supply chain use the same forecasting technique and inventory policy.Cette approche pourra reduire les effets Forrester, mais pas les eliminer.

14

Gestion globale

L’information reduit la variabilite

Un constat est simple a faire : plus les agents de la chaıne d’approvi-sionnement ont a leur disposition de l’information relative a la demandeinitiale, aux types de gestion qu’utilisent les agents en aval de la chaıne(si l’on suppose que le client final est le plus en aval), et plus il leur seraaise de contrer les effets Forrester, si tant est qu’ils y soient interesses fi-nancierement. Un moyen detourne et qui reste decentralise est d’inclure lanotion de variabilite et d’information au sein des contrats liant des acteurssuccessifs de la chaıne. Un fournisseur propose a son client des contratsliant une certaine souplesse de commande a un certain niveau de prix. Plusle client veut de souplesse, et moins le prix sera interessant, une souplessetotale etant associee au prix du marche du produit. Au contraire, si le clientconsent a reduire sa souplesse de commande, alors il pourra beneficier d’unprix plus attractif, et le fournisseur aura plus de visibilite quant a sa pro-duction future. Tout ceci est a la base de ce que les auteurs de [4] appellentles contrats d’approvisionnement6.

6en anglais, on parle de supply contract

15

Chapitre 2

Etat de l’art

Sommaire2.1 Les modeles . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Les methodes . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 Les outils . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Dans ce chapitre, nous nous interessons aux differents modeles de contratsd’approvisionnement, ainsi qu’aux outils et methodes pour resoudre ce typede probleme.

2.1 Les modeles

Historiquement, une des premieres reponses pour contrer les effets For-rester est de mettre en place des periodes de prix bas pour guider la demandedu client, comme dans [60]. Cette reponse peut sembler aller a l’encontre despropositions precedentes. Mais elle n’avait pas pour objectif la cooperation :il s’agissait plus de maıtriser la demande. Nous n’allons pas developper cetype de modele ici.

Une seconde approche, celle que nous allons developper plus en detail,est de mettre en place des contrats d’approvisionnement entre client etfournisseur. On peut alors controler indirectement la variabilite de la de-mande par des contraintes specifiques sur les commandes. L’approche restedecentralisee, elle est facile a mettre en place. Ces contrats d’approvisionne-ment incluent la notion d’engagement1. Le client s’engage contractuellement

1en anglais, on parle de commitment.

17

2. Etat de l’art

a respecter certaines contraintes en echange d’un prix d’achat garanti parle fournisseur.

D’apres [4], ce type de contrats se caracterise par :– la duree– les couts et prix associes– les periodes de commandes– l’engagement sur les quantites– la flexibilite (frequence et amplitude des recours possibles)– l’engagement de livraison du fournisseur– la qualite des produits livres– le partage d’information

Les flux (d’information de matiere, financier) sont captures a travers cer-taines de ces caracteristiques. Ces contrats sont la base d’une cooperationentre agents de la chaıne logistique.

Nous allons nous pencher maintenant plus en detail sur les differentstypes de contrats qui ont ete etudies jusqu’a maintenant, et en particulierceux qui prennent en compte plusieurs etapes, l’incertitude de la demande,un unique produit et un unique fournisseur.

Nous decrivons ci-apres la partie commune de la formulation de cesproblemes de minimisation de cout dont nous avons retire la partie constanteliee au revenu de la vente :

minx,q

−s[xT ]+ +T∑t=1

ctqt + ht[xt]+ + pt[−xt]+ (2.1a)

s.c. xt = xt−1 − dt + qt, t = 1, . . . , T, (2.1b)

x0 donne. (2.1c)

avec xt representant l’etat du stock a la periode t, qt est la commande enperiode t, et dt la demande en t. Il y a les couts de stockages ht, les coutsde rupture pt, les prix d’achat ct, et le prix de la valeur residuelle s.

engagement minimum [1] Le client s’engage au debut de l’exercice acommander une quantite minimale w a chaque periode de l’horizonde l’exercice. Il ne peut commander moins que son engagement parcontrat, et s’il commande plus, la quantite au dela du niveau de sonengagement est achete a un prix plus eleve ct > ct. Le modele est

18

Les modeles

comme suit :

minx,w,q

−s[xT ]+ +T∑t=1

ctw + ct[qt − w]+ht[xt]+ + pt[−xt]+(2.2a)

s.c. xt = xt−1 − dt + qt, t = 1, . . . , T, (2.2b)

qt ≥ w, t = 1, . . . , T, (2.2c)

x0 donne. (2.2d)

Ce modele permet au fournisseur de connaıtre a priori une quantiteminimale de la demande a laquelle il devra faire face.

engagement total minimum [9] La quantite commandee cumulee surl’horizon temporel doit etre superieure a un volume initial fixe parle client.

minx,w,q

−s[xT ]+ +T∑t=1

ctqt + ht[xt]+ + pt[−xt]+ (2.3a)

s.c. xt = xt−1 − dt + qt, t = 1, . . . , T, (2.3b)T∑t=1

qt ≥ w, (2.3c)

x0 donne. (2.3d)

Ce modele donne plus de flexibilite au client, mais permet tout dememe de donner une information importante au fournisseur. Cetteapproche a permis aux auteurs de [3] de gerer plusieurs produits,l’engagement portant alors sur un volume financier global.

engagement flexible Le client s’engage initialement sur des volumes acommander pour chaque periode de l’horizon. Ensuite, il peut com-mander la quantite qu’il desire, la flexibilite est totale. Mais si la com-mande differe de l’engagement, des penalites s’ajoutent. Ce modelene fixe pas la facon dont les penalites interviennent. Il specifie seule-ment que les commandes ne sont pas contraintes, seuls des couts dedeviations interviennent. Nous illustrons ci-apres un type d’engage-ment flexible particulier : a la periode t, une deviation positive (resp.

19

2. Etat de l’art

negative) entraıne un cout de α+t (resp. α−t ) par unites de difference.

minx,w,q

−s[xT ]+ +T∑t=1

ctqt + ht[xt]+ + pt[−xt]+

+T∑t=1

α+t [qt − wt]+ + α−t [wt − qt]+ (2.4a)

s.c. xt = xt−1 − dt + qt, t = 1, . . . , T, (2.4b)

x0 donne. (2.4c)

Dans [2], le client a la possibilite de commander au niveau de sonengagement initial plus ou moins un certain pourcentage predefinisans surcout, et dans [4] le client definit lui meme au debut la margedont il pourra user, pour un cout fixe. Nous developperons un modelede ce type en partie V.

Tous ces modeles ont pour objectif de maintenir un maximum de flexibi-lite au client tout en donnant un maximum d’information au fournisseur surl’evolution probable de la demande a venir. Par exemple, avec un contratdu second type, le fournisseur ne connaıt pas la repartition de la demande avenir, mais il en connaıt le volume total, tout du moins une borne inferieure.Cela lui permet de s’organiser beaucoup plus facilement que si aucun contratd’approvisionnement n’avait ete signe entre lui et son client.

Ce sont des problemes d’optimisation sous incertitude qui modelisent desdecisions periodiques : on parle de decisions sequentielles dans l’incertain,d’ou le titre de la presente these.

Ce type de probleme est plus complexe que le probleme standard dumarchand de journaux et demande au gestionnaire de mettre en œuvre desmethodes et outils specifiques, propre au domaine de l’optimisation.

2.2 Les methodes

Les problemes generes par les contracts d’approvisionnement, meme s’ilsne concernent qu’un unique couple client-fournisseur sur un unique produits’averent rapidement de grande taille, du fait de la composante incertainede la demande et de la necessite de travailler sur plusieurs periodes. Lesengagements n’ont en effet de l’interet que si le nombre de periodes quisuivent cet engagement sont nombreuses. Par exemple, on peut supposer quece type de contrats peut concerner une periode d’un an, avec 12 periodes,une pour chaque mois.

20

Les methodes

Les auteurs de [4] parlent d’analyse de contrats : en effet, dans leurdifferents articles, ils s’interessent a choisir le type de contrat, ou le typede flexibilite le plus adapte a un jeu de donne, mais ne recherchent pas laquantite optimale de l’engagement. Pour eux, la quantite de l’engagementest un parametre. Ils resolvent le probleme, et regardent le cout qui enresulte. Ils vont ensuite refaire les calculs avec une nouvelle valeur pourl’engagement et ainsi de suite. Cette approche naıve d’un point de vue del’optimisation a l’avantage de limiter la taille des problemes traites.

Le frein principal a la mise en place d’une methode d’optimisation sousincertitude permettant de trouver la quantite optimale de l’engagement estbien connu : la malediction de la dimension. Les methodes principales d’op-timisation sous incertitude que sont la programmation stochastique et laprogrammation dynamique souffrent toutes deux de ce mal. Une approchefrontale du probleme de contrat d’approvisionnement avec l’une de ces deuxmethodes semble tout a fait illusoire. Voila pourquoi les auteurs de [4] se re-streignent a une analyse. Nous reviendrons plus en detail sur la maledictionde la dimension au chapitre 7, en fin de la partie II consacree a l’optimisa-tion sous incertitude et particulierement a l’approche par programmationstochastique.

Contourner la malediction de la dimension n’est pas chose aisee. Il existecependant des moyens d’optimiser sous incertitude en contournant cettemalediction. La programmation robuste en fait partie. D’ailleurs, c’est lapiste qui a ete exploitee pour optimiser des contrats d’approvisionnementsous incertitude. Les auteurs de [12] proposent une approche pour trou-ver une solution a ce probleme. L’approche est seduisante, et la taille duprobleme genere, comparee a sa version deterministe, n’a augmente qued’une facon polynomiale. Les temps de calculs restent donc faibles. Ce-pendant, l’approche par programmation robuste s’interesse a trouver unesolution qui satisfasse toute les valeurs de l’alea, de telle sorte qu’un profitminimal soit garanti. Son objectif n’est donc pas la maximisation du profitmoyen. Ce type d’approche apporte une solution qui, en moyenne, est assezdecevante, si l’on s’interesse au critere d’esperance.

Enfin, une approche deterministe, qui consiste a considerer la demandeconnue a l’avance, n’a aucun interet dans une approche avec engagementinitial. C’est la succession de decisions faites au fur et a mesure de la connais-sance qui apporte tout son interet aux modeles presentes ci-dessus.

21

2. Etat de l’art

2.3 Les outils

Pour modeliser un probleme d’optimisation sous incertitude, il existede nombreux outils qui sont cependant reserves aux specialistes de l’op-timisation, et sont inaccessibles a la majorite des decideurs. La resolutiond’un probleme d’optimisation sous incertitude comporte deux difficultes : laprise en compte de l’incertitude et la methode d’optimisation. Ci-apres lesdifferentes approches possibles qui permettent de resoudre un tel probleme.

– La premiere approche consiste a modeliser le probleme mathema-tiquement, trouver la methode d’optimisation adaptee a sa resolution,et de tout traduire dans un langage de programmation informatique.On peut dans certains cas utiliser des programmes specialises, les op-timiseurs, qui pourront resoudre le probleme central, ou bien des sousproblemes, des problemes relaxes, etc. Cette approche est de loin laplus efficace, mais la plus difficile a mettre en place pour un gestion-naire. Cette approche necessite de maıtriser les methodes d’optimisa-tion mais aussi de pouvoir modeliser un probleme avec une compo-sante incertaine. Parmi les optimiseurs les plus connus citons CPLEX[50], Mosek [61], XPRESS [64]. Il existe aussi une communaute libre enpleine expansion avec des optimiseurs comme notamment Proximal-ACCPM [6, 7].

– La seconde approche est d’utiliser des programmes specialises dansla modelisation de l’incertitude. Ce sont des programmes dedies al’incertain. Ils sont plus facile a mettre en place que les precedents,mais restent toutefois tres specialises, et de nouveau difficile a mettreen place par un gestionnaire. Citons le principal outil qu’est SLP-IOR[51].

– Les langages de modelisations algebriques, ou AML. Ces outils sontde loin les plus faciles a mettre en œuvre. Cependant, ils sont bienadaptes aux problemes deterministes, mais de nouveaux difficiles amettre en place dans un contexte incertain. Citons parmi les plusconnus AMPL, GAMS, AIMMS, GMPL. Nous reviendrons plus endetail sur les langages de modelisation algebrique en partie III.

De tous ces outils, les AML sont tres certainement les plus faciles amanier, et a mettre en œuvre pour un gestionnaire puisque la formulationreste tres proche de la realite. On se dessaisit completement de la methodede resolution. Malheureusement passer d’une version deterministe a uneversion stochastique, gerant l’incertain, n’est pas chose aisee.

22

Chapitre 3

Contributions

Les contributions de la these se situent a deux niveaux : une contribu-tion technologique a la mise en place de la programmation stochastique, etune contribution methodologique au contournement de la malediction de ladimension dans la mise en place de la programmation stochastique sur desproblemes massivement multi-etapes.

3.1 Contribution technologique

Nous avons realise l’outil informatique DET2STO qui permet de fa-ciliter la formalisation de problemes stochastiques a partir de problemesdeterministes formules grace au langage de modelisation algebrique GMPL.L’outil, son fonctionnement ainsi que les regles a suivre afin de pouvoirl’utiliser ont ete presentes dans l’article [85]. L’outil DET2STO est libre,et supporte un sous-ensemble d’AMPL qu’est GMPL lui aussi libre. Encomplement de cet outil, un site internet a ete realise afin de permettrel’utilisation en ligne de DET2STO : AML4SP. Cet outil, entierement realiseavec des outils libres, permet de formuler des problemes deterministes, deles transformer en problemes stochastiques, et enfin de les resoudre.

Cette contribution permet de faciliter l’acces au monde de l’optimi-sation sous incertitude aux personnes deja sensibilisees a l’optimisationdeterministe grace aux AMLs, et ceci uniquement avec des outils libres.

3.2 Contribution methodologique

Nous avons cherche a employer la technique de regle de decision avec laprogrammation stochastique. Apres des recherches avec les regles lineaires,nous nous penchons sur les regles de decision constantes par morceaux. Avec

23

3. Contributions

ces dernieres nous construisons une methode d’approximation de problemesstochastiques : la SPSDR1 en introduisant notamment les notions d’en-sembles de decision. Cette methode fait l’objet de l’article [87]. Enfin, nousavons developpe une adaptation de la methode SPSDR dans le cas de l’uti-lisation d’un critere CVaR.

Cette contribution permet d’approximer des problemes massivementmulti-etapes qui etaient jusqu’alors approximes tres difficilement avec laprogrammation stochastique ou dynamique, toutes deux victimes de lamalediction de la dimension, ou bien uniquement utilises dans un cadredeterministe ou d’optimisation min/max. De plus, nous pensons que SPSDRest une base sur laquelle de nombreuses contributions pourraient etre baties.Cette methode va nous permettre d’approximer des problemes d’optimisa-tion incluant des contrats d’approvisionnement.

1pour Stochastic Programming with step decision rules

24

Chapitre 4

Organisation de la these

La suite de la presente these se focalise sur des methodes et outils d’opti-misation qui permettent de resoudre des problemes de gestion de contratsd’approvisionnement, mais qui peuvent aussi resoudre un large eventail deproblematiques comme des problemes de transport, de localisation, d’affec-tation, de reseau, de gestion de cout, de gestion de risque, de prevision, demodelisation, de conception, etc. Il y a fort a parier qu’une liste exhaustivene peut etre faite, tant les possibilites sont multiples, mais aussi parce qu’ilreste des problemes non encore formules.

La suite de la these s’organise comme suit :

Partie II : Nous presentons l’optimisation deterministe avant de s’inte-resser a la programmation stochastique pour resoudre des problemesd’optimisation sous incertitude. Cette presentation de la program-mation stochastique standard se fait avec des notions specifiques,que nous reutiliserons par la suite. Elles permettent une meilleurecomprehension de notre proposition, et une meilleure comparaison.Ensuite, nous nous penchons sur les difficultes de mise en œuvre d’unetelle methode, et discutons notamment de la malediction de la dimen-sion.

Partie III : Nous presentons la contribution a la mise en œuvre de la pro-grammation stochastique qu’est le programme DET2STO. Ce pro-gramme permet de faciliter le passage d’un probleme deterministe aun probleme stochastique.

Partie IV : Nous proposons une contribution a l’operabilite de la pro-grammation stochastique : la programmation stochastique avec reglesde decision constantes par morceaux (SPSDR), et une adaptation dela methode a une prise en compte du risque.

25

4. Organisation de la these

Partie V : Nous utilisons la methode SPSDR sur un probleme de contratsd’approvisionnement et comparons notre approche avec d’autres.

Partie VI : Nous concluons sur les contributions proposees et listons lesnouvelles pistes de recherche.

26

Partie II

Optimisation multi-etapesdans l’incertain

27

Introduction

Cette partie presente la programmation stochastique standard au seinde l’optimisation sous incertitude, et au sein de l’optimisation en general. Laspecificite de cette presentation est dans l’utilisation des notions d’ensemblesde decision et de regles de decision. Ces concepts existent depuis longtemps,mais les termes que nous decidons d’introduire s’adaptent bien a notre ap-proche qui fait l’objet de la presente these : la programmation stochastiqueavec regles de decision, developpee dans la partie IV.

Nous souhaitons presenter la technique standard et les limites a sonutilisation dans le cas d’un probleme avec de nombreuses etapes.

Dans le chapitre 5, nous decrivons le type de probleme auquel nous nousinteressons, en partant d’une formulation deterministe statique pour arrivera une formulation dynamique sous incertitude.

Dans le chapitre 6, nous presentons l’approche programmation stochas-tique pour resoudre des problemes d’optimisation dynamique sous incerti-tude : la programmation stochastique multi-etapes.

Dans le chapitre 7, nous presentons les difficultes methodologique ettechnologique de mise en place d’une telle methode.

29

Chapitre 5

Une classe de problemesd’optimisation

Sommaire5.1 Probleme deterministe . . . . . . . . . . . . . . . . . . . 31

5.2 Notations des donnees incertaines . . . . . . . . . . . . 33

5.3 Probleme stochastique . . . . . . . . . . . . . . . . . . . 34

Dans ce chapitre, nous rappelons la formulation standard d’un problemed’optimisation deterministe, puis sous incertitude. Cette these se limiteaux problemes d’optimisation convexes a contraintes lineaires et a variablesreelles.

Il existe bien entendu des extensions au cas lineaire comme la program-mation stochastique quadratique [52, 55], la programmation stochastiqueen nombres entiers [15, 41, 59, 77, 78], la programmation stochastique aveccontraintes en probabilite [67, 75] ou bien encore l’optimisation en tempscontinu [19]. Nous n’en parlerons pas ici.

5.1 Probleme deterministe

Optimiser un probleme c’est trouver, parmi toutes les solutions admis-sibles, une qui minimise un critere defini, la fonction objectif. Cette derniereest aussi appelee fonction economique car dans la plupart des cas, elle evaluela solution courante en terme de cout financier. La forme standard d’un

31

5. Une classe de problemes d’optimisation

probleme d’optimisation mathematique est la suivante :

minu∈U

f(u) (5.1a)

s.c. Au+ c ≤ 0 (5.1b)

ou u ∈ Rm est la variable de decision, celle dont nous devons trouver une desvaleurs optimales. Nous l’appellons aussi commande. La fonction objectiff : Rm 7→ R est supposee convexe et U est l’ensemble admissible des u,U ⊂ Rm, suppose non vide et convexe. L’inegalite Au + c ≤ 0 definitl’ensemble des contraintes lineaires1 auxquelles la variable u est soumise. Aest une matrice a valeur dans Rn,m, et c ∈ Rn est un vecteur. Tout deuxsont connus. Ce probleme compte n contraintes.

La structure de la matrice A fait que le probleme (5.1) peut etre statiqueou dynamique. Un probleme est considere statique si chaque composantede la commande u a ses contraintes propres. Soit ai,j un element de A, aveci = 1, . . .m et j = 1, . . . n. Si pour tout j il y a au plus un ai,j non nul, alorsle probleme est statique. Au contraire, un probleme est dynamique si lescontraintes font intervenir plusieurs variables, elles-memes presentes dansplusieurs contraintes.

Nous nous interessons maintenant a une classe de probleme dynamiqueparticuliere : celle qui regroupe les problemes dont la dynamique est tem-porelle et dont les contraintes dynamiques sont explicites.

Un probleme dynamique integrant le temps permet de representer l’evo-lution d’un systeme, fonction de decisions indicees par le temps. L’etat dusysteme est defini par la variable x = (x0, . . . , xT ), avec xt a valeurs dans Rsur l’intervalle de temps 0, . . . T , le parametre T etant l’horizon temporel.L’etat initial du systeme x0 est connu. u = (u0, . . . , uT ) ∈ Rm,T+1 est lavariable de decision definie sur 0, . . . T . Notons que le cas statique est un casparticulier du cas dynamique, avec une seule periode temporelle. La notiond’etat est dans le cas statique implicite dans l’ecriture de la contrainteAu+ c ≤ 0. Nous supposons que l’etat est uni-dimensionnel, mais s’il etaitmultidimensionnel cela ne changerait en rien le principe general.

Un intervalle de temps [t, t + 1] est une periode temporelle comportantdivers evenements, respectant la chronologie suivante :

→ xt 99K ut → (5.2)

L’etat xt est donc connu au moment de la prise de decision ut. Nousconsiderons que la periode [T, . . . [ comporte un etat, l’etat final xT , et unedecision uT . De plus, nous definissons les fonctions suivantes :

1La formulation Au+ c ≤ 0 permet une limitation explicite aux contraintes lineairesau sens de u.

32

Notations des donnees incertaines

– ft : R×U 7→ R permet d’evaluer la solution associee au couple (xt, ut)en fonction de l’etat du systeme et de la decision qui y est prise. Lafonction ft est defini pour t = 0, . . . T .

– φt : R× U 7→ R definit la dynamique du systeme a travers son etat :xt = φt(xt−1, ut−1). La fonction φt est lineaire et definie pour t =1, . . . T .

Un probleme avec une dynamique temporelle et a contraintes explicitesest defini comme suit :

minu,x

T∑t=0

ft(xt, ut) (5.3a)

s.c. Atut +Btxt + ct ≤ 0, t = 0, . . . T, (5.3b)

xt = φt(xt−1, ut−1), t = 1, . . . T, (5.3c)

x0 connu, (5.3d)

avec At defini sur Rm,n, Bt defini sur Rn et ct un vecteur a valeur dans Rn.Ces 3 entites sont definies pour t = 0, . . . T . Le present probleme compte(n + 1) × (T + 1) contraintes, de (5.3b) a (5.3d). Les contraintes propresa chaque periode temporelle sont decomposees en (5.3b) alors que la dy-namique du systeme est concentree en (5.3c). Dans les problemes (5.1) et(5.3), l’ensemble des parametres est considere connu, deterministe. Noussouhaitons maintenant nous interesser a des problemes dans lesquelles desinformations ne sont pas connues a priori.

5.2 Notations des donnees incertaines

Pour manipuler des elements incertains, nous avons besoin de quantifieret limiter la notion d’incertain. La presente section regroupe l’ensemble desdefinitions probabilistes qui seront utilisees dans le reste de cette these.

– Ω est un ensemble appele espace des observables ou espace des evene-ments elementaires. Un element ω de Ω est appele etat de la nature.

– Une tribu A sur Ω est une collection non vide de sous-ensembles deΩ stable par passage au complementaire et par unions denombrables.

– Un element a de A est appele un evenement.– Le couplet (Ω,A) est appele espace mesurable.– Une mesure sur un espace mesurable (Ω,A) est une application µ deA dans R ⊂ R+ telle que µ(∅) = 0 et µ(

⋃nk=1Ak) =

∑nk=1 µ(Ak)

pour toute collection denombrable d’elements Ak de A deux a deuxdisjoints. On note en forme compacte µ : A 7→ R.

33


– µ est une application mesurable de (Ω,A) dans (Ω1,A1) si pour toutB ∈ A1, A = µ−1(B) est un element de A. On note en forme com-pacte : µ : A 7→ A1. On dit aussi que µ est A1-mesurable, ou A1-adapte.

– Le triplet (Ω,A, µ), avec µ une mesure, est appele espace mesure.– La mesure P : A 7→ [0, 1] est appelee probabilite.– Le triplet (Ω,A,P) est appele espace de probabilite.– Une variable aleatoire ξ (ou v.a.) est une application mesurable de

(Ω,A,P) a valeur dans Ω1, muni d’une tribuA1. Dans le cas particulierd’une variable aleatoire reelle, le couplet (Ω1,A1) egale (R,B), avecB ensemble des boreliens.

– Une filtration (Ft)t∈N sur l’espace de probabilite (Ω,A,P) est uneserie de collections de sous-tribus contenues dans A telles que t < t′

implique Ft ⊂ Ft′ . Cette propriete est appelee raffinement.– (Ω,A, (Ft)t∈N,P) est appele espace de probabilite filtre.– On appelle processus aleatoire ou processus stochastique une famille

de v.a. indexees : ξtt∈N.– Le processus aleatoire ξtt∈N est adapte a la filtration (Ft)t∈N si ξt

est Ft-mesurable pour tout t.

5.3 Probleme stochastique

Dans la presente these, nous nous interessons a des problemes ou leparametre incertain intervenant est independant de la ou des decisions prisesau fur et a mesure.

Un probleme d’optimisation sous incertitude, ou probleme stochastique,est un probleme d’optimisation dans lequel la fonction objectif, et/ou descontraintes sont soumises a une incertitude. Nous modelisons cette incer-titude par une variable aleatoire ξ. Nous allons redefinir les 2 problemesprecedents en y integrant de l’incertitude.

Interessons-nous tout d’abord au cas statique. Definissons la fonction F ,fonction de la commande u et d’une variable aleatoire reelle ξ definie sur unespace de probabilite (Ω,A,P). Cette fonction F represente l’utilite de lasolution associee au couple (u, ξ). Elle est supposee mesurable, pour u fixe,et integrable. Nous definissons la nouvelle fonction objectif f(u) commel’esperance de F (u, ξ) telle que :

f(u) = E[F (u, ξ)]. (5.4)

34

Probleme stochastique

Un probleme stochastique statique est defini comme suit :

minu∈U

E[F (u, ξ)] (5.5a)

s.c. Au+ c ≤ 0 (5.5b)

A et c peuvent etre aleatoires, fonctions de ξ. Nous nous limitons a lapresentation du cas decision-hasard2 dans lequel la decision est prise avantde connaitre la realisation de l’alea. Le contraire reviendrait a optimiserplusieurs problemes independants, et n’aurait que peu d’interet dans l’ideed’etendre le formalisme au multi-etapes. Pour de plus amples informationssur les differences entre les approches decision-hasard et son oppose, onpourra consulter [95].

Nous allons etendre la definition (5.2) d’un intervalle de temps [t, t+ 1]a

→ ξt 99K xt 99K ut → (5.6)

avec ξt la realisation d’une nouvelle v.a. ξt definie sur (Ω,A,P). Un ensemblede ξt successifs represente un processus aleatoire que nous noterons parξtTt=0. Nous notons σt = (ξ0, . . . , ξt) une realisation partielle definie surl’espace de probabilite (Ω,A,P). Nous appelons cette realisation partielleun sous-scenario, et la realisation complete σT un scenario. Nous munissonsl’espace de probabilite d’une filtration (Ft)Tt=0. Nous posons l’hypothese queξtTt=0 est adapte a la filtration (Ft)Tt=0.

Notons les cas particuliers du debut et de la fin de l’horizon temporel :

x0 99K u0 → (5.7)

ξ0 ne pouvant prendre qu’une unique valeur (P(ξ0 = ξ0) = 1), et x0 estconnu (invariant). Pour la derniere periode :

→ ξT 99K xT 99K uT (5.8)

La prise de decision en derniere periode est tres souvent absente car nes’evaluant qu’a travers ses consequences sur l’etat suivant. Le cas echeant,nous fixerons uT = 0.

Dans le cas dynamique, la formule de recurrence qui definit la dynamiquedu systeme doit prendre en compte la variable aleatoire :

xt = φt(xt−1, ut−1, ξt) (5.9)

Nous pouvons reecrire cette egalite sans la recurrence de la facon sui-vante :

xt = φt(x0, u0, . . . , ut−1, ξ0, . . . , ξt) (5.10)

2En anglais on parle de here and now, a opposer au cas wait and see.

35


Nous faisons apparaıtre dans cette formulation les realisations de la v.a. etnon la v.a. elle-meme afin d’appuyer le fait qu’au moment de calculer xt, lesrealisations (ξ0, . . . , ξt) des v.a. (ξ0, . . . ξt) sont connues : ce sont des observa-tions. Nous incluons aussi dans les observations les etats passes du systeme,et les decisions qui ont deja ete prises. A l’instant t, les realisations desv.a. ξt+1, . . . ξT ne sont pas encore connues : c’est l’incertitude residuelle.Nous sommes en mesure d’evaluer le niveau d’information disponible achaque instant t. Cette information disponible est une contrainte intrinsequeau probleme : on ne peut pas decider de la commande ut en supposantconnaıtre les realisations de l’incertitude residuelle. C’est la contrainte denon-anticipativite. De la meme facon que nous avons ecrit xt, nous allonsecrire ut comme une fonction des observations :

ut = ψt(x0, u0, . . . , ut−1, ξ0, . . . , ξt) (5.11)

ou de facon recurrente :

ut = ψt(xt, ut−1, ξt) (5.12)

La commande est une fonction des observations ou regle de decision.En effet, la resolution d’un probleme d’optimisation stochastique ne fixepas de valeurs de commandes a prendre, mais bien un ensemble de reglesqui ne seront des decisions qu’apres observation. Cela met en lumiere laphase importante de mise en place des politiques de decision, bien souventoubliee dans la litterature. Nous parlerons plus longuement de cette phaseen fin du present chapitre, et nous reviendrons plus longuement sur les reglesde decision dans la partie IV.

La contrainte de non-anticipativite est respectee par definition car nousavons pose l’hypothese que le processus aleatoire est adapte a la filtra-tion (Ft)Tt=0. Nous sommes en presence d’un processus a memoire par-faite, c’est-a-dire qu’a l’instant t, l’ensemble des observations est disponible.Cela contraint l’approche par programmation stochastique a creer un arbred’evenements comme nous le verrons en detail dans le chapitre 6.

La reflexion qui va amener a une des contributions de la presente theseest la suivante : la Ft-adaptabilite du processus aleatoire est une condi-tion suffisante, mais pas necessaire, au respect de la contrainte de non-anticipativite.

D’ailleurs, la filtration est parfois inadaptee au type de probleme traite.Prenons le cas par exemple d’un processus a memoire instantanee, c’est-a-dire qu’a chaque instant t, l’ensemble des informations disponibles estlimite3 a la derniere realisation ξt. Dans ce cas precis, la filtration n’est pas

3Dans le sens ou la derniere observation est suffisante.

36

Probleme stochastique

necessaire. Il peut etre interessant de trouver une structure de tribus qui soitsuffisante, et qui ait des proprietes permettant de respecter la contrainte denon-anticipativite.

Supposons que nous ayons a notre disposition une suite de sous-tribusde A que nous noterons (Pt)Tt=0 telle qu’il existe une filtration Ft telle quepour tout t, Pt ⊂ Ft, alors un processus adapte a la serie de sous-tribus(Pt)Tt=0 respecte la contrainte de non-anticipativite. Nous reviendrons endetail sur cette approche dans la partie IV.

Les variables ut et xt sont des fonctions de σt, elles doivent aussi etre Ft-mesurables, pour tout t = 0, . . . , T . De facon precise, nous devrions dire queφt et ψt sont Ft-mesurables, mais par abus d’ecriture, nous remplaceronsparfois ces deux fonctions par leurs resultats xt et ut. La fonction objectiff(u) est supposee separable c’est-a-dire que nous pouvons l’ecrire commela somme de fonctions indicees par le temps. Nous etendons l’ecriture (5.4)au triplet (xt, ut, ξt) comme suit :

f(u) = E[T∑t=0

Ft(xt, ut, ξt)] (5.13)

Nous sommes maintenant en mesure de formuler un probleme d’optimi-sation dynamique sous incertitude :

minu,x

E[T∑t=0

Ft(xt, ut, ξt)] (5.14a)

s.c. Atut +Btxt + ct ≤ 0, t = 0, . . . , T, (5.14b)

xt = φt(xt−1, ut−1, ξt), t = 1, . . . , T, (5.14c)

xt et ut sont Ft-mesurables. (5.14d)

x0 connu (5.14e)

Nous desirons resoudre de tels problemes par une approche programma-tion mathematique. Pour cela, la programmation stochastique propose dediscretiser l’alea ξt en un nombre fini de valeur afin d’ecrire un equivalentdeterministe au probleme (5.14).

37

Chapitre 6

L’approche par laprogrammation stochastique

Sommaire6.1 Deux etapes . . . . . . . . . . . . . . . . . . . . . . . . 40

Discretisation de ξ1 . . . . . . . . . . . . . . . . . . . . 40

Adaptation de x1 et u1 a la discretisation . . . . . . . . 42

6.2 Plus de 2 etapes . . . . . . . . . . . . . . . . . . . . . . 43

Arbre d’evenements . . . . . . . . . . . . . . . . . . . . 44

6.3 Generation d’un arbre d’evenements pour processusmulti-etapes . . . . . . . . . . . . . . . . . . . . . . . . 46

Agregation de scenarios . . . . . . . . . . . . . . . . . . 48

6.4 Application de la politique de decision . . . . . . . . . . 55

Dans ce chapitre, nous decrivons l’approche par programmation stochas-tique pour resoudre le probleme (5.14), ou plutot la facon dont la program-mation stochastique permet de formuler ce probleme comme un problemede programmation mathematique. La resolution en elle-meme est confiee aun calculateur de programmation mathematique adapte.

Nous distinguons deux cas, qui font l’objet de deux sections : le pre-mier cas est le probleme a deux etapes, et le second cas est le problemea plus de deux etapes, appele multi-etapes. Ces deux classes de problemesse distinguent par des approches, des utilisations et des complexites tresdifferentes. Nous parlons ensuite de la construction de l’arbre d’evenements,puis de l’application des politiques de decision.

39

6. L’approche par la programmation stochastique

6.1 Deux etapes

Nous commencons par nous interesser aux problemes a deux etapes,c’est-a-dire pour lesquels une decision u0 est prise (decision de premiereperiode ou decision du present), puis apres observation d’un alea ξ1, unedecision u1 est prise (decision de seconde periode ou decision de recours).Nous avons la chronologie suivante :

u0 → ξ1 99K x1 99K u1. (6.1)

Un probleme a deux etapes peut se formuler comme suit :

minu,x

f(u) = F0(u0) + E[F1(x1, u1, ξ1)] (6.2a)

s.c. A0u0 +B0x0 + c0 ≤ 0, (6.2b)

A1u1 +B1x1 + c1 ≤ 0, (6.2c)

x1 = φ1(x0, u0, ξ1), (6.2d)

x1 et u1 sont F1-mesurables. (6.2e)

x0 connu (6.2f)

Pour resoudre ce probleme, la programmation stochastique propose dediscretiser la v.a. ξ1 de telle sorte que le probleme (6.2) puisse etre formulecomme un probleme de programmation mathematique standard. Il va deplus nous falloir expliciter les contraintes de mesurabilite.

Discretisation de ξ1

Nous ecrivons la fonction objectif (6.2a) sous une forme plus compacteet nous remplacons l’esperance par son ecriture integrale :

min f(u) =

∫F (x, u, ξ1) dD(ξ1) (6.3)

avec F (x, u, ξ1) = F0(u0) + F1(x1, u1, ξ1) et D(·) la fonction de densite deprobabilite de ξ1.

Discretiser ξ1 revient a trouver une loi de probabilite, caracterisee parune fonction de densite D, d’une variable aleatoire ξ proche de ξ1. On resoutdans ce cas un probleme approche de minimisation de fonction objectif :

f(u) =

∫F (x, u, ξ) dD(ξ). (6.4)

40

Deux etapes

La variable aleatoire ξ etant consideree discrete, on ecrit plutot :

f(u) =N∑n=1

πnF (x, u, ξn) (6.5)

avec ξ1, . . . ξN les valeurs possibles de ξ et π1, . . . πN leurs probabilites res-pectives.

Nous devons trouver une distribution D qui soit la plus proche possiblede D. La notion de proximite peut prendre plusieurs formes. Nous pourrionspar exemple nous interesser a egaliser un grand nombre de moments de sesdeux distributions. On parle alors d’adaptation des moments, ou momentmatching. Cependant, l’auteur de [54] montre que cette methode utiliseepour mesurer la distance entre une distribution continue et une distribu-tion discrete ne donne pas une bonne approximation en terme de politiquede decision. Les auteurs de [47] montrent d’ailleurs sur un exemple quememe avec les quatre premiers moments identiques, l’erreur d’approxima-tion (comme defini peu apres) peut etre grande. Nous pourrions utiliser ladistance de Kolmogorov-Smirnov, ou distance uniforme. Elle est cependantconnue pour mal discretiser les queues de distributions.

Nous allons nous concentrer sur deux options, qu’il nous semble perti-nent d’introduire avant une prochaine utilisation en partie IV. Il s’agit dela mesure de distance de Fortet-Mourier introduite dans [99] puis etudieedans [25, 40, 44, 65, 84], et de la generation par methode de Monte-Carlo[79].

La premiere approche consiste a minimiser l’erreur qui serait faite entrela solution optimale et la solution approchee, evaluee a travers la fonctionde cout f . En reprenant les notations de [65], on calcule l’erreur d’approxi-mation comme suit :

e(f, f) = f(arg minuf(u))− f(arg min

uf(u)) (6.6)

L’auteur de [65] explique que le probleme de minimiser cette erreur estequivalent, sous condition que la fonction f soit lipschitzienne, au problemede minimisation de la distance suivante :

d1(D, D) = sup∫F (x, u, ξ) dD(ξ)−

∫F (x, u, ξ) dD(ξ) (6.7)

La distance de Fortet-Mourier se note de facon generale dp, avec commecontrainte que la fonction traitee f doit etre lipschitzienne d’ordre p. Si lafonction f est lipschitzienne d’ordre 1, on parle alors du cas particulier dela distance d1 dite distance de Wasserstein. De plus, on note :

κ(D, D) = minD

d1(D, D) (6.8)

41


avec κ appelee fonction de Kantorovich [71]. La minimisation de (6.7) est unprobleme de transport de masse optimal de Monge-Kantorovitch [69, 70].Il en decoule les proprietes suivantes :

Theoreme 1. Parmi toutes les distributions D avec comme support uneserie de points ξn, n = 1, . . . N , la distribution D la plus proche de D, ausens du probleme de transport de masse (6.7), est definie telle que :

D(z) =∑n|ξn≤z

D(ξn + ξn+1

2) (6.9)

avec ξN+1 = +∞. L’extremum de (6.7) est atteint en

d1(D, D) =N∑n=1

∫ ξn+ξn+12

ξn−1+ξn2

| ξ − ξn | dD(ξ) (6.10)

avec ξ0 = −∞.

Demonstration. Ces proprietes sont des consequences du theoreme de Kan-torovitch - Rubinstein, prouvees par l’auteur de [90].

On s’interesse alors a minimiser (6.10) avec comme variable la serie desξn. On trouve finalement une serie de N valeurs ξn auxquelles on associe lesprobabilites definies a travers (6.9).

La seconde approche, tres utilisee dans la litterature, consiste a tirer defacon aleatoire un ensemble de valeurs ξn. On parle de methode de Monte-Carlo. La theorie des grands nombres nous assure que lorsque le nombre devaleurs tend vers l’infini, l’ecart d’approximation tend vers 0. Les valeurstrouvees sont equiprobables, soit πn = 1

Navec n = 1, . . . N . Cette methode

nous permet de construire l’estimateur :

f(u) =1

N

N∑n=1

F (x, u, ξn) (6.11)

La qualite de cet estimateur est lie a la grandeur du nombre N , et a laqualite du generateur pseudo-aleatoire utilise [56].

Adaptation de x1 et u1 a la discretisation

Apres utilisation d’une des methodes precedemment citees, nous sommesen presence d’un probleme d’optimisation comme le probleme (6.2), avecξ1 discrete. Expliciter la contrainte de mesurabilite sur un espace discretiserevient a rendre les variables u1 et x1 contingentes aux valeurs ξn. Nous

42

Plus de 2 etapes

reecrivons une version equivalente mais deterministe du probleme (6.2), lefameux deterministe equivalent :

minu,x

f(u) = F0(u0) +N∑n=1

πnF1(xn1 , un1 , ξ

n) (6.12a)

s.c. A0u0 +B0x0 + c0 ≤ 0, (6.12b)

A1un1 +B1x

n1 + c1 ≤ 0, n = 1, . . . N (6.12c)

xn1 = φ1(x0, u0, ξn), n = 1, . . . N (6.12d)

x0 connu (6.12e)

L’etat xn1 et la commande un1 sont maintenant au nombre de N . Leurs va-leurs sont specifiques a la realisation ξn. Le probleme (6.12) est un problemede programmation mathematique. F etant convexe et les contraintes lineairespar hypothese, ce probleme est facilement resolu par l’utilisation d’un op-timiseur.

6.2 Plus de 2 etapes

Nous considerons maintenant un probleme a plus de 2 etapes, avec unprocessus temporel comme defini par les formules (5.6) a (5.8). Pour ex-pliciter les contraintes de mesurabilite, nous pouvons formuler le problemede facon recurrente comme etant la minimisation de chaque periode, souscondition que les decisions anterieures ont ete prises. Le premier problemeest donc :

minu,x

F0(u0) + E[Q1(x1, u1, ξ1)] (6.13a)

s.c. A0u0 +B0x0 + c0 ≤ 0, (6.13b)

x0 connu (6.13c)

avec une formulation generale de la fonction Q pour t = 1, . . . T − 1 commesuit :

Qt(xt, ut, ξt) = infut

[Ft(xt, ut, ξt)

+ E[Qt+1(xt+1, ut+1, ξt+1)|ξt]]

(6.14a)

s.c. Atut +Btxt + ct ≤ 0, (6.14b)

xt = φt(xt−1, ut−1, ξt), (6.14c)

xt−1, ut−1, ξt connus (6.14d)

43


Nous supposons dans la suite que la decision uT n’est pas evaluee, afinde se rapprocher des formulations plus souvent employees en multi-etapes.Ainsi, uT disparait des formulations, et notamment dans celle de QT :

QT (xT , ξT ) = inf[FT (xT , ξT )] (6.15a)

s.c. BTxT + cT ≤ 0, (6.15b)

xT = φT (xT−1, uT−1, ξT ), (6.15c)

xT−1, uT−1, ξT connus (6.15d)

On voit ici de facon explicite toute la difficulte d’un tel probleme. Leprobleme de l’etape t est fonction d’une esperance sur la prochaine realisationde la v.a. ξt+1 sachant σt = (ξ0, . . . , ξt).

Pour formuler un tel probleme comme un probleme de programmationmathematique, nous avons besoin d’un support discret pour le processusaleatoire qui traduise l’espace filtre.

Arbre d’evenements

Pour cela, nous approximons le processus aleatoire par un processusdiscret represente sous forme d’un arbre d’evenements, comme illustre dansla figure 6.1. Un arbre d’evenements est un graphe oriente possedant unesource (t = 0, N0 = 1), et dont les nœuds terminaux, ou feuilles, sont tousa la meme distance de la source, en terme de nombre d’aretes. Les nœudssepares par une unique arete de la source sont consideres comme apparte-nant a la periode 1, les suivants (a une distance de la source de exactementdeux aretes) a la periode 2, etc. Nous ne representons pas l’orientation desarcs du fait de ce repere par periode.

Les nœuds sont identifies par le couple (t, n) indiquant qu’il s’agit duneme nœud de la periode t. Il y a Nt nœuds par periode t, avec Nt−1 ≤Nt, t = 1, . . . , T .

Nous associons une realisation du processus aleatoire a chaque nœud del’arbre d’evenements. Les arcs representent les successions possibles entre lesdifferentes realisations de la variable aleatoire. La structure d’arbre (chaquenœud ne possede qu’un arc entrant) nous garantit l’unicite du chemin jus-qu’a un nœud, soit l’unicite du passe. L’apparition de l’incertitude au furet a mesure des periodes se caracterise par la presence de plusieurs arcssortants.

Ces caracteristiques traduisent une des proprietes de la filtration qu’estl’evolution de l’apparition de l’incertitude ou de l’information. Par exemple,au nœud (2, n2) de la figure 6.1, nous connaissons l’historique des realisationsξ0, ξ

n11 , mais nous ne connaissons pas encore la realisation en periode 3. Les

44

Plus de 2 etapes

`

``````

``````

!!!!

!!!

aa

!!

aa

!!

aaaaaaa

PPZZZZZZZZ

t = 0 t = 1 t = 2 t = 3

ξ0

1

ξN11

N1

ξn11

n1

ξ11

1

...

...

ξN22

N2

ξn22

n2

ξ12

1

...

...

ξN33

N3

ξn3+13

n3 + 1

ξn33

n3

ξ13

1

...

...

Fig. 6.1: Un arbre d’evenements a 4 etapes (T = 3)

deux scenarios terminant aux nœuds (3, n3) et (3, n3 + 1) ne sont pas re-connaissables avant la periode 3.

Pour faciliter le referencement des successeurs (sens de l’arc oriente) etpredecesseurs (sens oppose), nous definissons une fonction a qui pour toutnœud (t, n) nous donne l’indice du nœud precedent. Le predecesseur dunœud (t, n) est le nœud (t− 1, a(t, n)). Par exemple, a(3, n3) = n2.

En presence d’un arbre1, nous explicitons la contrainte de mesurabiliteen rendant contingentes aux nœuds (t, n) les variables u et x. L’unicite dupasse est garanti, ainsi que la non-anticipativite. Nous nous passons donc desfonctions Q. Nous reecrivons une version deterministe du probleme (5.14) :

1La construction a proprement parler de l’arbre fait l’objet de la section suivante.

45


minu,x

F0(u0) +

N1∑n1=1

πn11 F1(xn1

1 , un11 , ξ

n11 ) + . . .

+

NT∑nT=1

πnTT FT (xnTT , ξnTT ) (6.16a)

s.c. Atunt +Btx

nt + ct ≤ 0, t = 0, . . . T, n = 1, . . . Nt, (6.16b)

xnt = φt(xa(t,n)t−1 , u

a(t,n)t−1 , ξnt ), t = 1, . . . T, n = 1, . . . Nt, (6.16c)

x0 connu (6.16d)

La presence de la fonction a dans la formulation souligne l’importanced’un bon indicage des variables. Nous en parlerons plus longuement dansla partie III.

Ce probleme de programmation mathematique est de grande taille pourT ou N grand. En effet, les fonctions de recurrence amenent une structurematricielle tres creuse. Si l’on considere un probleme ou les contraintesdynamiques ne sont pas explicitees par φ, mais sont presentes au sein dela matrice A, nous pouvons illustrer cette derniere comme dans la figure6.2. Cette matrice a une structure emboitee tres particuliere dont certainsoutils, comme SET [32], tirent avantage pour repousser un peu plus loin lalimite de la dimension d’un probleme gerable. La matrice possede N1 blocsdisposes en diagonale. Le premier bloc, la sous-matrice M , definit toutes lescontraintes pour le premier sous-arbre, de racine (1, 1). Cette sous-matricea elle-meme une structure en bloc-diagonale. Et ainsi de suite.

La separabilite de la fonction F permet d’utiliser une technique dedecomposition type Benders [96] qui nous donne la possibilite de parallelisercertains sous-problemes, et de la gagner du temps de calcul. Nous allonsnous interesser plus precisement a la complexite d’un tel probleme dans lasection 7. Avant cela, il est important de se pencher sur la structure et laconstruction de l’arbre.

6.3 Generation d’un arbre d’evenements

pour processus multi-etapes

Pour construire un arbre d’evenements, nous pouvons utiliser une ap-proche s’interessant a discretiser les probabilites conditionnelles de chaqueξt sachant σt−1. Cette methode est facile a mettre en œuvre pour T faible, etelle permet une bonne discretisation. Mais pour T grand, l’arbre genere est

46

Generation d’un arbre d’evenements pour processus multi-etapes

Fig. 6.2: Structure de la matrice du deterministe equivalent, dans le cas oules contraintes dynamiques ne sont pas separees

soit trop grand pour etre utilise pour l’optimisation, soit trop peu discretise.C’est pourquoi nous ne parlerons pas de cette methode ici.

La plupart du temps l’arbre d’evenements est construit sur base d’unecollection de scenarios. Cette section s’interesse a cette construction, quirevet une importance capitale.

Nous supposons posseder une collection deN scenarios σn = (ξ0, ξn1 , . . . ξ

nT )

representant tout ou partie des suites de realisations possibles des ξt. Cettecollection, notee S, est la representation parfaite du processus stochas-tique s’il est discret, ou, comme c’est plus generalement le cas, est unerepresentation partielle du processus trouvee par tirage aleatoire type Monte-Carlo. Dans ce cas, card(S) = N doit etre grand.

Si le processus aleatoire est continu, la collection S, trouvee par ti-rage aleatoire, est un arbre particulier. En effet, tous les scenarios serontdifferents (avec une probabilite de 1) des la periode 1. Cet arbre ne possedepas de branchement apres la periode 0. Nous appelons ce type d’arbreun peigne. Si le processus aleatoire est discret, la collection S n’est pasnecessairement un peigne. Dans la suite de la these, nous supposons que lacollection S est un peigne.

En l’etat, le peigne ne peut pas etre utilise comme support de la pro-grammation stochastique puisqu’il ne traduit pas le fait que l’information

47


stochastique est devoilee au fur et a mesure. Il va donc falloir passer d’unpeigne a un arbre possedant plus de branchements.

La morphologie d’un arbre nous donne des informations sur la filtrationa laquelle est adaptee le processus stochastique represente. Par exemple,dans la figure 6.3, nous illustrons 3 arbres representant de facon exacte desprocessus aleatoires. Il en ressort des structures de filtrations differentes :

– pour l’arbre du haut, ou peigne, F0 ( F1 = F2 = F3.– pour l’arbre central, ou arbre equilibre, F0 ( F1 ( F2 ( F3.– pour l’arbre du bas, ou plumeau, F0 = F1 = F2 ( F3.Dans le premier et dernier cas, l’incertitude n’intervient qu’a un unique

moment, la periode ou la filtration evolue. Ces deux arbres representent desprocessus aleatoires qui, pris en compte dans un probleme d’optimisation,seront consideres comme des processus a deux etapes. A l’oppose, l’arbrecentral represente un processus aleatoire qui fait apparaıtre l’informationau fur et a mesure : le probleme d’optimisation associe compte 4 etapes.La presence de branchements a chaque periode, et plus encore a chaquenœud, est la garantie d’une evolution dans l’apparition de l’incertitude. Cesbranchements permettent la formulation de probabilites conditionnelles ap-proximant celles auxquelles fera face le decideur a la date t. Ces probabilitesconditionnelles sont essentielles aux decisions.

Agregation de scenarios

Le passage d’un peigne a un arbre possedant de nombreux branche-ments est obtenu par agregation de scenarios partiels. L’agregation consistea remplacer des realisations d’un scenario par celles d’un autre du fait deleur proximite. Par exemple, une agregation des scenarios (ξ0, 2, 4, 6) et(ξ0, 2.1,−2, 5) peut consister a remplacer la valeur ξ1

1 = 2 par la valeurξ2

1 = 2.1. Nous pourrions envisager d’utiliser une nouvelle valeur en placedes ξ1

1 et ξ21 comme par exemple leur esperance. Cependant, nous n’explo-

rons pas ces possibilites dans la presente these. Nous nous limitons a choisirune des valeurs de l’arbre.

L’agregation de scenarios consiste a choisir des sous-scenarios a evincerou a conserver. Nous pouvons voir cela comme realiser des partitions Pt achaque periode t avec la particularite que la partition en t est un raffinementde celle en t−1. Les partitions sur S, de taille finie, sont consideres comme latraduction des filtrations sur Ω. Pour mieux comprendre le deroulement decette agregation nous l’illustrons a travers les differentes figures suivantes.Dans la figure 6.4, nous representons un peigne initial et un exemple deraffinement.

Nous appelons les parties de la partition des ensembles de decision. Ce

48


Un peigne

mmmmmmmm

mmmmmmmm

mmmmmmmm

JJJJJJJ

@@@@@

"""""

bbbbb

````m

t = 0 t = 1 t = 2 t = 3

Un arbre equilibre

mmmmmmmm

````

````

````

````mmmm

!!!!!

aaaaa

!!!!!

aaaaa

m

m

ZZZZZ

m

t = 0 t = 1 t = 2 t = 3

Un plumeau

mmmmmmmm

JJJJJJJ

@@@@@

"""""

bbbbb

````mmm

t = 0 t = 1 t = 2 t = 3

Fig. 6.3: Differents types d’arbres d’evenements49


mmmmmmmm

mmmmmmmm

mmmmmmmm

JJJJJJJ

@@@@@

"""""

bbbbb

````m

t = 0 t = 1 t = 2 t = 3

Fig. 6.4: Partitionnement des nœuds d’un peigne pour agregation

mmmmmmmm

mmmmmmmm

mmmmmmmm

JJJJJJJ

@@@@@

"""""

bbbbb

````m

t = 0 t = 1 t = 2 t = 3

vvvvvvvv

vvvv

v

v

Fig. 6.5: Les (sous-) scenarios references dans le peigne en cours d’agre-gation

nom prendra tout son sens dans la partie IV. Au sein de ces parties il fautmaintenant choisir un unique representant de l’ensemble de decision, quenous appelons (sous-)scenario reference, comme illustre dans la figure 6.5.

Un sous-scenario reference de la periode t finit par un nœud noir enperiode t. Il suffit maintenant de supprimer les nœuds qui ne finissent pasun sous-scenario reference et de mettre a jour les arcs afin d’avoir un arbrequi ne soit pas un peigne, comme illustre en figure 6.6.

50


mmmmmmmm

HHHHH

HHHHH

HHHHH

HHHHH

mmmm

@@@@@

@@@@@

m

m

````m

t = 0 t = 1 t = 2 t = 3

vvvvvvvv

vvvv

v

v

Fig. 6.6: L’arbre apres agregation au sein des ensembles de decision

Reduire le nombre de nœuds c’est faire un choix parmi les realisations duprocessus aleatoire. Il faut associer aux realisations restantes de nouvellesprobabilites πnt . Par abus de langage nous parlerons parfois de probabilited’un nœud en se referant a la probabilite de la realisation associee a unnœud. Nous discutons plus loin de la valeur a attribuer aux πnt .

La premiere fois que nous avons utilise un arbre, il etait une illustrationd’un processus aleatoire connu. Maintenant nous faisons le chemin inverseet definissons un nouveau processus stochastique ξtTt=0 base sur la seriede partition (Pt)T−1

t=0 et caracterise par la nouvelle mesure de probabilite P.

La technique d’agregation a besoin de deux elements pour fonction-ner : un moyen de calculer la distance separant deux scenarios et un critered’arret. Nous utilisons dans la suite la meme mesure de distance que dansle cas a deux etapes. Nous nous concentrons dans un premier temps surl’agregation a l’etape 1, et supposons connaitre le nombre R de nœuds fi-naux voulus. Nous avons une collection S de N sous-scenarios σt, et nousdesirons trouver la meilleure approximation P de P. L’ensemble R des in-dices des R scenarios est inclus dans l’ensembleN = 1, . . . , N. Le supportde P est l’ensemble ΩR = σnTn∈R ⊂ Ω. Nous avons bien sur πn = 0 pourtout n ∈ N \ R.

Avec c : Ω × Ω 7→ R une metrique basee sur une norme ‖ · ‖p, nouspouvons calculer la distance separant les deux mesures de probabilites gracea d1. La distance minimale entre deux distributions discretes se formule, sur

51


base des equations (6.7) a (6.10), comme suit :

d1(P, P) = minp

N∑n,m=1

c(σn, σm)pnm | pnm ≥ 0,N∑n=1

pnm = πm,

N∑m=1

pnm = πn.

(6.17)Nous souhaitons trouver un ensemble R de cardinalite R, et une mesure

de probabilite P de telle sorte que la distance d1(P, P) soit minimale :

κ(P, P) = minR,P

d1(P, P) (6.18)

Theoreme 2. Le probleme (6.18) est equivalent a un probleme de p-medianes.

Demonstration. Supposons que dans un premier temps l’ensemble R =(r1, r2, . . . , rR) soit donne. Nous supposons que les elements sont tries telsque rν < rν+1 pour ν < R. Le probleme est donc de trouver P telle que ladistance soit minimale. Cela revient a resoudre le probleme en dimensionfinie et a variables π et p :

minπ,p

∑(n,m)∈N 2

c(σn, σm)pnm

s.c.∑n∈N

pnm = πm, ∀m ∈ N et∑m∈N

pnm = πn, ∀n ∈ N

pnm ≥ 0, ∀(n,m) ∈ N ×N∑m∈N

πm = 1,

πm ≥ 0,∀m ∈ R et πm = 0,∀m ∈ N \ R.

Une solution optimale de ce probleme de transport de masse est fa-cilement trouvee grace aux proprietes (6.9) et (6.10). Tout d’abord nousconstruisons des sous-ensembles de l’ensemble N en associant chaque sce-nario d’indice n ∈ N a son plus proche scenario d’indice rν ∈ R au sens dec.

Dν = n ∈ N | rν = arg minm∈R

c(σn, σm), ν = 1, . . . R.

L’ensemble des Dν ne forme pas necessairement une partition deN puisqu’ilpeut y avoir des doublons, c’est-a-dire un element n qui appartient a plusd’un ensemble Dν . Nous allons completer la definition des ensembles Dν enfixant que si n ∈ Dν ∪ Dν′ avec ν < ν ′ alors :

Dν′ = Dν′ \ n.

52


A noter que rν ∈ Dν . Sur base de (6.10), le minimum du probleme de trans-port de masse est atteint avec :

πm =

∑n∈Dν

πn pour les elements m = rν de R

0 sinon.

pnm =

πn si n ∈ Dν et m = rν

0 sinon.

Ainsi, le probleme de trouver l’ensemble R de cardinalite R et la me-sure de probabilite P dont la distance a P est minimale est le probleme deprogrammation lineaire avec variables entieres et reelles suivant :

minp,b

∑(n,m)∈N 2

cnmpnm (6.20a)

s.c.∑m∈N

pnm = 1, ∀n ∈ N (6.20b)

0 ≤ pnm ≤ bm,∀(n,m) ∈ N ×N , (6.20c)

bm ∈ 0, 1,∀m ∈ N , (6.20d)∑m∈N

bm = R, (6.20e)

ou cnm = πnc(σn, σm). Ce probleme est connu dans la litterature comme un

probleme de p-medianes. Il consiste a definir, dans notre cas, R medianesparmi N possibilites, et a affecter chaque n a la plus proche mediane. m estune mediane uniquement si bm = 1.

Les auteurs de [47] ont pour leur part traite le probleme de transport demasse comme un probleme de localisation2, qui se distingue d’un problemede p-medianes uniquement par l’ajout d’un cout fixe a l’utilisation d’unemediane, le nombre final de medianes etant a definir.

Le probleme de p-medianes resolu, nous construisons les ensembles dedecision comme suit. Soit l’ensemble des indices de scenarios reference :

R = r ∈ N | br = 1.

On pose que les elements rν deR sont tries par ordre croissant. Pour chaquerν , on definit Dν le ν eme ensemble de decision par

Dν = n ∈ N | rν = arg minm∈R

cnm. (6.21)

2En anglais, on parle de facility location problem.

53


Le probleme de p-medianes est NP-difficile [53]. Cependant, il existede puissants algorithmes pour generer des solutions optimales (voir parexemple une liste de methodes dans [73]). Une solution optimale n’etant pasnecessaire, nous pouvons nous tourner vers des heuristiques comme cellesdeveloppees successivement dans [43, 44, 45] ou bien, comme nous allonsle faire en partie V, vers une heuristique basee sur une relaxation Lagran-gienne comme dans [23] et couplee a une technique d’arrondi aleatoire3 [72].

Maintenant que la technique a ete presentee pour l’etape 1, il suffit degeneraliser aux autres etapes du probleme :

– La periode 0 n’a pas besoin de partition, car il existe une uniquerealisation possible ξ0 pour la variable aleatoire ξ0.

– Pour permettre la generalisation, supposons qu’a la periode 1, nousavons calcules les ensembles R1 et Dν1 avec ν = 1, . . . R1. Nous allonssupposer que la serie des Rt, qui doit etre strictement croissante, estde la forme suivante : Rt = Rt−1 × qt, avec qt entier, superieur a 1, ett = 2, . . . T − 1.

– En periode 2, nous allons resoudre R1 problemes de p-medianes inde-pendants sur les ensembles de scenarios d’indices appartenant a Dν1 enplace de S. Le nombre de medianes pour chaque probleme independantest de q2. Nous aurons donc R1× q2 ensembles de decision en periode2, soit R2. A noter que la numerotation des ensembles de decision etdes scenarios references ira de 1 a q2 pour le premier sous-ensemble,puis de 1 + q2 a 2× q2 pour le second, et ainsi de suite.

– En periode 3, nous resolvonsR2 problemes de p-medianes independantssur les ensembles de scenarios d’indices appartenant a Dν2 en place deS. Le nombre de medianes pour chaque probleme independant est deq3. Nous aurons donc R2× q3 ensembles de decision en periode 3, soitR3.

– Et ainsi de suite jusqu’en periode T − 1.Il est important de noter que nous avons fait l’hypothese d’une serie de

la forme Rt = Rt−1 × qt. Cela simplifie l’explication, et montre clairementl’augmentation exponentielle du nombre d’ensembles de decision au fur eta mesure du temps. Nous pourrions tout a fait envisager d’autres series,comme par exemple des qt tous identiques (nous serions alors en presenced’une serie geometrique), ou bien des qνt distincts pour chaque sous-ensembleν = 1, . . . Rt−1. Enfin, il est aussi possible d’avoir un autre critere d’arretdans la procedure de calcul de p-medianes, comme par exemple une bornesur

∑(n,m)∈N 2 cnmpnm : lors du calcul iteratif, nous choisissons 1 mediane,

3En anglais, on parle de randomized rounding.

54

Application de la politique de decision

puis 2, puis 3, et lorsque la distance totale citee precedemment passe endessous d’une certaine limite, nous arretons l’agregation. Nous utiliseronsune telle condition d’arret dans le programme developpe pour resoudre desproblemes par approche programmation stochastique en partie V.

6.4 Application de la politique de decision

Les problemes d’optimisation a deux etapes (6.12) et plus (6.16) sontdes problemes de programmation mathematique a dimension finie lorsquele processus stochastique est discret. Nous considererons dans la suite uni-quement le probleme (6.16) puisqu’il est une generalisation de (6.12). Saresolution nous donne 2 valeurs :

– la commande optimale u∗S = unt | t = 0, . . . T, n = 1, . . . Nt– la valeur optimale de la fonction objectif f ∗S = f(u∗S)Nous notons f ] la solution optimale du probleme sur une representation

exhaustive du processus stochastique.Lorsque la programmation stochastique est utilisee pour resoudre des

problemes a nombreuses etapes, la valeur de f ∗S n’est finalement que peuinformative, car l’erreur d’approximation peut etre tres grande du fait de lareduction drastique que nous avons appliquee au peigne, qui lui-meme estune representation partielle de Ω si le processus aleatoire est continu.

Il semble interessant de proceder a une validation empirique, c’est-a-dire calculer la valeur moyenne de la fonction objectif lorsqu’on appliquela politique de decision u∗S a un grand nombre de scenarios (beaucoup plusque ce que compte l’arbre). Cette validation empirique pose la question del’operabilite de la politique de decision : Quelle decision prendre lorsqu’unerealisation quelconque est donnee, et surtout si cette realisation n’est paspresente dans l’arbre ?

La maniere de mettre en place la politique de decision est tres peupresente dans la litterature, voire inexistante. C’est pourtant l’objectif fi-nal d’une technique d’aide a la decision que de donner les moyens d’ap-pliquer une decision optimisee. Nous expliquons cette methode ci-dessous.Nous avons a notre disposition les valeurs u∗S , f

∗S ainsi que les ensembles de

decision Dνt et les ensembles Rt calcules a priori. Nous appliquons d’ores et

deja la decision unique u0. Nous souhaitons trouver la bonne valeur un′11 a

appliquer suite a la realisation ξ′1 qui n’est pas presente dans l’arbre. Nousallons rechercher l’indice n′1 tel que :

n′1 = arg minn∈R1

c(ξ′1, ξn1 ) (6.22)

55


Pour trouver un′22 , nous recherchons l’indice n′2 de la meme maniere, mais uni-

quement parmi les indices n ∈ R2 qui verifient a(2, n) = n′1. Nous operonsde la meme facon suite aux realisations σ′ = (ξ0, ξ

′1, . . . , ξ

′T ) pour trouver la

suite de decisions a prendre

u′ = (u0, un′11 , . . . u

n′T−1

T−1 ).

Nous sommes alors en mesure d’evaluer fσ′(u′) la performance de la poli-

tique optimisee pour le scenario σ′.Une validation empirique consiste a realiser cette operation pour un tres

grand nombre de scenarios σ′ ∈ V avec S ⊂ V et de calculer une valeurmoyenne fV . Nous appelons l’ensemble V l’ensemble de validation.

Cette phase de validation est peu discutee dans la litterature, car lesmoyens utilises pour formuler les problemes stochastiques, pour agreger lesarbres, reposent sur des bases theoriques presentant des bornes maximalesd’erreur par rapport a l’optimum. Cependant, ces bornes d’erreur maxi-male sont tres importantes lorsqu’on combine un processus aleatoire sur denombreuses periodes temporelles et un arbre d’evenements qui doit avoirun nombre de scenarios limite. L’effet de la combinaison de telles valeurspour ces parametres est discute dans la prochaine section. Dans l’approcheSPSDR, nous n’avons pas de tels appuis theoriques. Nous nous basons surune validation empirique qui nous permet d’evaluer la qualite de predictiond’une methode, mais aussi de comparer les methodes entre elles. Dans lapartie IV, nous introduisons un cadre de travail precis permettant d’evalueret de comparer des methodes d’optimisation sous incertitude avec de nom-breuses periodes temporelles.

56

Chapitre 7

Les obstacles a la mise enœuvre

Sommaire

7.1 Une difficulte technologique . . . . . . . . . . . . . . . . 58

7.2 Une difficulte methodologique . . . . . . . . . . . . . . 58

Certains problemes sont purement deterministes. D’autres sont resoluscomme tels, alors qu’ils ont des parametres variables. On considere parfoisa tort que ces variations sont faibles, et donc qu’il n’est pas necessaire deles prendre en compte. Seulement, ce n’est pas la variation du parametrequi est importante, mais bien la sensibilite de la solution optimale a ceparametre.

On oppose au terme de sensibilite celui de robustesse. Une solution ro-buste sera moins sensible, en terme d’evaluation a travers la fonction ob-jectif, a une variation d’un parametre qu’une solution deterministe. L’op-timisation sous incertitude est une facon de construire une solution plusrobuste.

Le gain de la prise en compte de l’incertain est indeniable, mais le prix apayer est parfois trop eleve. Il faut maitriser les outils technologiques de for-mulation de tels problemes. Il faut aussi maıtriser l’aspect methodologiquede l’optimisation sous incertitude afin de ne pas tomber dans le piege de ladimension.

Cette section s’interesse a mettre en lumiere deux obstacles majeurs ala mise en place de la programmation stochastique.

57

7. Les obstacles a la mise en œuvre

7.1 Une difficulte technologique

L’integration d’incertitude dans les problemes d’optimisation est encoreconfidentielle, au contraire de l’optimisation deterministe. Le monde de l’op-timisation s’ouvre de plus en plus aux decideurs, et notamment a ceux quine maıtrisent pas les techniques de resolution, grace a des outils simples,et integres. Nous pouvons citer par exemple l’optimiseur d’Excel, qui per-met de resoudre des problemes de programmation lineaire de petite tailletres simplement. Pour des problemes de plus grandes tailles, des outils demodelisation, de plus en plus interfaces, existent. Et l’emploi d’un opti-miseur n’est plus restreint au monde universitaire ou a celui des grandesentreprises, avec par exemple l’apparition de communautes du logiciel librespecialisees dans l’optimisation. La formulation d’un probleme deterministeest maintenant a la portee du plus grand nombre.

L’optimisation sous incertitude, elle, a du retard dans le domaine. Ilexiste quelques outils specialises, mais reserves a une elite. Il est vrai que laformulation d’un probleme d’optimisation sous incertitude n’est pas choseaisee. Prenons le cas de la programmation stochastique, et interessons nousa la formulation d’un probleme deterministe equivalent. Les formulationsdeterministe et deterministe equivalent ne sont pas si eloignees les unes desautres, mais il est necessaire de maitriser nombre de connaissances pourformuler le probleme correctement.

Dans la partie III, nous proposons un outil d’aide a la formulationd’un probleme stochastique. Nous fixons une liste de regles d’ecriture duprobleme deterministe, et sur base d’une information incertaine formuleesous la forme d’un arbre ou tout simplement sur base des probabilites condi-tionnelles, notre outil va transformer le probleme deterministe en deter-ministe equivalent.

7.2 Une difficulte methodologique

Les techniques de modelisation des problemes incertains que sont la pro-grammation stochastique et la programmation dynamique souffrent toutesdeux de ce que Richard Bellman [10, 11] a appele the curse of dimensio-nality. Nous parlerons en francais de la malediction de la dimension. Elledesigne l’augmentation explosive du volume de donnees associees a l’ajoutde dimensions supplementaires dans un espace mathematique. Prenons unexemple simple : 100 observations couvrent l’intervalle [0, 1]. Il faudra 106

observations pour discretiser l’intervalle multidimensionnel [0, 1]3 avec la

58

Une difficulte methodologique

meme precision1. L’ajout de 2 dimensions a l’espace du probleme fait mul-tiplier par 10′000 le nombre d’observations necessaires.

En programmation stochastique, la malediction de la dimension portesur l’aspect temporel et aleatoire du probleme2, c’est-a-dire sur la dimensionde l’espace de probabilite sur lequel est defini le processus stochastique.

L’ajout d’une periode temporelle a un probleme stochastique va aug-menter considerablement sa dimension, pour une discretisation identique.Prenons l’exemple d’un arbre d’evenements ou chaque nœud possede s suc-cesseurs. Cet arbre compte N s

T =∑T

t=0 st = 1+s1−sT

1−s nœuds. L’ajout d’uneunique periode temporelle va multiplier le nombre de nœuds par plus de s,puisque nous passons a N s

T+1 =∑T+1

t=0 st > s × N s

T , pour s > 1. Or, lenombre de variables (et de contraintes) du probleme croit lineairement avecle nombre de nœuds.

L’augmentation de la discretisation d’une variable aleatoire va elle aussiaugmenter considerablement la taille du probleme a resoudre, pour unnombre de periodes temporelles constant. Reprenons l’exemple precedentd’un arbre comptant N s

T nœuds. Le passage a une discretisation en s + 1

valeurs va faire augmenter le nombre de nœuds a N s+1T = 1+(s+1)1−(s+1)T

1−(s+1).

Pour illustrer cette augmentation explosive du nombre nœuds, prenonsun exemple simple avec s = 5 et T = 4. Nous avons alors :

– pour l’arbre d’evenements en question : N sT = 781 nœuds,

– si on discretise avec 1 valeur supplementaire : N s+1T = 1555 nœuds

(de l’ordre de 2×N sT ),

– si on ajoute une periode temporelle : N sT+1 = 3906 nœuds (de l’ordre

de 5×N sT ).

La malediction de la dimension est un obstacle majeur :– d’une part a l’integration de l’incertitude dans les problemes d’opti-

misation avec un grand nombre de periodes. Prenons par exemplele cas d’un probleme de Plan Industriel et Commercial. C’est unprobleme dynamique defini sur 12 periodes (les 12 mois de l’annee)qui requiert une precision importante. Si nous voulions le resoudrepar programmation stochastique, nous definirions alors un problemestochastique gigantesque que nous ne pourrions pas resoudre en untemps raisonnable, ou avec une precision satisfaisante. Il est donc dif-ficile de prendre en compte l’incertitude dans de tels problemes, alorsqu’evidemment elle serait tres utile au decideur.

1Avec des points dans l’espace discretise espaces les uns des autres par la memedistance que celle qui separe les 100 points de l’intervalle [0, 1].

2En programmation dynamique, la malediction porte sur l’espace des etats dusysteme.

59

7. Les obstacles a la mise en œuvre

– d’autre part a l’amelioration de la precision des problemes incertains atravers une forte discretisation du processus aleatoire, qui peut etre degrande dimension3. Prenons l’exemple d’une variable aleatoire reelledefinie sur R5. Si nous desirons discretiser chaque dimension en 10valeurs, et combiner toutes ses valeurs, nous avons 105 possibiliteset ce, uniquement a la premiere etape ! A la seconde periode, avecla meme discretisation, il faut 1010 nœuds, ce qui est probablementune taille maximale pour pretendre a une resolution en un tempsacceptable.

Il est aise de s’en rendre compte en lisant les differentes series de testsreferences dans [68], rubrique Test sets. Le nombre maximum de scenariospris en compte ne depasse pas 104 et le nombre de periodes temporelles estau maximum de 6. Seule une serie depasse ces chiffres, mais elle est utiliseepour le calcul sur un reseau de plusieurs centaines de processeurs.

Le decideur doit faire un arbitrage, et bien souvent le choix est in-termediaire : prendre en compte le maximum de parametres que nous per-met le temps imparti, si tant est que l’on puisse calculer le temps deresolution en fonction de la taille du probleme a priori. L’objectif n’estdonc plus de resoudre un probleme d’optimisation, mais d’optimiser uneformalisation.

Les techniques d’agregation et de reduction de scenarios permettent dereduire la dimension de l’espace de probabilite, mais fait perdre en incer-titude, dans le sens ou l’arbre d’evenements compte de moins en moins debranchements.

Il faudrait donc avoir un maximum d’incertitude avec un minimum descenarios. Nous proposons une solution a ce probleme dans la partie IV. Celapasse par une nouvelle structure d’information, par un processus decisionnelqui ne soit pas calque sur le processus aleatoire.

3En dehors de considerations temporelles.

60

Partie III

Contribution a la mise enœuvre de la programmation

stochastique grace a DET2STO

61

Chapitre 8

Introduction

Dans la plupart des cas, pour formuler un probleme stochastique, ledecideur commence par formuler la version deterministe du probleme. Surbase de cette version deterministe, il construit une version stochastiqueen integrant une variation d’un parametre, et en adaptant les etats et lesdecisions. Il est alors en presence d’un probleme deterministe equivalent,qu’il va falloir resoudre.

Deux difficultes font face au decideur :– Comment resoudre un probleme formule mathematiquement ?– Comment transformer un probleme deterministe en probleme stochas-

tique ?Il existe des outils, plus ou moins techniques, pour formuler mathe-

matiquement et resoudre un probleme, qu’il soit deterministe, ou stochas-tique (dans sa version deterministe equivalent). Nous nous interessons a laclasse d’outils que nous appelons les langages de modelisation algebrique,ou AML1. Ce sont des langages de programmation permettant de decrireet resoudre des problemes d’optimisation. Leur syntaxe est tres proche desnotations mathematiques, et permet donc de formuler de facon concise etclaire des problemes pouvant etre relativement complexes. Les AML tra-duisent la formulation mathematique en un format standard, bien souventMPS, qui sera utilise par un calculateur, ou optimiseur2. Ces derniers sontdes programmes specialises dans la resolution.

L’AML est un pont entre la formulation du probleme du decideur et leprogramme de resolution qu’est l’optimiseur, comme illustre en figure 8.1.

Il permet au decideur de ne pas entrer dans les details de la programma-tion informatique et des methodes de resolution de problemes d’optimisa-tion. Les AML les plus connus sont AMPL [31], AIMMS [16] et GAMS [17].

1pour Algebraic Modeling Language.2termes preferes au franglais solveur, traduction approximative de solver.

63

8. Introduction

Problème

réel

Formulation

mathématique

Formulation

informatique

Solution Décideur

Optimiseur

AML

Fig. 8.1: Le role de l’AML dans la resolution d’un probleme

Grace a ces derniers, le decideur peut facilement resoudre des problemesdeterministes simples a formuler.

La seconde difficulte reside dans la formulation d’un probleme stochas-tique. Ce dernier est beaucoup plus complexe a formuler qu’un problemedeterministe. Il existe pourtant de fortes similitudes entre un problemedeterministe et sa version stochastique. La figure 8.2 illustre ces propos.

Problème

réel

Formulation

mathématique

Formulation

informatique

Solution Décideur

Optimiseur

AML

Problème

réel

Formulation

déterministe

Formulation

informatique

Solution Optimiseur

AML

Formulation

stochastique

Formulation

informatique

Solution Optimiseur

AML

Problème

réel

Formulation

déterministe

Formulation

informatique

Solution Décideur

Optimiseur

AML

Formulation

stochastique

Formulation

informatique

Solution Optimiseur

AML

Similitudes

Similitudes

facile

difficile

Fig. 8.2: Un constat simple et une absence d’outils adequats

D’apres cette illustration, il semble pertinent d’utiliser les similitudesentre les deux formulations afin d’eviter au decideur la difficulte de formulerdirectement le probleme stochastique. Il n’y a malheureusement pas d’outilsimple et accessible qui utilise ces similitudes pour faciliter le travail dudecideur.

La partie III presente la premiere contribution de la these, consistanten :

Des conventions d’ecriture d’un probleme deterministe formule gracea GMPL, sous-ensemble libre du language AMPL. Ces conventionsfacilitent la reconnaissance de similitudes entre la version deterministeet la version stochastique d’un probleme. Sur base de ces conventions,nous proposons une liste de regles permettant la transformation d’uneversion a l’autre.

Un programme informatique libre appele DET2STO qui permet detransformer un probleme deterministe ecrit en GMPL en une version

64

stochastique elle aussi ecrit en GMPL, sous condition qu’il respecteles conventions precedemment citees. Le programme DET2STO, pourdeterministic to stochastic, automatise les regles. Il est ecrit en lan-gage Perl [93] et est mis a disposition gratuite sur internet a l’adressesuivante :

http://www.ordecsys.com/det2sto/rights.html

Une interface sur Internet appelee aml4sp qui permet de realiser latransformation via DET2STO et aussi de resoudre les problemes di-rectement en ligne grace a l’utilisation de l’optimiseur libre glpsol. Lesite internet aml4sp [24], pour algebraic modeling language for sto-chastic programs, permet de realiser l’entierete du processus en ligne,a l’adresse suivante :


La totalite des outils realises et utilises sont libres de droit. L’optimiseurglpsol et le language GMPL font partie du kit de programmation lineairelibre GLPK, pour GNU Linear Programming Kit. L’annexe A apporte desprecisions sur les droits d’utilisation de DET2STO.

Cette contribution a fait l’objet d’une publication [85] dans la revueComputational Management Science. Elle est proposee au chapitre suivantdans sa version finale, en anglais. Afin de faciliter la comprehension, nousfaisons ci-apres un rapide descriptif de l’article :

La section 9.1 presente la formulation d’un probleme deterministe equi-valent sur base de notations tres proches de celles utilisees jusqu’amaintenant dans la these. Pour de plus amples details, voir la listedetaillee des notations dans la section 9.4. L’article s’interesse auxproblemes d’optimisation sous incertitude a contraintes et fonctionslineaires.

La section 9.2 presente une maniere de formuler un arbre d’evenementsa travers une fonction a[t, n, k], qui n’est autre qu’une extension de lafonction a(t, n). Elle permet de retrouver l’indice du keme predecesseurdu nœud (t, n). Nous avons donc a[t, n, 1] = a(t, n). L’ensemble denœuds de l’arbre a la periode t est note S[t]. Enfin, une distinctionest faite entre la probabilite d’un nœud et la probabilite d’un scenario.

La section 9.3 presente un exemple illustrant l’utilisation d’AMPL sur unprobleme simple. Les formulations des problemes deterministe puisstochastique sont proposes. Nous observons de grandes similitudesentre les deux formulations.

65

8. Introduction

La section 9.4 propose une liste de parametres et variables qui peuventetre communs a tous les problemes qui nous interessent. Nous appe-lons ces parametres des primitives. Elles peuvent etre regroupees endeux classes : celles concernant l’arbre d’evenements et les autres. Lapremiere classe permet de manipuler un arbre, en fonction des in-formations donnees par le decideur. Nous proposons deux manieresde representer l’arbre : par des scenarios ou par un processus transi-tionnel. Les primitives concernant l’arbre sont specifiques au type derepresentation, les autres sont generales.

La section 9.5 fait le bilan de toutes les observations precedentes et pro-pose d’ajouter aux outils proposes que sont les primitives une listede conventions d’ecriture du probleme deterministe en AMPL, ouGMPL. Ces conventions permettent d’homogeneiser l’ecriture alge-brique, en vue de la transformation a proprement parler. Cette trans-formation est realisee en appliquant au modele une liste de regles detransformation. La transformation est garantie si le probleme initialutilise les primitives et respecte les conventions enoncees precedem-ment. Ces regles peuvent etre appliquees manuellement, mais nousproposons un programme informatique automatisant le processus.

L’article n’incluant ni le code informatique de DET2STO ni la presen-tation de l’interface AML4SP, ces derniers sont respectivement presentes enannexes A et B.

66

Chapitre 9

Automatic formulation ofstochastic programs via anAML [85]

Contents9.1 Stochastic programming formulation . . . . . . . . . . . 70

9.2 The event tree formulation . . . . . . . . . . . . . . . . 72

9.3 An illustrative example . . . . . . . . . . . . . . . . . . 74

The deterministic model . . . . . . . . . . . . . . . . . 74

The stochastic process . . . . . . . . . . . . . . . . . . . 75

The deterministic equivalent . . . . . . . . . . . . . . . 76

9.4 Primitives on the event tree . . . . . . . . . . . . . . . . 78

Scenario-based representation . . . . . . . . . . . . . . . 78

Transition-based representation . . . . . . . . . . . . . . 81

9.5 Automatic generation of the deterministic equivalentin ampl . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

The two basic components . . . . . . . . . . . . . . . . 88

Building the deterministic equivalent . . . . . . . . . . 89

The case of a transition-based formulation . . . . . . . 91

Extension to variables with time lags . . . . . . . . . . 92

9.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . 92

67

9. Automatic formulation of SP programs via an AML

Introduction

Sequential decision-making under uncertainty is a common situationthat decision-makers face. Stochastic programming is a powerful analyticaltool to support this process. As a scientific field stochastic programminghas been in existence for many years and has received many contributions(see, for example [15, 52] and the website “stoprog.org” for exhaustive refe-rences). Yet this tool is not widely used, mainly because users find it difficultto handle and implement. Indeed, the complexity of implementing stochas-tic programming is considerably higher than in the deterministic case. Forthe latter, algebraic modeling languages, in short aml, make it possible forusers who are not experts in mathematical programming to formulate anddevelop complex problems rapidly and have them solved.

A multistage stochastic programming problem can be interpreted as thecombination of a multistage dynamic model and a discrete time stochasticprocess. If the stochastic process has finitely many states, one can formulatethe stochastic program as a deterministic problem, the so-called determi-nistic equivalent. To build this model, one has to describe the two base com-ponents separately—the deterministic multistage dynamic model and thestochastic process—, and then define variables and constraints contingenton the realization of the stochastic process. This last operation is tedious, ifnot difficult, because the contingent variables and constraints are in greatnumber and must be appropriately hooked to specific events. The deve-lopment of automatic procedures to build this model is an active researchstream in stochastic programming [21, 30]. In any case, the dimension of thedeterministic equivalent is a major issue in stochastic programming. Devi-sing efficient solution methods is still an open field. It is thus important togive the user the opportunity to experiment with solution methods of hischoice.

The present work achieves a two-fold goal. First, we derive rules togenerate event trees in a way similar to [91] for the transition-based and thescenario-based description. Second, we present a script that automaticallygenerates the deterministic equivalent. The script is generic in that it appliesto any problem, provided the user complies with simple formulation rules inthe writing of the base deterministic model and the event tree description.In our approach we use ampl [31], which is one of the available commercialaml. The extension to another aml is conceivable if the language is endowedwith analogous recursive definitions properties.

In [21, 22, 49], the authors propose a black-box approach, whose inputconsists in two files that are provided by the user. The output is the nume-rical solution of the deterministic equivalent. The input files describe the

68

deterministic information and the stochastic part. Data are to be transmit-ted via smps [27, 39], an extension of the mps format [49, 62]. For practicalapplications, even if some aml is used to build the data, this approach isnot as straightforward as it seems : at first, the whole procedure is likely toappear quite tedious and long for practitioners and furthermore, some co-efficients in the deterministic equivalent may be given as complex functionsof deterministic and stochastic data, which cannot be easily translated assuch in smps file. Furthermore, the control the user has on his model isthrough data transmission, with a model building process which is exter-nally defined. Basically, in this approach the model building process is notreally under direct control of the user. For example, the user cannot imple-ment specific resolution algorithm via specific packages or decompositionmethods.

Another approach, the one we choose to develop here, consists of exploi-ting the aml features in order to formulate the full deterministic equivalent,see [91], and having a direct vision and control of this model. Then the usersends the problem to a commercial solver, knowing that nowadays such sol-vers can often handle large linear programming problems. Such an approach,which permits the user to develop the model, is a necessary condition duringthe modeling process. As a matter of fact, in real-life application the deve-lopment of a model of the considered problem is a complex issue involvingthe setting of critical assumptions and approximations (as the choice of theparameters of influence, time horizon, randomness modeling, ...). It is thusan advantage for the user to control and understand the model structureduring this development process.

In the hope of narrowing the gap between users and the available mo-deling and algorithmic tools, we propose some simple techniques to convertmultistage deterministic problems into stochastic programming ones. In thisframework, the deterministic part is entered as a standard ampl model. Thestochastic component is described via a collection of simple recursive for-mulas that allow ampl1 to generate the event tree for the stochastic processoutcomes and compute the associated probabilities. We show that, in ourframework, putting together the deterministic programming problem andthe stochastic information can be made automatic by an appropriate script.We give the rules to write the script in terms of elementary operations. Withour approach, the user is just asked to build the deterministic model andto provide the numerical data relative to the stochastic process. The scriptproduces two files, a model file consisting of the full deterministic equiva-

1In theory, the approach can also be extended to any aml that supports recursivedefinitions.

69


lent, and a data file. With those two files, ampl can build the model andthe instance to be passed to the solver that the user wishes to use.

Our methodology is inspired by the principles exposed in [38]. We be-lieve our proposal meets the main objectives of [38] and offers the useropen access and full control of the deterministic equivalent. Our approachextends some of the ideas that appeared in [33]. There, the authors wereable to show that a portfolio selection model with a million scenario couldbe generated by an aml and the data processed by a structure-exploitingtool called set [32] to feed general purpose optimization codes for decom-position. More recently, a similar scheme has been applied to the analysisof a supply chain management problem [91]. In both cases, the underlyingstochastic process is represented by an event tree and a one-step transi-tion process. However, in many stochastic programming applications thestochastic process is described via scenarios. We thus devised an extensionto that case. The originality of our approach is that it is entirely basedon available functionalities of ampl [31] and gmpl2 [29], a free subset ofampl. Our tool can be freely duplicated.

This paper is organized as follows. Section 2 presents the basic assump-tions which characterize the stochastic optimization models considered inthis paper. Section 3 deals with the modeling of the event tree. Section 4presents a simple example to illustrate the concepts previously introduced.It will also be used in the later sections. Section 5 defines the primitivesthat make it possible to navigate through the tree. In Section 6, we discussthe automatic merging of the linear deterministic optimization problem andthe stochastic information embedded in the event tree to build the so-calleddeterministic equivalent, and we provide an example. In the conclusion, wesummarize our contributions.

9.1 Stochastic programming formulation

Consider the following deterministic dynamic problem

min h0(x0) +T∑t=1

ht(Xt,Ξt) (9.1a)

s.t. ft(Xt,Ξt) = 0, t = 1, . . . , T, (9.1b)

f0(x0) = 0, (9.1c)

gt(Xt,Ξt) ≤ 0, t = 1, . . . , T, (9.1d)

g0(x0) ≤ 0, (9.1e)

2for Gnu MathProg Language

70

Stochastic programming formulation

where Xt = (x0, x1, . . . xt), with xt ∈ Rpt , is a decision variable and Ξt =(ξ1, . . . ξt), with ξt ∈ Rqt , is a parameter. The equality constraints (9.1b)and (9.1c) are usually associated with the dynamics of the problem. Ingeneral, ft, f0, gt and g0 are vector-valued functions. Some problems mayinvolve decision variables with delayed effect. To account for the time lag,one must use doubly indexed variables, e.g. xt,t+k, to express the fact thatthe decision is taken at time t and takes effect at time t + k. For the sakeof simplicity, we do not consider this notational extension in the main text.For more details, see subsection 9.5 or [91].

A stochastic version of Problem (9.1) is as follows

min h0(x0) + Eξ

T∑t=1

ht(Xt,Ξt)

(9.2a)

s.t. ft(Xt,Ξt) = 0, t = 1, . . . , T, (9.2b)

f0(x0) = 0, (9.2c)

gt(Xt,Ξt) ≤ 0, t = 1, . . . , T, (9.2d)

g0(x0) ≤ 0, (9.2e)

where, in this stochastic counterpart, the parameter Ξt is a stochastic pro-cess. In that general framework, the constraints are required to hold in analmost sure sense.

In the sequel, we shall use the concept of scenario.

Definition 1. Each scenario ω is a full realization of the random processΞT , namely

ΞT (ω) = (ξ1(ω), . . . , ξT (ω)).

Similarly,

Ξt(ω) = (ξ1(ω), . . . , ξt(ω)).

When the number of scenarios is finite, Problem (9.2) becomes a regularfinite-dimensional mathematical programming problem. Thus, we posit theassumption :

Assumption 1. We assume that the process ΞT has a finite number Nof scenarios ω ∈ Ω = ω1, . . . , ωN. Scenario ω has an occurrence pro-bability πω, with

∑ω∈Ω πω = 1. Furthermore, this stochastic process ΞT is

independent of the decision vectors Xt.

It can be seen that in Assumption 1 the scenarios can be identified byarbitrary alphanumeric codes. For the sake of simpler notation, one oftenchooses ωi = i and this is what we use in the sequel. Nevertheless, for

71


clarity purposes, we shall sometimes keep with the more general notationωi to stress the fact that we are dealing with a scenario.

A fundamental issue is the handling of the information structure, namelywhat is known at period t when decision xt, associated with this period, ismade. We assume the following structure :

Assumption 2. In period t, the history of the stochastic process is knownup to its current realization ξt. This means that the decision-maker is in-formed of the streams Ξt and Xt−1. However, the decision-maker has onlyprobabilistic knowledge of the future evolution ξt+1, . . . , ξT , conditionally tothe past history Ξt.

The decision process has then the form :

decision

x0

→ observation

Ξ1

→ decision

x1

· · · → decision

xT−1

→ observation

ΞT

→ decision

xT

The deterministic equivalent To account for Assumption 2, the va-riable Xt is formally expressed as the function Xt(Ξt). We obtain the follo-wing version of the deterministic equivalent

min h0(x0) +∑ω∈Ω

πω

[T∑t=1

ht(Xt(Ξt(ω)),Ξt(ω))

](9.3a)

s.t. ft(Xt(Ξt(ω)),Ξt(ω)) = 0, t = 1, . . . , T, ω ∈ Ω, (9.3b)

f0(x0) = 0, (9.3c)

gt(Xt(Ξt(ω)),Ξt(ω)) ≤ 0, t = 1, . . . , T, ω ∈ Ω, (9.3d)

g0(x0) ≤ 0. (9.3e)

However, the explicit formulation of this deterministic equivalent as afunction of the decision variables Xt(Ξt(ω)) and of the stochastic processΞt(ω) along the N different scenarios is not a straightforward issue. Problem(9.3) is not a standard mathematical programming formulation in finitedimension. The transformation into a finite dimension problem can be donevia an event tree representation that we discuss in the next section.

9.2 The event tree formulation

Under Assumption 2, the random data can be represented on an eventtree. Without loss of generality, the tree is assumed to be rooted at a singlenode in period 0. The arcs only link nodes in successive time periods. Anode in period t has a unique predecessor in period t − 1, but possibly

72

The event tree formulation

several successors in time t + 1. We can univocally define a node of theevent tree as a pair (t, n), n ∈ St, where St is the set of indices of the nodesat period t. Each node (t, n) on the tree has an unconditional probabilityPt,n of being visited by the stochastic process. Let us furthermore define Nt

as the cardinality of St, i.e. Nt = |St|. Note that Nt ≤ N, for 0 ≤ t ≤ Tand NT = N .

To navigate in the event tree, one has to define a predecessor functionthat identifies the node that immediately precedes the current node. To thisend, we introduce the concept of predecessor function a(t, n, k) which mapsthe current node (t, n) to the index of its predecessor node in period t− k,along the unique path that goes from the root (0, 1) to the node (t, n). Usingthis concept, a scenario i, that ends at node (T, i), is uniquely associatedwith the sequence of nodes(

(0, 1), (1, a(T, i, T − 1)), . . . , (T − t, a(T, i, t)), . . . , (T − 1, a(T, i, 1)), (T, i)

)(9.4)

Let us consider Ξt(ωi) and Xt(Ξt(ωi)) the realizations of the stochasticprocess and of the decision variables along the scenario ωi. (Recall that weidentify ωi with its index i.) Denoting the unique node that scenario ωicrosses at time t as (t, ni) = (t, a(T, i, T − t)), with a(T, i, T − t) ∈ St, onecan introduce the notation

Ξt(ωi) = Ξt,ni := (ξ1,a(t,ni,t−1), . . . , ξt−1,a(t,ni,1), ξt,ni), (9.5)

Xt(Ξt(ωi)) = Xt,ni := (x0,1, . . . , xt−1,a(t,ni,1), xt,ni), (9.6)

with the decision variables xt,ni and the random process value ξt,ni associa-ted with the different nodes of the event tree. We can thus formally replaceΞt(ωi) and Xt(Ξt(ωi)) by Ξt,ni and Xt(Ξt,ni).

Along these lines, the deterministic equivalent is formulated as the finitedimensional problem

min h0(x0,1) +T∑t=1

[∑n∈St

Pt,n ht(Xt,n,Ξt,n)

](9.7a)

s.t. ft(Xt,n,Ξt,n) = 0, t = 1, . . . , T, n ∈ St, (9.7b)

f0(x0,1) = 0, (9.7c)

gt(Xt,n,Ξt,n) ≤ 0, t = 1, . . . , T, n ∈ St, (9.7d)

g0(x0,1) ≤ 0. (9.7e)

It can thus be seen that the components necessary to define the deter-ministic equivalent (9.7) are the following :

73


1. The time horizon T .

2. The parameters describing the event tree, namely

St : set of node indices at period t, (9.8)

a(t, n, k) : index of the pred. of node (t, n) in period t− k.(9.9)

3. The stochastic process values and the node probabilities, formallygiven by

ξt,n : random process value at node (t, n), (9.10)

Pt,n : unconditional probability of visiting node (t, n). (9.11)

4. The deterministic parameters.

5. The variables (in general, hooked on nodes).

6. The objective and the constraints (in general, hooked on nodes).

Item 1 is read from the model file for the deterministic problem. Items2 and 3 are provided by special files. The user is not supposed to edit(or even to look at those files). However, in the case of a transition-basedrepresentation (see Section 9.4), the stochastic process values are problemdependent. It may be necessary to compute them and the user has to providethe relevant formulas. The last 3 items are modifications and extensions ofthe deterministic model, according to the information introduced in items2 and 3.

The key points of the paper are :– The model information (not the data) in items 2 and 3 is independent

of the problem (to the exception of special process value computationin a transition-based representation of the event tree).

– The user can rely on a script to create items 4, 5 and 6 from thedeterministic problem and the information in items 2 and 3.

9.3 An illustrative example

The deterministic model

To illustrate problem (9.1), we propose the simple deterministic problem

min (x2 − x2)2 (9.12a)

xt = xt−1 + ut−1 − ξt, t = 1, 2, (9.12b)

0 ≤ ut ≤ bt, t = 0, 1, (9.12c)

x0 = x0. (9.12d)

74

An illustrative example

The decision variables are xt and ut, which can be respectively interpretedas state and control variables. The parameters are x0, x2, bt and ξt. Theampl formulation and the data file of the deterministic problem are givenin Figure 9.1.

#-------------------------------------## Model for the deterministic problem ##-------------------------------------#

param T; # number of periods (time horizon)set TIME := 0..T;set TIME1:= 0..T-1;set TIME2:= 1..T;set TIME3:= T;set TIME4:= 0;param x0 >= 0; # initial stateparam xTobj >= 0; # objective for the stateparam b TIME1 >= 0; # bound for the control at each periodparam xiTIME2 ; # perturbationvar x TIME >= 0; # state of the system at each periodvar u TIME1 >= 0; # control for each period# Objective functionminimize slack: sumt in TIME3 (x[t] - xTobj)^2;# System dynamicssubject to timedynamics t in TIME2: x[t] = x[t-1] + u[t-1] - xi[t];# Bound for the control variablesubject to timebound t in TIME1: u[t] <= b[t];# Initial state of the systemsubject to initial t in TIME4 : x[t] = x0;

#------------------------------------## Data for the deterministic problem ##------------------------------------#

param T := 2; # number of periods (time horizon)param x0 := 0; # initial stateparam xTobj := 10; # objective for the stateparam b := 0 10 1 10; # bound for the control at each periodparam xi := 1 8 2 12; # perturbation

Fig. 9.1: Model and data for the deterministic problem in ampl

The stochastic process

As in Section 9.1, we introduce randomness in the problem via the pa-rameter ξt. The process has three periods (0, 1, 2). The stochastic process

75


is defined for periods 1 and 2, as period 0 constitutes in fact an auxiliaryinitial period. There are two transitions per period. Figure 9.2 displays aclassical representation of the process via scenarios on an event tree.

QQQQ

H

L

H

L

H

L

PPPPPP

PPPPPP

Scenario ξ1 ξ2 π

HH 8 12 0.36

HL 8 10 0.24

LH 6 10 0.24

LL 6 8 0.16

Fig. 9.2: Stochastic process in the illustrative example

We will show in the next section how this process can be representedin two ways, either by scenarios or by transitions and how a deterministicequivalent can be coupled with both representations.

The deterministic equivalent

For this example, along the lines of (9.7) and assuming that the para-meters (9.8)-(9.11) are known, the deterministic equivalent can be formallywritten as

min∑n∈S2

P2,n (x2,n − x2)2 (9.13a)

s.t. xt,n = xt−1,a(t,n,1) + ut−1,a(t,n,1) − ξt,n, t = 1, 2, n ∈ St,(9.13b)

0 ≤ ut,n ≤ bt, t = 0, 1, n ∈ St, (9.13c)

x0,1 = x0. (9.13d)

The ampl formulation3 of this deterministic equivalent is displayed inFigure 9.3. It clearly appears now that the main difficulty is the automa-tic computation of parameters (9.8)-(9.11) from the deterministic modeland the stochastic process description. This issue is addressed in the nextsections.

3 The functions nodeprob[·,·], NodeSet[·] and kancest[·,·,·] that appear in thatformulation will be defined in the next sections.

76

An illustrative example

#--------------------------------------------------## Generated model for the deterministic equivalent ##--------------------------------------------------## PARAMETERS.param T;set TIME := 0..T;set TIME1:= 0..T-1;set TIME2:= 1..T;set TIME3:= T;set TIME4:= 0;## PROBABILISTIC SECTION OF THE MODEL# insert here the formulas to compute the functions relative# to the event tree (Set of nodes, k-ancestor function, etc.)# See next sections.#param x0 >= 0;param xTobj >= 0;param b TIME1 >= 0;param xit in TIME2,n in NodeSet[t];

# VARIABLES.var x t in TIME, n in NodeSet[t]>= 0;var u t in TIME1,n in NodeSet[t]>= 0;

# OBJECTIVE FUNCTION.minimize slack: sumt in TIME3,n in NodeSet[t]

nodeprob[t,n]*((x[t,n] - xTobj)^2);

# CONSTRAINTS.subject to timedynamics t in TIME2, n in NodeSet[t]:

x[t,n] = x[t-1,kancest[t,n,1]] + u[t-1,kancest[t,n,1]] - xi[t,n];subject to timebound t in TIME1, n in NodeSet[t] : u[t,n] <= b[t];subject to initial t in TIME4, n in NodeSet[t] : x[t,n] = x0;

Fig. 9.3: The deterministic equivalent problem in ampl

77


9.4 Primitives on the event tree

We discuss two ways to describe an event tree and we give the correspon-ding parameters and auxiliary functions. In the first case, the base conceptis a scenario. The scenarios are described recursively, starting from an ini-tial scenario. A new scenario is linked to an existing one, which becomes itsparent scenario. The scenario description includes the values taken by thestochastic process. In the second approach, the base concept is the tran-sition process. Starting from the root node, the set of possible transitionsrecursively defines the nodes in the future periods. The index of a node inperiod t is thus associated with the state of the process. Contrary to thescenario description, the event tree and the values taken by the stochasticprocess are not given explicitly ; they have to be built from base information.

The scenarios provide an explicit description of the event tree and, inparticular, the values taken by the stochastic process along the scenariosare explicitly given.

The transition-based approach is well-fitted for a discrete-time stochas-tic process with a known finite one-step transition distribution. This ap-proach can be furthermore exploited to implement complex discretizationprocedure of underlying random variables (see for example [91]). The scenario-based formulation is usually the output of a complex procedure aiming toapproximate a continuous time and state process by a discrete event treethrough Monte-Carlo simulation and scenario reduction schemes whose des-cription is out of the scope of this paper. See for instance [94] or [65].

The two approaches will now be described in detail. From here on, wechoose to insert the argument of a function within square brackets ‘[’ and‘]’. This notation matches that which is in force in the algebraic modelinglanguage ampl, which we use to model and solve the examples (see [91]).

Scenario-based representation

The general setting

As previously defined, a scenario is a realization of the underlying sto-chastic process, from t = 0 to the horizon t = T . The first scenario in thelist is often named the base scenario : all other scenarios will be recursivelydefined with respect to this base scenario.

In fact, it is useful to characterize how scenarios are related to each other.First, from the definitions, it is directly seen that two scenarios ω[i] and ω[j]may coincide up to a certain time t′, but if these scenarios are distinct att′, they are disjoint for all periods t > t′. In contrast, if two scenarios are

78

Primitives on the event tree

identical in period t, they are indistinguishable for all periods t′ < t. Thiscan be interpreted by considering that ω[i] is the parent scenario for scenarioω[j] and the meeting period is t′. Formally, we define two parameters σ[i]and τ [i], with the understanding that σ[i] is the index of the parent scenariofor scenario ω[i], and τ [i] is the meeting period with its parent scenario. Itis worth noting that under this interpretation, the set S[t] can be viewedas the set of distinct scenarios at time t.

We recall that the user gives the probabilities π[n] associated with eachscenario ω[n] = n. The values taken by the stochastic process along scenarioω[n] are denoted by Ξ[t, ω[n]] and are entered as data, or computed bygeneric formulas. The set of node indices at each period is then computedas

S[t] =

1 if t = 0,n | ω[n] ∈ Ω, τ [n] < t if 1 ≤ t ≤ T.

(9.14)

Under this interpretation, for each time period t ≤ T , the set S[t] isviewed as the set of scenarios which have diverged at some time t′ < t. Thisscenario description is illustrated via the example, in Figure 9.4 below.

t = 0 t = 1 t = T = 2τ σ

0 1

1 1

0 1

1 3

1 1 1aaaaaa2@@@@@@3 3aaaaaa4

S[0] S[1] S[2]= = =1 1, 3 1, 2, 3, 4

Fig. 9.4: Scenario description for the illustrative example

Furthermore, for each node (t, n), the unconditional probability of beingvisited by the stochastic process can be recursively computed as follows fromthe scenario probabilities

P [t, n] =

π[n] if t = T,

P [t+ 1, n] +∑

m∈S[t+1]τ [m]=t, σ[m]=n

P [t+ 1,m] if 0 ≤ t < T. (9.15)

79


The one-period predecessor function a[t, n, 1] is defined by

a[t, n, 1] =

n if t > τ [n] + 1,σ[n] if 1 ≤ t ≤ τ [n] + 1,

(9.16)

with a[t, 1, 1] = 1, for 1 ≤ t ≤ T .The k-period predecessor function a[t, n, k] can afterwards be defined as

a[t, n, k] =

a[t, n, 1] if k = 1,

a[t− 1, a[t, n, 1], k − 1] otherwise,(9.17)

for all 1 ≤ k ≤ t.

Information provided by the user

The set of scenarios2 : 1, . . . , NScenario probabilities : π[n] for 1 ≤ n ≤ NParent scenario : σ[n] for 1 ≤ n ≤ NMeeting period : τ [n] for 1 ≤ n ≤ NProcess values : ξ[τ [n] + 1, n], . . . , ξ[T, n] for 1 ≤ n ≤ N .

Generic information

Set of nodes : S[t] computed by formula (9.14)Node probabilities : P [t, n] computed by formula (9.15)Predecessor function : a[t, n, 1 computed by formula (9.16)k-predecessor function : a[t, n, k] computed by formula (9.17).

Notation in the AMPL models

We have chosen the following ampl notations

The set of scenarios : 1, . . . , N → ScenScenario probabilities : π → scenprobParent scenario : σ → parentMeeting period : τ → meetProcess values : ξ → xiSet of nodes : S → NodeSetNode probabilities : P → nodeprobk-predecessor function : a → kancest.

2In the present ampl file, the scenarios can be alpha-numerically named, implying afew simple changes, the most important being S[0] = root instead of 1.

80


The corresponding ampl set of instructions is displayed in Figure 9.5.With this scenario-based description, the deterministic equivalent is ea-

sily obtained from the deterministic model by making the variable x andthe parameter ξ contingent on the nodes (t, n) of the tree represented inFigure 9.2. The ampl formulation of the deterministic equivalent has beengiven in Figure 9.3.

One notices that the k-ancestor function kancest[·, ·, ·] and the set ofindices NodeSet[·], that are used in the model are not defined in Figure 9.2(see footnote 3, page 76). These functions are defined via a set of genericampl instructions that will be appended to the deterministic file by anautomatized process to be described in the next section. Furthermore, in theproposed ampl formulation without loss of generality, we formally definethe different sets of time periods involved in the problem definition. This isa convention that will be explained in section 6.

Transition-based representation

The general setting

In the transition-based representation, the user describes the stochasticprocess by a one-step transition process from one period to the next fullyexplained in this section. This information is used to build the tree and tocompute the probabilities and the stochastic process values to be assignedat each node. It is usually the case that the process value at a given nodein t + 1 depends on two elements. First, it depends on the history of thestochastic process until t, namely Ξ[t]. Second, it also depends on the natureof the transition from t to t + 1. We thus assume that the description ofthe one-step transition process from a node in period t to a node in periodt+ 1 is made via the following functions

– f [t] := number of transitions from any node at period t4,– p[t, j] := one-step transition probability of transition j ∈ 1, . . . , f [t],– ε[t, j] := one-step random factor corresponding to transition j ∈1, . . . , f [t].

The event tree is then built as follows. At period t, the nodes are numberedfrom 1 to N [t] going from top to bottom : node (t, n) is the n-th node fromthe top in period t. In this way, we directly find S[t] = 1, ..., N [t]. The

4 In this paper, we restrict our presentation to the symmetric case where the num-ber of transitions depends only on the time period. However, models with asymmetricevent trees can be handled. They involve computed parameters f [t, n], contingent on theinformation (probability, value of the stochastic process) available at node (t, n). Thiscase has been treated in [91].

81


#------------------------------------------------------------------## Computation of the primitives: the scenario-based representation ## The formulas ##------------------------------------------------------------------### DATA STATEMENTset Scen;param scenprob Scen;param parent Scen symbolic in Scen union ’root’;param meet Scen;## GENERIC FORMULASset NodeSet t in 0..T:= if t = 0 then ’root’

else s in Scen: meet[s]<t;param ancest t in 1..T, n in NodeSet[t]symbolic in Scen union ’root’:=if t = 1 then ’root’

else if t > meet[n] + 1 then nelse parent[n];

param kancest t in 1..T, n in NodeSet[t], k in 1..tsymbolic in Scen union ’root’:=if t = 1 or k = 1 then ancest[t,n]

else kancest[t-1,ancest[t,n],k-1];set Reverse := T..0 by -1;param nodeprob t in Reverse, n in NodeSet[t]:=if t = T then scenprob[n] else if t = 0 then 1 else nodeprob[t+1,n]+ summ in NodeSet[t+1]: meet[m]=t and parent[m]=n nodeprob[t+1,m];

#------------------------------------------------------------------## Computation of the primitives: the scenario-based representation ## The data ##------------------------------------------------------------------### data concerning the scenariosset Scen := hh hl ll lh;param :meet parent scenprob :=hh 0 root .36hl 1 hh .24ll 0 root .16lh 1 ll .24 ;## data concerning the stochastic processparam xi : hh hl ll lh :=1 8 . 6 .2 12 10 8 10 ;

Fig. 9.5: Event tree parameters for a scenario-based representation

82


number of nodes at period t is recursively computed by

N [t] = N [t− 1]f [t− 1], (9.18)

with N [0] = 1, where f [t] is the number of branches emanating from eachnode at period t. In this formulation, the one-period predecessor functiona[t, n, 1] is recursively defined by

a[t, n, 1] =

a[t, n− 1, 1] if n ≤ a[t, n− 1, 1]f [t− 1],

a[t, n− 1, 1] + 1 otherwise,(9.19)

with

a[t, 1, 1] = 1, for 0 < t ≤ T,

a[t, n, 0] = n, for 0 ≤ t ≤ T, n ∈ S[t].

Then we recursively define the general k-period predecessor function with(9.17).

We also need to identify the transition index j that led from the previousnode (t−1, a[t, n, 1]) to the actual node (t, n). It can be formally computedby the auxiliary function `[t, n] defined as

`[t, n] = n− (a[t, n, 1]− 1)f [t− 1]. (9.20)

Using the primitives (9.19) and (9.20) one may write

ξ[t, n] = q[Ξ[t− 1, a[t, n, 1]], ε[t− 1, `[t, n]]], (9.21)

where q[·, ·] is a given function. According to (9.21), it can be seen thatthe random process value ξ[t, n] is computed based on past events Ξ[t −1, a[t, n, 1] and on the one step transition process ε[t− 1, `[t, n]], correspon-ding to the transition leading to node (t, n).

To illustrate our point, we consider the illustrative example, which is athree-period model (with T = 2) with a symmetric event tree. We representit in Figure 9.6. The uncertainty unfolds in time from left to right. Nodesappearing in the same vertical cut belong to the same time period. At t = 0,there are two branches giving rise to a pair of nodes in t = 1 (f [0] = 2 andN [1] = 2). At t = 1, each node has two branches (f [1] = 2) and there areN [2] = 4 nodes in t = 2. Time t = 2 is the horizon : no branch emanatesfrom those nodes. Furthermore, the transition indices are the following :`[1, 1] = 1, `[1, 2] = 2, `[2, 1] = 1, `[2, 2] = 2, `[2, 3] = 1 and `[2, 4] = 2.

83


t = 0 t = 1 t = T = 2

QQQQQ

1

1

2

11

2

PPPPP

21

2

PPPPP

1

2

3

4N [0] = 1 N [1] = 2 N [2] = 4

Fig. 9.6: Transition-based representation for the example

From our assumptions, for a given node (t, n), the conditional transitionprobabilities depend on the period t and on the transition index j. In thepresent formulation, those probabilities are given and denoted p[t, j]. Often,these probabilities result from the discretization procedure of an underlyingrandom variable (see, for example, [91]). From these transition probabili-ties, the unconditional occurrence probability P [t, n] of node (t, n) can berecursively computed by

P [t, n] =

1 if t = 0,

p[t− 1, `[t, n]]P [t− 1, a[t, n, 1]] if 1 ≤ t ≤ T.(9.22)

Figure 9.7 displays the formulas written in ampl.

Information provided by the user

Number of emanating arcs : f [t], for 0 ≤ t < T,One-step random factor : ε[t, j], for 0 ≤ t < T, j = 1, . . . , f [t],Transition probabilities : p[t, j], for 0 ≤ t < T, j = 1, . . . , f [t].

84


#--------------------------------------------------------------------## Computation of the primitives: the transition-based representation ## The formulas ##--------------------------------------------------------------------### declaration of data given by the user :param transnb t in 0..T-1;param transprob t in 0..T-1, k in 1..transnb[t];

# automatically computed valuesparam nodenb t in 0..T := if t = 0 then 1

else nodenb[t-1]*transnb[t-1];set NodeSet t in 0..T := 1..nodenb[t];param ancest t in 1..T, n in NodeSet[t]:=if t = 1 then 1 else if n = 1 then 1else if n <= ancest[t,n-1]*transnb[t-1] then ancest[t,n-1]else ancest[t,n-1]+1;

param kancest t in 1..T, n in NodeSet[t], k in 1..t:=if t = 1 or k = 1 then ancest[t,n] else kancest[t-1,ancest[t,n],k-1];

param lastmove t in 1..T, n in NodeSet[t]:=n-(ancest[t,n]-1)*transnb[t-1];

param nodeprob t in 0..T, n in NodeSet[t]:= if t = 0 then 1else transprob[t-1,lastmove[t,n]]*nodeprob[t-1,ancest[t,n]];

#--------------------------------------------------------------------## Computation of the primitives: the transition-based representation ## The data ##--------------------------------------------------------------------### data concerning the transitionsparam transnb :=0 2 1 2;param transprob :1 2 :=0 0.6 0.41 0.6 0.4 ;

# data concerning the stochastic processparam epsilon : 0 1 :=0 8 61 4 2 ;

Fig. 9.7: Event tree parameters for a transition-based representation

85


Generic information

Number of nodes : N [t] computed by formula (9.18).Set of nodes : S[t] = 1, . . . , N [t]Predecessor : a[t, n, 1] computed by formula (9.19).k-predecessor : a[t, n, k] computed by formula (9.17).Transition index : `[t, n] computed by formula (9.20).Node probabilities : P [t, n] computed by formula (9.22).

Notation in the AMPL models

In complement to the ampl notations introduced in the scenario-basedapproach, we add the following notations

Number of nodes : N → nodenbNumber of transitions : f → transnbTransition probabilities : p → transprobOne-step random factor : ε → epsilonLast transition index : ` → lastmove.

Computing the values of the stochastic process

We have explained in the general setting that in the transition-based re-presentation, the stochastic process values to be assigned at each node haveto be computed. It can be seen via (9.21) that these values are assumed todepend on the history of the stochastic process and on the nature of the lasttransition. If this dependence is described by a formula, this formula mustbe made contingent on the node of the tree, which is not direct for a user, asthe tree is not externally given (as in the scenario-based approach). To per-mit an automatic computation, we ask the user to modify the deterministicmodel (9.1) by adding the following deterministic equation

ξ[t] = q(Ξ[t− 1], ε[t− 1]), (9.23)

that expresses ξ[t + 1] as a function of the external parameter ε[t]. In theampl deterministic model, ξ[t] will be declared as a variable5, ε[t] as a para-meter and the transition equation (9.23) as a constraint. The parameter ε[t]can be viewed as a pure random effect that is node independent. With such

5These variables will take fixed values on the event tree, a fact that the solver pre-process will use to eliminate them for the solution phase.

86

Automatic generation of the deterministic equivalent in ampl

conventions, the contingent process values will be automatically computedduring the deterministic equivalent generation.

We illustrate this approach with our example. In this example, the sto-chastic process in Figure 9.2 can also be alternatively represented by thetransition function

ξ[t] = ξ[t− 1] + ε[t− 1], (9.24)

with the understanding that ξ[0] = 0 is fixed and ε[t] is the underlyingrandom effect. Table 9.1 displays these data.

outcomes

t = 0 t = 1

ε[t] 8 6 4 2p[t] 0.6 0.4 0.6 0.4

Tab. 9.1: Data on the transition process

We thus reformulate the deterministic problem (9.12) for the exampleas

min (x[2]− x[2])2 (9.25a)

x[t] = x[t− 1] + u[t− 1]− ξ[t], t = 1, 2, (9.25b)

0 ≤ u[t] ≤ b[t], t = 0, 1, (9.25c)

ξ[t] = ξ[t− 1] + ε[t− 1], t = 1, 2, (9.25d)

x[0] = x[0], ξ[0] = 0. (9.25e)

In this formulation, the parameter ξ is treated as a variable, but ε is therandom parameter that triggers the process. The change in the status of ξis purely formal, but it gives a common framework for the description ofprocess via scenario or via transitions. The modification in the deterministicmodel (Figure 9.1) is displayed in Figure 9.8.

9.5 Automatic generation of the

deterministic equivalent in ampl

In this section, we discuss the automatic merging of the deterministicstructure of the optimization problem (f [t], f [0], g[t] and g[0]) and the sto-chastic information embedded in the event tree. We recall here that, while

87


#------------------------------------------------------------------## Computation of the values of the stochastic process ## Extension of the deterministic model ##------------------------------------------------------------------##param xi0 := 0; # initial value for the stochastic processvar xi TIME; # stochastic processparam epsilonTIME1; # underlying randomness#subject to initialstate t in TIME4: xi[t] = xi0;subject to processdynamics t in TIME2: xi[t] = xi[t-1] + epsilon[t-1];

Fig. 9.8: ampl formulation of the dynamics of the perturbation

it is relatively easy to describe the two base components—the underlyingdeterministic model and the stochastic process—, it is tedious to define thecontingent variables and constraints and build the deterministic equivalent.We show in this section how to define a systematic procedure that performsthis. This procedure can then be translated into a script, so that the user iscompletely relieved from the painstaking work. The procedure is simpler inthe case of a scenario-based description of the stochastic process. We shalldetail this case and briefly review the few modifications required to handlethe transition-based case.

The two basic components

The first step in the generation of the deterministic equivalent is thedescription of the two basic components underlying the stochastic model,namely the deterministic structure and the full description of the stochasticprocess via an event tree. This step, which is to be performed by the user,can be summarized as follows :

1. Formulate the underlying deterministic dynamic model as defined in(9.1).– The number of time periods must be defined as a parameter, named

“T”.

2. Enter the information describing the structure and the values of thestochastic process as described in Section 9.4.– To do this, the convention described in subsection 9.4 should be

followed.– The set of scenarios S[T ] must be non-empty, and the first scenario

in S[T] must have no parent scenario. The user must describe atleast one scenario, named scenario 1.

88


Building the deterministic equivalent

The second step consists in building the deterministic equivalent. Thiscan be performed in an automatic fashion provided the deterministic mo-del (9.1) is written according to some simple conventions. We detail firstthe conventions, and describe later the transformation rules that map thedeterministic dynamic problem to the deterministic equivalent.

Notation for the deterministic model

The formulation must comply with conventions. The first convention isthe standard modeling convention in ampl.

Convention 1. Indices are entered as arguments of functions, i.e., theyare delimited by square brackets “[” and “]”. For instance, we write

ft(x0, x1, . . . , xt, ξ1, ξ2, . . . , ξt) asf [t, x[0], x[1], . . . , x[t], ξ[1], ξ[2], . . . , ξ[t]].

The next convention applies to variables and parameters whose valuesare contingent on the nodes of the event tree.

Convention 2. The time index at which the value of the variable or theparameter is fixed is first in the list of indices which influence the value ofthe variable or parameter.

For instance, we write x[t, j], with j representing a location or a producttype, and not x[j, t].

In the declaration phase, one must define the set of all time periods, andpossibly some of its subsets.

Convention 3. Any set of time periods starts with the same characterstring.

Our own convention is to denote TIME as the full set of time periods0, . . . , T. The denomination of any subset of TIME will take the formTIME<exp >, e.g., TIMEa = 2, . . . , T − 1.

In the problem definition (objective and constraints), the following conven-tion is in force :

Convention 4. Time indices in variables and parameters are never repla-ced by constants.

89


For instance, we do not write x[0] = 0, but, in mathematical style,x[t] = 0 | t = 0.

Under these conventions, the mathematical programming formulationcan be obtained from (9.1) by some simple transformations described below.

Transformation rules

The main task in defining the deterministic equivalent consists in pro-perly associating variables and constraints to the different nodes of the eventtree. Furthermore, the objective function has to be reformulated along (9.3).This can be done via the following rules.

Rule 1 (Variable transformation). Replace the variable Xt with the N [t]variables X[t, n], n ∈ S[t]. If a variable has two time indices, only the firsttime index, corresponding to the period when the decision is made, is to betaken into account.

Rule 2 (Parameter transformation). Replace the parameter Ξt with the N [t]parameters Ξ[t, n] where n ∈ S[t].

Rule 3 (Constraint transformation). Replace the constraints

ft(Xt,Ξt) = 0 and gt(Xt,Ξt) ≤ 0

with the N [t] constraints

f [t,X[t, n],Ξ[t, n]] = 0 and g[t,X[t, n],Ξ[t, n]] ≤ 0,

where n ∈ S[t].

Rule 4 (Objective transformation). In the objective, replace

ht(Xt,Ξt) with∑n∈S[t]

P [t, n]h[t,X[t, n],Ξ[t, n]].

Implementing the rules

We propose on the internet6 a script that implements the rules via thesyntactic interpretation language perl [93]. This script is generic and ap-plies to any model and data that comply with our rules7. The script auto-matically generates the corresponding deterministic equivalent. It performs

6The “DET2STO” program. Free program available online at the website :“www.ordecsys.com/det2sto”.

7The authors cannot guarantee that all syntaxes supported by ampl are currentlyunderstood by the script.

90


a syntactic analysis based on regular expressions (see [36]).

Inputs-OutputsThe script counts four input files and two output files. We describe first theinput :

File I.1 describes the deterministic dynamic model structure (9.1) (.modformat in ampl).

File I.2 describes the corresponding numerical data (.dat).

File I.3 describes the stochastic primitives (.mod).

File I.4 describes the numerical data underlying the stochastic process(.dat).

And then the output :

File O.1 describes the deterministic equivalent model structure (9.7) (.mod).

File O.2 describes the corresponding numerical data (.dat).

Script structureFirst, the script generates the deterministic equivalent model, as follows :– Pre-process in order to check the input structure validity.– Declare and define the primitives according to the formulas in sub-

sections 9.4 and 9.4.– Identify declarations of variables and parameters.– Modify the above declarations according to rule 1.– Identify definitions of constraints.– Modify the above definitions according to rule 2.– Identify the definition of the objective function.– Modify the above definition according to rule 3.

In a second phase, the script generates the deterministic equivalent datafile by merging the two numerical data input files.

The rules are simple enough to encode, but, in practice, the user musttake great care to make sure that the input files are consistent and complete.One must keep in mind that there are often many different ways to write amodel in ampl, only some of which are consistent with Conventions 1-4.

Recall that a generated deterministic equivalent model is presented inFigure 9.3.

The case of a transition-based formulation

The reader has certainly noticed that the transition-based formulationis more complicated than the scenario-based one. Indeed, the user has to

91


provide information on the dynamics of the stochastic process as formulasthat can be handled in ampl. The surprising fact is that the deterministicequivalent can still be produced by a script file at a minimal additionaleffort from the user.

The transformation rules differ from the scenario-based approach. Rule1 is replaced by :

Rule 5 (Variable transformation). Replace the variables Xt and Ξt with theN [t] variables X[t, n] and Ξ[t, n], n ∈ S[t].

Rule 2 is replaced by the following :

Rule 6 (Parameter transformation). Replace the parameter εt−1 with theN [t] parameters ε[t− 1, `[t, n]] where n ∈ S[t].

Rules 3 and 4 are maintained as in subsection 9.5.

Extension to variables with time lags

For the sake of simpler notation, we have not considered problems withtime-lagged decisions. However it is often the case that a decision is to betaken at t but takes effect at t + k. This can be formalized by means of adouble-indexing. We adopt the following convention

Convention 5. If a variable or a parameter includes more than one timeindex, the first time index corresponds to the time at which the decision istaken ; the subsequent time indices define the dates at which the parameteror variable has an impact.

For instance, x[t, t+ 1] will be made contingent on nodes [t, n], n ∈ S[t],but not to nodes [t+ 1,m], m ∈ S[t+ 1].

9.6 Conclusion

Multistage stochastic programming with recourse is one possible ap-proach to model sequential decision-making under uncertainty. It appliesto discrete, or discretized, stochastic processes and leads to the formulationof the deterministic equivalent. This mathematical programming problemis expressed in algebraic terms and can be solved by available optimizationsoftware. In this paper, we have proposed a methodology to help users toformulate the deterministic equivalent program from their base determi-nistic model and from general event tree representations of the stochastic

92

Conclusion

process. In particular, we have introduced recursively-defined generic func-tions that make it possible to navigate through the tree and the alternativeevent tree formulations.

Together with the methodology, we offer a tool, the perl script, thatfully automatizes the process of of building and solving stochastic program-ming problems. We would also like to emphasize a nice feature of the propo-sed tool. Associated with the free gnu linear programming kit that containsthe gmpl language —a subset of ampl— and a LP solver, our tool offersa free alternative to stochastic linear programming. It is our hope that thetool will evolve and benefit from contributions of the community. A debug-ger that would check the correctness of the deterministic model would bemost welcome, as well as a user-friendly interface.

93

Partie IV

Programmation stochastiqueavec regle de decision

95

Introduction

Cette partie est la seconde contribution de notre travail de recherche.Elle presente une methode heuristique d’optimisation dans l’incertain. Elle afait l’objet d’une publication [87] recemment parue dans une edition specialede la revue Automatica.

Les decideurs ont besoin de prendre en consideration de plus en plusde parametres. Cela peut se traduire par des problemes d’optimisationmulti-etapes dans l’incertain. Ces problemes sont difficiles a resoudre. Lesmethodes disponibles sont victimes de la malediction de la dimension commenous l’avons vu en partie II. Le decideur opte alors pour des techniques dereduction et d’agregation de scenarios pour revenir a un probleme, certescaptant moins l’incertitude, mais gerable. Plus recemment, des propositionsont ete faites ne mettant pas en jeu de probabilites, comme la programma-tion robuste [14]. Ces methodes utilisent un critere min-max, qui permet deprendre en compte une part d’incertitude tout en maintenant la taille duprobleme traite. Nous reviendrons plus en detail sur l’approche program-mation robuste en partie V.

Ainsi le decideur doit se resigner a diminuer la dimension des variablesde son probleme, a diminuer le nombre de periodes temporelles ou bienencore a utiliser un critere qui n’est peut etre adapte a son objectif. Lapremiere motivation de nos recherches est donc de tenter de resorber l’ecartentre l’objectif du decideur et les moyens a sa disposition. Cela nous conduita chercher une alternative a la programmation stochastique qui contournela malediction de la dimension. La seconde motivation est de simplifier lamise en place des politiques de decisions trouvees. Pour cela nous nous in-terrogerons sur le mode operatoire actuel que doit suivre le decideur apresavoir resolu un probleme de programmation stochastique.

Nous avons choisi d’adopter une methode heuristique, et c’est proba-blement une des methodes les plus a meme d’apporter des solutions auxproblemes massivement multi-etapes, comme nous pouvons le lire dans ces

97

Introduction

citations tirees de la litterature, et qu’il nous semble important de mention-ner :

We argue that multi-stage problems, even linear with complete recourse,generically are computationally intractable already when medium-accuracysolutions are sought.

A. Shapiro et A. Nemirovsky dans [80].

It simply is not wise to solve scenario problems to optimality.

Not only can one solve scenario problems approximately, one should solvethem approximately.

P. Kall et S. W. Wallace dans [52].

Stochastic programming problems are in general hard to solve, even harderthan most well known combinatorial optimization problems.

M. Dyer et L. Stoogie dans [26].

Partant de la constatation qu’il est illusoire de rechercher une methodenumeriquement traitable, c’est-a-dire de complexite polynomiale, nous n’avonspas essaye d’etablir de resultats theoriques de convergence. Notre proposi-tion est donc heuristique. Pour l’evaluer et la comparer a d’autres methodes,nous avons mis au point une technique de validation empirique.

98

Chapitre 10

La programmationstochastique avec regle dedecision constante parmorceaux

Sommaire10.1 Un probleme multi-etapes sur un peigne . . . . . . . . . 100

10.2 Un processus decisionnel a memoire imparfaite . . . . . 103

Regles de decision . . . . . . . . . . . . . . . . . . . . . 105

Perte d’information contre gain d’incertitude residuelle 106

10.3 Combinaison de regles de decision . . . . . . . . . . . . 107

Si nous pouvions representer de facon exhaustive le processus aleatoireξt, il aurait la forme d’un arbre, contenant probablement un tres grandnombre de branchements a chaque nœud. Cette representation, certes par-faite, ne peut en aucun cas etre utilisee dans une approche programma-tion stochastique comme il en a ete discute dans la section traitant de lamalediction de la dimension.

Dans la majorite des cas, nous disposons d’une representation partielledu processus aleatoire, bien souvent tiree par methode de Monte-Carlo,consistant en une vaste collection S de scenarios. Nous supposons que cettecollection est un peigne. L’approche par programmation stochastique stan-dard, ne pouvant fonctionner en l’etat sur un peigne, est precedee d’unephase de reduction/agregation de scenarios permettant de transformer le

99

10. La programmation stochastique avec regle de decisionconstante par morceaux

peigne en arbre avec de nombreux branchements. En calquant le proces-sus de decision sur un tel arbre, on rend les variables de decision et lescontraintes contingentes aux valeurs du processus aleatoire. On peut ainsirespecter les contraintes :

– de non-anticipativite. L’arbre d’evenements est le support de la filtra-tion de l’espace de probabilite.

– d’un processus a memoire parfaite. A chaque instant, toutes les ob-servations sont disponibles.

Nous estimons que l’arbre d’evenements et le processus a memoire parfaitesont les deux sources de la malediction de la dimension dont souffre laprogrammation stochastique multi-etapes. Nous proposons dans la presentepartie de nous en affranchir. Dans la section 10.1, nous formulons un pro-bleme de programmation stochastique sur un peigne. Dans la section 10.2,nous proposons des regles de decision, support d’un processus a memoireimparfaite. La section 10.3 presente une maniere d’ameliorer la nouvelleformulation.

10.1 Un probleme multi-etapes sur un

peigne

Nous desirons souligner dans cette section que la phase d’agregationn’est pas necessaire dans sa totalite. Lorsque l’on dit qu’un peigne n’est pasutilisable en l’etat c’est que l’on considere le processus d’information calquesur le processus aleatoire. Cependant, rien ne nous empeche de dissocier cesdeux processus. De plus, l’agregation reduit l’information presente dans S,qui est deja rappelons-le une vision partielle de la realite. Ainsi, reduire cettephase au strict minimum permettrait de minimiser la perte d’information.

La structure de peigne n’est pas un probleme pour le processus aleatoireproprement dit. Elle est un probleme pour les decisions. Si nous procedionssur le peigne comme sur l’arbre, nous rendrions contingentes les variablesde decision et d’etat au peigne, et la distinction de chaque scenario d’unpoint de vue decisionnel se ferait alors des l’etape t = 1. Il faut trouver unsupport aux decisions qui ne revele pas le futur.

La programmation stochastique permet de trouver un tel support, maisen transformant le peigne. Ce support est le processus d’information. Ilest implicite dans la formulation de la programmation stochastique. Il vanous falloir l’expliciter. Nous nous basons sur la serie (Pt)T−1

t=1 de partitionsPt = (D1

t , . . . ,DRtt ) formant un raffinement de la partition en t−1, qu’utilisel’approche standard. Nous allons agreger le processus d’information sans

100

Un probleme multi-etapes sur un peigne

agreger le processus aleatoire.Soit la fonction indicatrice de Dirac suivante :

δDνt (ξnt ) =

1 si n ∈ Dνt0 sinon,

Nous definissons une nouvelle fonction ψ telle que :

unt = ψt(xt, ut−1, ξt) =Rt∑ν=1

vνt δDνt (ξnt ), (10.1)

avec vνt une variable de decision reelle.L’egalite (10.1) definit la commande comme une regle de decision de

l’alea. Cette regle regroupe un maximum d’observations au moment de laprise de decision unt puisque nous sommes en mesure de connaıtre le sous-scenario σnt regroupant les realisations, l’historique des etats (x0, . . . x

nt ) et

l’historique des decisions, du fait de la propriete de raffinement. Toutes lesobservations sont disponibles. Cette regle de decision est le support d’unprocessus d’information a memoire parfaite.

Dans la litterature, nous trouvons plusieurs references au concept deregle de decision, et ce des 1960 dans [48] pour resoudre des problemesde planning de production. En effet, pour simplifer des formulations ouacquerir des proprietes interessantes pour la resolution, certaines reglessont contraintes a faire partie d’un sous-ensemble de fonctions initiale-ment etudiees. Les auteurs de [37] s’interessent aux proprietes des regles dedecision lineaires dans le cadre de la programmation stochastique. Il sembleque cet outil conceptuel tombe ensuite dans l’oubli avant de reapparaıtredans le cadre de la programmation robuste dans [13]. La reduction de lacommande a une regle de decision lineaire permet aux auteurs de [13] deproposer une formulation robuste multi-etapes, l’AARC pour affinely adu-jstable robust counterpart. Nous avons ensuite etudie cette piste, et presentenos premiers resultats lors d’une conference [86]. Dernierement, les auteursde [80] s’interessent a la complexite de problemes stochastiques integrantl’utilisation des regles de decision lineaires. Dans la section suivante, nousnous interessons a un nouveau sous-ensemble de fonctions : les fonctionsconstantes par morceaux, telles qu’introduites en (10.1).

Une unique decision vνt est prise pour tous les nœuds de Dνt , d’ou leterme d’ensemble de decision. La decision vνt est prise sur base de l’in-formation d’appartenance a l’ensemble de decision Dνt , mais ne peut dis-tinguer deux sous-scenarios de cet ensemble de decision. Tous les sous-scenarios traversant l’ensemble de decision Dνt ont les memes decisions

101


passees (uo, vν11 , . . . , v

νt−1

t−1 ) du fait de la propriete de raffinement des par-titions. Par contre, ces sous-scenarios peuvent avoir des decisions futuresdistinctes. L’incertitude residuelle est maintenue.

Nous definissons un nouveau deterministe equivalent sur un peigne :

minu,x,v

F0(u0) +N∑

n1=1

1

NF1(xn1

1 , un11 , ξ

n11 ) + . . .

+N∑

nT=1

1

NFT (xnTT , ξnTT ) (10.2a)

s.c. Atunt +Btx

nt + ct ≤ 0, t = 0, . . . T, n = 1, . . . N, (10.2b)

xnt = φt(xnt−1, u

nt−1, ξ

nt ), t = 1 . . . T, n = 1, . . . N, (10.2c)

unt =Rt∑ν=1

vνt δDνt (ξnt ), t = 1, . . . T − 1, n = 1, . . . N, (10.2d)

Pt raffinement de Pt−1, (10.2e)

x0 connu (10.2f)

Les veritables variables de decision de ce nouveau probleme sont les vνt . Il ya autant de variables vνt dans (10.2) que de variables unt dans (6.16). Nousutilisons 1

Nen place de πnt car supposons que les scenarios de S sont tous

equiprobables.La difference entre les deux formulations se situe au niveau du nombre

de nœuds. Notre nouveau probleme (10.2) comporte N nœuds par periodetemporelle, soit plus de contraintes et plus de variables d’etats que leprobleme (6.16) malgre un nombre constant de variables de decision. C’estl’inconvenient majeur de cette formulation. Nous proposons une manierede le contourner dans la section 10.3. Notons que cette formulation n’estqu’une etape pour arriver a la formulation de la section suivante.

Le gros avantage d’une telle approche est le maintien de l’ensembleS. Rappelons que cet ensemble est deja une vision partielle du processusaleatoire. Une agregation de ce dernier ne peut se traduire que par une perted’information. Ici, la perte est limitee.

Nous pouvons aussi noter que cette formulation evite d’avoir a choisirune realisation representative de l’ensemble de decision. Dans la presentationde l’approche de programmation stochastique, nous avons fait le choix deconserver la valeur de la realisation du scenario reference. Mais de nom-breuses options restaient possibles. Dans la presente formulation sur unpeigne, la question ne se pose plus.

Cette formulation souffre cependant toujours de l’accroissement expo-nentiel du nombre d’ensembles de decision donc de ces variables, du fait

102

Un processus decisionnel a memoire imparfaite

de la presence de la traduction de la filtration qu’est la contrainte de raffi-nement des partitions. Cet accroissement, necessaire par definition, imposesoit de limiter drastiquement le nombre d’ensembles de decision dans lesperiodes initiales (ou encore de limiter drastiquement le raffinement) pourrester compatible avec un peigne donne, soit de creer un peigne de dimen-sion considerable et aboutir a un probleme ingerable. La section suivantepropose une formulation qui s’affranchit de cet acroissement.

10.2 Un processus decisionnel a memoire

imparfaite

Notre objectif est de contourner l’augmentation explosive du nombre devariables de decision dans l’approche programmation stochastique. Cetteaugmentation est rendue necessaire afin de maintenir un niveau d’incer-titude residuelle important tout au long du processus temporel. C’est unveritable piege. La source de l’evolution exponentielle du nombre de cesvariables est la serie de partitions formant un raffinement. L’idee est doncde se passer d’un tel raffinement.

Concretement, se passer de raffinement veut dire calculer la partitionPt independamment de la partition Pt−1, et cela veut dire que la seriedes Rt ne doit pas necessairement etre strictement croissante. Ce sont desconsequences tout a fait positives a la vue de notre objectif.

Cependant, l’absence de raffinement a une consequence directe sur leprocessus d’information : il devient faillible. Sans raffinement, il est parfoisimpossible d’identifier les decisions passees, tout du moins de facon totale-ment explicite. Nous sommes alors en presence d’un processus d’informationa memoire imparfaite.

Limiter l’evolution exponentielle du nombre de variables a un cout :celui d’oublier une partie des observations. Cela n’aurait aucun sens dansun probleme a deux etapes, mais pour resoudre un probleme a plus de 10etapes, c’est difficile de conclure, en tout cas au premier abord. Nous allonsdiscuter de tout cela en detail ci-apres, en expliquant la demarche pas apas.

Nous supposons avoir a notre disposition un ensemble S, et une serienon necessairement strictement croissante de Rt. Nous desirons commen-cer par calculer des ensembles de decision, independants d’une periode al’autre. Nous reprenons les memes notations que dans la section 6.3, et lameme approche sans agregation du processus aleatoire que dans la sectionprecedente.

103


Nous resolvons T−2 problemes de p-medianes. Rappelons la formulationdu probleme d’optimisation permettant de creer une partition optimale enperiode t :

minp,b

∑(n,m)∈N 2

πnt c(σnt , σ

mt )pnm (10.3a)

s.c.∑m∈N

pnm = 1, ∀n ∈ N (10.3b)

0 ≤ pnm ≤ bm,∀(n,m) ∈ N ×N , (10.3c)

bm ∈ 0, 1,∀m ∈ N , (10.3d)∑m∈N

bm = Rt, (10.3e)

La solution a ete donnee en section 6.3. On la rappelle ici pour facili-ter la lecture. Elle se compose des ensembles des indices de sous-scenariosreference

Rt = m ∈ N | bm = 1,

ainsi que des ensembles de decisions

Dνt = n ∈ N | rν = arg minm∈Rt

πnt c(σnt , σ

mt ).

La partition des indices des sous-scenarios σnt ne doit se faire que surbase des observations. Etant donne l’absence de raffinement, la fonctionindicatrice doit avoir comme parametre le sous-scenario σnt en place de ξnt .Nous etendons la definition de la fonction de Dirac comme suit :

δDνt (σnt ) =

1 si n ∈ Dνt0 sinon,

Nous illustrons la difference majeure avec la programmation stochas-tique dans la figure 10.1. On peut facilement voir que les ensembles dedecision de la periode t = 2 ne forment pas un raffinement de la partitionP1.

La definition de la metrique c est capitale. C’est elle qui definit la notionde proximite de deux sous-scenarios. C’est aussi elle qui fixe le niveau deconnaissance des observations pour le calcul de la proximite.

Nous pouvons utiliser toute sorte de distance, comme celles basees surdes normes 1, 2, ∞. Nous utiliserons aussi dans la partie V une norme ins-piree du lissage exponentielle, comme suit :

c(σat , σbt ) = α‖ξat − ξbt‖p + (1− α)c(σat−1, σ

bt−1)

104

Un processus decisionnel a memoire imparfaite

mmmmmmmm

mmmmmmmm

mmmmmmmm

JJJJJJJ

@@@@@

"""""

bbbbb

````m

t = 0 t = 1 t = 2 t = 3

v

vv

v

v

Fig. 10.1: Ensembles de decision de formant pas de raffinement

avec c(σa1 , σb1) = ‖ξa1 − ξb1‖p, α un parametre donne avec 0 ≤ α ≤ 1, et ‖ · ‖p

la norme p.Le controle sur le niveau d’information se fait par la restriction a un

sous-ensemble de (ξ1, . . . , ξt). Nous pourrions par exemple considerer que laproximite de sous-scenarios en periode t ne se mesure qu’a travers les troisdernieres realisations. Nous aurions alors, pour t ≥ 3 :

c(σat , σbt ) = ‖(ξat−2 − ξbt−2, ξ

at−1 − ξbt−1, ξ

at − ξbt )‖p.

L’information d’appartenance a un tel ensemble de decision nous ap-porte une information partielle : Dνt regroupe des sous-scenarios proches lesuns des autres au sens de la metrique c choisie. Nous decidons de limiter leprocessus d’information a cette notion de proximite. Les sous-scenarios d’unensemble de decision n’ont pas necessairement les memes decisions passees,puisque la notion de proximite est propre a chaque periode temporelle.

Regles de decision

Cette restriction se traduit par la definition d’une nouvelle regle dedecision :

ut = ψt(x0, u0, ξ0, . . . , ξt) =Rt∑ν=1

vkt δDνt (σnt ) (10.4)

Les decisions passees ont disparues de cette formulation. Nous consideronsqu’une commande a la periode t est une regle de decision des realisationsde l’alea uniquement.

105


Dans la presente approche, nous faisons intervenir des fonctions indica-trices. La fonction ψ est une fonction constante par morceaux. Nous appe-lons cette regle de decision une regle de decision constante par morceaux 1.Ce concept ne semble pas avoir ete utilise par le passe.

Nous sommes maintenant en mesure de formuler un probleme de pro-grammation stochastique avec regle de decision constante par morceaux,soit une adaptation du probleme (10.2). En anglais nous parlerons de sto-chastic programming with step decision rules, abrege en SPSDR.

minu,x,v

F0(u0) +N∑

n1=1

1

NF1(xn1

1 , un11 , ξ

n11 ) + . . .

+N∑

nT=1

1

NFT (xnTT , ξnTT ) (10.5a)

s.c. Atunt +Btx

nt + ct ≤ 0, t = 0, . . . T, n = 1, . . . N, (10.5b)


nt−1, ξ

nt ), t = 1 . . . T, n = 1, . . . N, (10.5c)

unt =Rt∑ν=1

vνt δDνt (σnt ), t = 1, . . . T − 1, n = 1, . . . N, (10.5d)

x0 connu (10.5e)

Notons que la formulation du probleme (10.5) est une generalisation duprobleme (10.2). Au contraire de l’approche standard, SPSDR ne necessitepas que la cardinalite Rt des partitions soit strictement croissante pourgarantir la presence d’une incertitude residuelle. En effet, la distinction d’unpoint de vue decisionnel de sous-scenarios en periode t n’est pas un gage dedistinction definitive. Prenons le cas de deux scenarios d’indices a et b. Lessous-scenarios σat et σbt sont dans deux ensembles de decision distincts en t,mais peuvent appartenir au meme a la periode t + 1. Finalement, la suitedes Rt n’est pas du tout contrainte. Nous pourrions meme definir une suitedecroissante de Rt !

Le nombre de variables de decision du probleme etant proportionnelau nombre d’ensembles de decision, la valeur des Rt constitue un outil decontrole de la taille du probleme genere.

Perte d’information contre gain d’incertituderesiduelle

La particularite de SPSDR est la perte d’information sur les observa-tions. Nous limitons cette perte en regroupant des scenarios proches en

1En anglais, nous parlons de step decision rule.

106

Combinaison de regles de decision

terme de realisations passees. Nous supposons que cette proximite dans lesrealisations traduit un passe decisionnel proche.

Nous voudrions aborder plusieurs points qui nous permettent de penserque ne pas mettre en place un processus d’information a memoire parfaitea des avantages :

L’importance de la premiere decision. L’optimisation sous incertitude,en tant que technique d’aide a la decision, fournit au decideur unedecision initiale u0 capitale, et des politiques de decision pour la suite.Dans les faits, les periodes suivantes pourront etre reoptimisees par ho-rizon glissant. La decision qui compte plus que toutes est la premiere.On peut donc supposer qu’il faille discretiser au maximum l’alea ξ1.Cette perspective n’a pas d’influence nefaste sur notre approche, parcontre elle est desastreuse pour la programmation stochastique. Rap-pelons aussi que u0 est traite de la meme facon par les deux approches.Les regles de decision ne concernent que les decisions ut, t ≥ 1 pourlesquelles nous pouvons adopter une processus d’information faillibleavec une influence sur la pertinence de la premiere decision faible.

La rationalite du decideur. La modelisation d’un probleme d’optimisa-tion est base sur le principe de la rationalite de l’agent. Nous savonsbien evidemment que le resultat d’une optimisation n’est qu’une aidea la decision, et que l’agent prendra sa propre decision. Il faut aussisouligner que meme si le probleme formule prend en compte toutes lesdonnees, l’agent pourrait prendre une decision tout autre. Car dans lesfaits, la rationalite de l’agent est limitee [83]. Notre approche ne metpas en place la rationalite totale de l’agent puisqu’il oublie une partiedes realisations. Cette perte d’information ne doit pas s’interpreterqu’a l’instant t le decideur aura oublie la chaıne de decisions qu’il aprises, mais plutot qu’a l’instant initial il n’arrive pas a integrer dansson anticipation des actions qui seront prises en t le fait qu’il aura alorsune connaissance parfaite du passe. La rationalite reste utopique, ilne semble donc pas absurde de ne pas la mettre en place.

10.3 Combinaison de regles de decision

Il est possible d’ameliorer SPSDR en prenant une combinaison convexede plusieurs regles de decision constantes par morceaux independantes lesunes des autres. Du fait de la convexite du probleme, une telle combinaisonest realisable, et la valeur esperee du cout de la combinaison sera meilleure(plus petite) que la combinaison des esperances de cout de ces memes regles.Nous considerons la regle de decision calculee sur un ensemble de scenarios

107


comme l’avis d’un expert face a cet ensemble, representation partielle duprocessus aleatoire. La combinaison de plusieurs regles est alors vue commela proposition combinee d’un groupe d’experts. L’idee de construire plu-sieurs regles de decision a partir d’ensembles independants est directementinspire de [63]. Le recours a l’avis d’expert est aussi utilise dans le cadred’apprentissage automatique2 comme dans [18, 34, 35].

Nous presentons ci-apres brievement une utilisation possible des avisd’experts dans notre approche SPSDR. Nous tirons E ensembles Se, e =1, . . . E, independants. Chaque ensemble est affecte a un expert different.Chaque expert calcule ses propres ensembles de decision et sa propre reglede decision. Nous combinons ensuite les differentes regles pour n’en formerqu’une seule, plus efficace. Le theoreme suivant justifie la combinaison desregles plutot que la combinaison des couts :

Theoreme 3. L’esperance de cout d’une combinaison convexe de regles dedecision est inferieure ou egale a la combinaison convexe des esperances decouts des regles de decision individuelles.

Demonstration. Le probleme (10.5) etant convexe, nous pouvons dire quel’esperance de cout d’une combinaison convexe de regles de decision estinferieure a la meme combinaison convexe des esperances de couts desexperts individuels. Il suffit de le prouver pour un unique et quelconquescenario. Rappelons que pour un scenario, la suite des commandes definitde facon unique la suite des etats a travers l’equation (10.5c). Tout d’abord,il est clair que la combinaison convexe des regles de decision satisfait lacontrainte (10.5b). Ensuite, etant donnee que la contrainte (10.5c) est lineaire(la fonction φ etant lineaire par definition), la suite des etats associes a lacombinaison de regles de decision est la combinaison des suites d’etats in-dividuels. Enfin, la convexite de la fonction objectif implique que le coutd’une combinaison convexe d’une regle de decision est inferieure ou egale a lacombinaison convexe des couts individuels. L’esperance etant elle-meme unefonction convexe, nous etendons la preuve a un ensemble de scenario.

Nous presentons ci-apres la procedure generale de SPSDR, en utilisantun cadre de travail que nous appliquerons aussi pour les autres methodesdeveloppees en partie V, c’est-a-dire le decoupage en 3 phases : initialisation,optimisation et mesure de performance.

1 Initialisation : Nous disposons d’un large ensemble de validation V decardinalite N , et d’un ensemble de calcul C, de cardinalite E×N , tirealeatoirement a partir de V .

2 Optimisation : Cette phase est decoupee en deux etapes :

2Branche de l’intelligence artificielle. En anglais, on parle de machine learning.

108

Combinaison de regles de decision

2.1 Expertise : Repeter E fois la procedure suivante, apres avoir separel’ensemble C en E ensembles Se independants de cardinalite N , avece = 1, . . . E :

1. Construire les ensembles de decision Dνt,e, avec t = 1, . . . T − 1 etν = 1, . . . Rt en resolvant T − 2 problemes (10.3). En deduire lesensembles Rt,e.

2. Construire la regle optimale u∗Se sur Se avec unet,e =Rt∑ν=1

vνt,eδDνt,e(σnet )

avec ne indice du scenario σnet ∈ Se.

2.2 Combinaison des avis d’experts :

1. Etendre la regle de decision u∗Se a tous les scenarios de V en calcu-lant la partition suivante sur l’ensemble des indices des scenarios

de V :E⋃e=1

Dνt,e = 1, . . . N. Cette partition est realisee sur base

de l’equation (6.22) et des ensembles de sous-scenarios referenceRt,e. A noter que Dνt,e ⊂ Dνt,e. Nous pouvons donc definir la regle

de decision sur V : unt,e =Rt∑ν=1

vνt,eδDνt,e(σnt )

2. La combinaison de regles u∗C est tout simplement l’esperance des

regles sur les experts, soit : unt = 1E

E∑e=1

unt,e

3 Mesure de performance

3.1 Prediction : La valeur de fC est l’esperance en terme de cout a tra-vers f de tous les scenarios de C. Cette valeur est utilisee comme uneprediction de la valeur esperee. Elle pourra servir de base de comparai-son avec d’autres methodes, les valeurs d’optimisation des differentsexperts ne prenant pas en compte la combinaison des regles. Nousnommons cette phase la phase de prediction

3.2 Validation : La valeur de fV est l’esperance en terme de cout a tra-vers f de tous les scenarios de V . En supposant ce dernier commerepresentatif du processus aleatoire, il sera la base de comparaison dece que nous appelons la phase de validation.

3.3 Statistiques : Cette phase regroupe le calcul d’un ensemble d’in-dicateurs permettant d’evaluer la qualite de la solution, de chaquephase du calcul, et bien sur de comparer differents parametrages,differentes methodes. Nous nous interesserons en particulier a l’erreurde prediction, qui sera le ratio : epred =| fC−fV

fV| .

109


Ce cadre de travail est employe dans la partie V. Il permet de mesurer a tra-vers epred la performance d’une methode, et permet de comparer, a traversplusieurs valeurs fV , differentes methodes d’optimisation sous incertitude.

110

Chapitre 11

Procedure d’amelioration avecun objectif CVaR

Sommaire11.1 Prise en compte du risque . . . . . . . . . . . . . . . . . 11111.2 Creation de nouveaux ensembles Se : type 1 . . . . . . 11511.3 Creation de nouveaux ensembles Se : type 2 . . . . . . 116

Ce chapitre presente deux ameliorations possibles de l’approche de pro-grammation stochastique avec regles de decision constantes par morceauxdans le cadre d’un probleme integrant le risque a travers CVaR. Cette ap-proche s’interesse au comportement d’un sous-ensemble de scenario de l’en-semble de calcul. L’utilisation des avis d’experts reduit considerablementla taille des ensembles de calcul, et aussi de ces sous-ensembles. Cette car-dinalite faible reduit la pertinence du critere CVaR. Nous proposons deuxsolutions pour contourner cette difficulte. Dans une premiere section, nousrappelons la definition du CVaR et son integration dans un probleme d’op-timisation. Les deux sections suivantes proposent deux approches modifieesde la SPSDR avec utilisation du CVaR.

11.1 Prise en compte du risque

Tout d’abord, nous allons nous interesser a la valeur de defaillance auniveau γ, ou VaRγ pour Value at Risk. Les auteurs de [5] la definissentcomme le γ-quantile de la distribution d’une v.a. ξ. Dans le cadre d’unprobleme de minimisation de cout, ce sont les couts les plus eleves qui

111

11. Procedure d’amelioration avec un objectif CVaR

constituent le risque. Nous nous interessons donc au dernier quantile, celuides plus grandes valeurs de ξ. Le VaR d’une v.a. reelle ξ peut se definircomme suit :

VaRγ = infl ∈ R | P(ξ ≥ l) ≤ γ. (11.1)

Nous illustrons dans la figure 11.1 le VaR10% d’une v.a. qui suit une loinormale centree reduite.

Fig. 11.1: Representation du VaR10% d’une v.a. qui suit N (0, 1)

Sur base du VaR, les auteurs de [74] definissent l’esperance condition-nelle de defaillance de niveau γ de la v.a. ξ, ou CVaR pour ConditionnalValue At Risk, comme suit :

CVaRγ =

∫ ∞VaRγ

ξ ×D(ξ | ξ ≥ VaRγ)dξ, (11.2)

avecD(·) la fonction de densite de probabilite de ξ. Le CVaRγ est l’esperancedes valeurs des realisations de ξ qui sont superieures ou egales au seuil definipar VaR. On parle aussi d’Expected Shortfall. La figure 11.2 illustre le CVaRde la v.a. reelle ξ qui suit N (0, 1). Dans le cas d’une loi normale centree

reduite, le CVaR est egale a 1γ√

2πe−

CVaR2

2 , soit pour notre exemple environ1.755.

112

Prise en compte du risque

Fig. 11.2: Representation du CVaR10% d’une v.a. qui suit N (0, 1)

Dans le cas d’une v.a. discrete, nous reformulons CVaR comme unprobleme d’optimisation :

CVaRγ = miny,z

z +1

γ

N∑n=1

πnyn, (11.3a)

yn ≥ 0, n = 1, . . . N, (11.3b)

yn ≥ ξn − z, n = 1, . . . N, (11.3c)

avec ξn les realisations de la v.a. reelle discrete ξ et πn leurs probabilitesassociees, n = 1, . . . N . L’interet de la formulation de CVaR, par rapport aVaR, est sa propriete de convexite. Appliquee a un probleme d’optimisationconvexe, elle ne modifie pas les proprietes du probleme original, seulementl’apprehension du risque dans la fonction objectif.

Afin de faciliter l’application de CVaR sur une formulation SPSDR, nousallons modifier l’ecriture des fonctions objectifs utilisees precedemment.

Les formulations (6.16) et (10.5) peuvent se reformuler avec une fonctionobjectif de la forme :

min∑n∈N

πng(σn) (11.4)

ou g represente l’evaluation a travers les fonctions Ft sur tout l’horizon

113


temporel d’un unique scenarios :

g(σn) = F0(u0) + F1(xn1 , un1 , ξ

n1 ) + · · ·+ FT (xnT , ξ

nT ) (11.5)

avec σn = (ξn1 , . . . ξnT ). La fonction g est evidemment fonction des variables

x, u, v, mais nous ne les avons pas reportees ici par souci de lisibilite. Lafonction g, a travers σ, est une variable aleatoire dont on peut definir leCVaR.

Lorsque nous desirons prendre en compte la notion de risque dans unprobleme d’optimisation, nous pouvons notamment nous interesser a mini-miser un autre critere que l’esperance des couts. Une des options possiblesest de s’interesser a la minimisation du CVaR. Nous definissons ci-apres unprobleme d’optimisation sous incertitude avec regles de decision constantespar morceaux, et avec une fonction objectif de minimisation du CVaR :

minu,v,x,y,z

z +1

γ

N∑n=1

πnyn (11.6a)

s.c. Atunt +Btx

nt + ct ≤ 0, t = 0, . . . T, n = 1, . . . N, (11.6b)


nt−1, ξ

nt ), t = 1 . . . T, n = 1, . . . N, (11.6c)

unt =Rt∑ν=1

vνt δDνt (σnt ), t = 1, . . . T − 1, n = 1, . . . N, (11.6d)

x0 connu, (11.6e)

yn ≥ 0, n = 1, . . . N, (11.6f)

yn ≥ g(n)− z, n = 1, . . . N, (11.6g)

avec g(n) defini comme dans (11.5).Considerant que l’approche standard de SPSDR comporte l’utilisation

des experts, nous devons resoudre E problemes (11.6) sur des sous-ensemblesde N scenarios, avec N faible.

L’association d’un γ petit et d’un N faible implique que le sous ensemblede mauvais scenarios est tres petit. Ce sous-ensemble reflete alors assez malles mauvais scenarios de l’ensemble initial. Par exemple, on peut imaginerque tous les mauvais scenarios de C soient regroupes dans un unique Se.Nous entendons par mauvais scenario un scenario qui apres optimisationa une valeur g(n) > z, soit yn > 0. Cette notion sera precisee lors despresentations des procedures a suivre.

Pour reduire l’effet d’une telle restriction, il faut pouvoir utiliser un Naussi grand que possible, pour γ fixe.

114

Creation de nouveaux ensembles Se : type 1

11.2 Creation de nouveaux ensembles Se :

type 1

La valeur de γ n’a pas de consequence sur la complexite du probleme,mais N en a une.

Au lieu de travailler avec des ensembles Se plus grands, nous preferonsutiliser pour commencer l’approche standard SPSDR, et utiliser l’informa-tion donnee par le calcul du CVaR a posteriori.

La qualite de la solution est liee a la presence de mauvais scenariosdans le sous ensemble Se. Apres l’optimisation, nous sommes capables dereconnaitre les mauvais scenarios de chaque ensemble Se. Nous proposonsd’integrer les mauvais scenarios de tous les ensembles dans chacun d’eux,et de relancer l’optimisation. Pour maintenir une coherence, nous modifionsles probabilites de tous les mauvais scenarios. La procedure est decrite enfigure 11.3. Les valeurs de N et γ seront choisies de telle sorte que γ × Nsoit entier.

1. Resoudre E problemes (11.6) sur les ensembles Se.2. Creer les ensembles Me de mauvais scenarios : Me = σn | yn >

0, σn ∈ Se, e = 1, . . . E. La cardinalite de l’ensembleMe est egalea γ ×N .

3. Creer de nouveaux ensembles Se = Se⋃

ε=1,...Eε6=e

Mε, e = 1, . . . E.

4. Remplacer les probabilites πn par πn =

1E× πn si σn ∈

E⋃e=1

Me

πn sinon.

5. Calculer de nouveaux ensembles de decision pour les sous-ensemblesSe en prenant en compte les nouvelles probabilites πt.

6. Resoudre E problemes (11.6) sur les ensembles Se .

7. Combiner les regles de decisions de chaque expert pour permettreles calculs de fC et fV .

Fig. 11.3: Methode de calcul sur les ensembles Se, type 1.

115


11.3 Creation de nouveaux ensembles Se :

type 2

La particularite de cette approche est de nuancer le terme de mauvaisscenario.

Apres optimisation, comme nous l’avons dit dans la presentation de laprecedente procedure, nous sommes en mesure de reconnaitre les mauvaisscenarios de chaque ensemble Se, mais nous sommes aussi en mesure de lesreconnaıtre au sein de C en utilisant non pas le resultat des E optimisationscomme base de reference, mais l’application de la combinaison des regles dedecision sur C. En d’autres termes, nous calculons fC. Sur cette base, noussommes en mesure de calculer les mauvais scenarios. Nous avons alors deuxsous-ensembles :M et C \M qui nous permettent de calculer de nouveauxensembles Se. La procedure est decrite en figure 11.4

1. Resoudre E problemes (11.6) sur les ensembles Se.2. Appliquer la combinaison de regles de decision a tous les scenarios

de C.3. Creer l’ensembleM de mauvais scenarios :M = σn | g(n) > z, en

resolvant le probleme trivial suivant, ou les g(n) sont des parametres :

minz,y

z +1

γ

E×N∑n=1

πnyn s.c. yn ≥ g(n)− z ≥ 0, n = 1, . . . E ×N

La cardinalite de l’ensemble M est egale a : |M| = γ × E ×N .

4. Tirer de facon aleatoire E sous-ensembles Se, e = 1, . . . E de taille(1− γ)×N depuis C \M.

5. Finaliser les nouveaux sous-ensembles Se ← Se ∪M, e = 1, . . . E.

6. Remplacer les probabilites πn par πn =

1E× πn si σn ∈M

πn sinon.

7. Calculer de nouveaux ensembles de decision pour les sous-ensemblesSe en prenant en compte les nouvelles probabilites πt.

8. Resoudre E problemes (11.6) sur les ensembles Se .

9. Combiner les regles de decisions de chaque expert pour permettreles calculs de fC et fV .

Fig. 11.4: Methode de calcul sur les ensembles Se, type 2.

116

Partie V

Etude empirique

117

Chapitre 12

Le probleme de contratd’approvisionnement

Sommaire12.1 Le modele RSFC . . . . . . . . . . . . . . . . . . . . . . 11912.2 Methodes developpees . . . . . . . . . . . . . . . . . . . 122

SPSDR . . . . . . . . . . . . . . . . . . . . . . . . . . . 122Optimisation Robuste . . . . . . . . . . . . . . . . . . . 125SP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

12.3 CVaR applique au modele RSFC . . . . . . . . . . . . . 131

Nous appliquons notre approche sur un modele de chaıne d’approvi-sionnement, un probleme de contrat d’approvisionnement avec engagementflexible appele RSFC pour retailer-supplier flexible commitment. Dans lapremiere section, nous presentons en detail le modele RSFC. Puis dans laseconde section, nous expliquons les methodes developpees pour resoudre ceprobleme : la programmation robuste (RO), la programmation stochastiquestandard (SP) et la programmation stochastique avec regles de decisionconstantes par morceaux (SPSDR) Nous employerons les abreviations an-glaises pour nommer les methodes dans la suite de la these.

12.1 Le modele RSFC

L’article [4] donne une des premieres formulations du probleme RSFC.Cette formulation a ensuite ete reprise dans [12]. Ce probleme concerne

119

12. Le probleme de contrat d’approvisionnement

la gestion du stock d’un detaillant qui fait face a une demande aleatoirede clients, et qui passe des commandes a son fournisseur pour satisfairecette demande. Afin de reduire la variabilite des commandes (l’effet For-rester, introduit en partie I, dont pourrait etre victime le fournisseur), desobjectifs d’achat mensuels sont fixes a l’avance. Ce contrat laisse en outrela possibilite d’ajuster les commandes en exercant des options, moyennantune penalite. C’est un probleme de contrat d’approvisionnement, problemed’optimisation sous incertitude multi-etapes, sur les 12 mois de l’annee. Encomptant les decisions de premiere periode, avant le debut de l’exercice,nous avons un probleme comptant 13 periodes.

Nous reprendrons la methode RO developpee dans [12], et developperonsune approche SP afin d’avoir des bases de comparaisons pour mesurer laperformance empirique de notre approche SPSDR.

Interessons-nous tout d’abord au modele deterministe du RSFC :

minx,w,q

−s[xT ]+ +T∑t=1

ctqt +T∑t=1

ht[xt]+ + pt[−xt]+

+T∑t=1

α+t [qt − wt]+ + α−t [wt − qt]+ (12.1a)

+T∑t=1

β+t [wt − wt−1]+ + β−t [wt−1 − wt]+

s.c. xt = xt−1 − dt + qt, t = 1, . . . , T, (12.1b)

Lt ≤ qt ≤ Ut, t = 1, . . . , T (12.1c)

x0, w0 donnes. (12.1d)

C’est un modele de gestion de stock a produit unique dans lequel lestock est gere par etape sur un horizon de T periodes. Au debut de l’exer-cice, le detaillant specifie un vecteur d’engagement w = w1, . . . wT d’achatsde produits. Ces engagements servent de prevision au fournisseur pour luipermettre de determiner son planning de production. Au debut de la periodet, la demande dt est revelee, puis le stock xt est calcule, enfin la commandeqt+1 est prise.

→ dt 99K xt 99K qt+1 → (12.2)

La decision qt+1 est prise en periode t pour livraison en t+1. Elle est soumiseaux contraintes des wt+1. Le status du detaillant est resume a travers lestock x0 et une valeur nominale w0 representant le niveau precedent desengagements passes. Nous representons ci-apres la periode 0, soit le debutde l’exercice :

x0 99K q1, w1, . . . w12 → (12.3)

120

Le modele RSFC

Nous pourrions simplifier les notations precedentes pour gerer indepen-damment le cas t = 1 ou nous avons q1 = w1, mais nous preferons garderun modele plus general.

Les couts suivants s’appliquent sur les parties positives [xt]+ = max(0, xt)

et negatives [−xt]+ = max(0,−xt) du stock qui representent respectivementle stock physique et les reports de commandes :

– cout de stockage = ht[xt]+, ou ht est le cout de stockage unitaire.

– cout de rupture = pt[−xt]+, ou pt est le cout de rupture par unite.De plus, les engagements incluent les couts suivants :

– penalite sur la variation de deux engagements successifs. β+t [wt −

wt−1]+ + β−t [wt−1 − wt]+, ou β+t , β

−t sont les couts unitaires associes.

– penalite d’ecart entre l’engagement et la commande reelle α+t [qt −

wt]++α−t [wt−qt]+, ou α+

t , α−t sont respectivement les couts de penalites

pour une difference positive et negative.Ces couts permettent un lissage des commandes et donc une diminution del’effet Forrester pour le fournisseur.

Le stock restant en fin d’exercice xT est bonifie par une valeur s. Ceparametre doit etre plus petit que cT . Pour maintenir la convexite de lafonction (12.1a), s doit respecter la contrainte suivante :

hT − s ≥ −pT .

Le modele original inclut une contrainte sur les commandes cumulees,mais cette contrainte est inactive avec le parametrage W12 que nous utili-sons (voir [12]). Les parametres du modele sont definis dans le tableau 12.1.Les demandes sont considerees independantes et identiquement distribuees

T x0 w0 ct ht pt s α+t α−t β+

t β−t Lt Ut12 0 100 10 2 10 0 10 10 10 10 0 200

Tab. 12.1: Donnees pour le probleme RSFC, instance W12 dans [12]

de facon uniforme sur l’intervale 100± 70.Ce probleme entre parfaitement dans la categorie des problemes qu’est

capable de traiter SPSDR car :– la fonction objectif est convexe,– les etats xt du systeme ne sont pas contraints (en dehors de la defi-

nition de la dynamique du systeme),– les contraintes sont lineaires.

121


12.2 Methodes developpees

Notre objectif est de comparer 3 methodes : SP, SPSDR et RO. Leschema est le suivant. Tout d’abord, nous calculons une politique optimalepour chaque methode, ensuite nous implementons ces politiques sur un largeensemble de validation V de 100.000 scenarios. Enfin, nous calculons diverscriteres de performance (moyenne, ecart-type, valeurs maximale et mini-male, CVaR, etc.). Cela nous permet de comparer les differentes methodes.

Pour construire une politique optimale pour SP et SPSDR, nous tironsaleatoirement depuis V un ensemble C de 2000 scenarios. Il sera utilise parles deux methodes, sur base de plusieurs fonctions objectif (esperance, va-leur maximale, CVaR, etc.). L’approche RO n’a pas besoin d’ensemble decalcul pour fonctionner. Nous utilisons pour cette derniere une unique fonc-tion objectif, mais des niveaux d’immunisation differents. Nous reviendronsplus tard sur ce concept. Pour generer des solutions par la methode RO,nous utilisons l’outil informatique RobCOP1 developpe par les auteurs de[12] qui ont bien voulu le mettre a notre disposition, et nous les en remer-cions.

Nous concluons l’etude empirique par une comparaison de SP et SPSDRsur un ensemble de calcul C plus grand, contenant 5000 scenarios, afind’evaluer l’apport pour les deux methodes d’une augmentation de l’en-semble de calcul. Cette section ne presente pas de resultats numeriques(cela fera l’object du prochain chapitre), mais explique les trois methodesemployees.

SPSDR

Les parametres de la methode SPSDR sont essentiellement :– La suite des Rt definissant le nombre d’ensembles de decision a chaque

periode t,– Le nombre E d’experts, tous de cardinalite N = card(C)/E,– le type de fonction objectif employee.

Le calcul des ensembles de decision se fait a l’aide de la metrique c, sur based’une norme l2, comme suit :

c(σat , σbt ) =

||ξa1 − ξb1||2, pour t = 1√c(σat−1, σ

bt−1)2 + ||ξat − ξbt ||22, pour t ≥ 2.

(12.4a)

1pour Robust Commitment Optimization Package.

122

Methodes developpees

Avec la norme l1 ponderee, la distance est definie par :

c(σat , σbt ) =

||ξa1 − ξb1||1, pour t = 1

(1− α)c(σat−1, σbt−1) + α||ξat − ξbt ||1, pour t ≥ 2,

(12.5)

ou α est un coefficient compris entre 0 et 1. Apres de nombreux calculs,la valeur 0.65 s’est averee etre la plus performante, c’est donc celle-ci quenous utiliserons.

Nous avons mis en place de nombreuses combinaisons de parametragepossibles en terme de nombre d’ensembles de decision et de nombre d’ex-perts (5, 10 et 20). Les deux tableaux suivants (12.2 et 12.3) donnent lesreglages pour ce que l’on considere le meilleur compromis entre precision dela solution et temps de calcul.

Pour comparer SPSDR avec RO et SP, nous utilisons le parametragedu tableau 12.2. Le nombre total d’ensembles de decision pour chaque ex-

Taille de V 100,000Taille de C 2,000E 10N 200R1, . . . R11 (10,10,10,12,12,12,14,14,14,16,16)metrique c basee sur une norme l1 ponderee

Tab. 12.2: Parametrage pour les comparaisons de SPSDR avec RO et SP.

pert dans cette configuration est 141, en incluant la decision unique a lapremiere periode, ce qui represente 0.59% du nombre total de nœuds dupeigne representant C.

Enfin, pour comparer SPSDR avec SP, nous utilisons un second pa-rametrage decrit dans le tableau 12.3. Le nombre total d’ensembles de

Taille de V 100,000Taille de C 5,000E 10N 500R1, . . . R11 (50,50,50,60,60,60,70,70,70,80,80)metrique c basee sur une norme l2

Tab. 12.3: Parametrage pour les comparaisons de SPSDR avec SP.

123


decision pour chaque expert dans cette configuration est 701, ce qui repre-sente 1.17% du nombre de nœuds du peigne representant C.

Notons que le choix de la norme (l2 ou l1 ponderee) a un impact marginalsur la qualite des resultats.

La figure 12.1 presente l’algorithme de calcul des ensembles de decisionutilise par l’approche SPSDR. Nous l’utilisons pour resoudre T−2 problemesde p-medianes. Trouver une solution exacte est NP-difficile pour ces pro-blemes, alors nous allons nous contenter d’une solution approchee. Nousproposons l’algorithme suivant base sur l’arrondi aleatoire [72]. Les calculsdes ensembles de decision etant independants d’une periode a l’autre, nouspresentons le cas general du calcul pour la periode t.

Etape 1 Resoudre la relaxation lineaire du probleme (6.20). La relaxationlagrangienne est une methode de choix pour resoudre ce problemede programmation lineaire de grande taille. Dans notre cas, nousutilisons Proximal-ACCPM [6]. La solution d’une telle relaxationest une solution optimale reelle β∗, avec

∑i β∗i = νt.

Etape 2 Creer des valeurs entieres β par une methode d’arrondi aleatoire.A chaque fois qu’une solution entiere est generee, nous evaluons soncout a travers f . La methode d’arrondi aleatoire est repetee un grandnombre de fois, et la meilleure solution entiere est retenue. L’algo-rithme s’arrete apres un nombre maximum d’iterations autorisees,ou bien apres qu’un certain nombre d’iterations ait ete fait sansameliorer la meilleure solution.

La procedure d’arrondi aleatoire est definie comme suit : A chaquei, nous associons une variable aleatoire de Bernouilli Xi avec uneprobabilite β∗i d’etre egale a 1. L’element i est une mediane si Xi = 1.Si le nombre de medianes est inferieur a Rt, nous choisissons unelement i aleatoirement parmi ceux qui ne sont pas encore designesmediane. Nous realisons un tirage aleatoire binaire. Si le resultatest 1, l’element i est ajoute aux medianes. La procedure est repeteejusqu’a avoir exactement Rt medianes. Nous calculons le cout d’unetelle solution et le sauvegardons.

Fig. 12.1: Algorithme de calcul des ensembles de decision dans l’approcheSPSDR

La procedure de l’approche SPSDR dans notre cadre de travail estpresentee en figure 12.2.

124


1 Initialisation : Nous disposons d’un large ensemble de validation Vde cardinalite N , d’un ensemble de calcul C, et des parametresnecessaires aux calculs des ensembles de decision (Rt, c, E).

2 Optimisation :

2.1 Expertise : Nous calculons les ensembles de decision avec l’algo-rithme presente en figure 12.1 sur E sous-ensembles, puis resolvonsE problemes a l’aide de CPLEX.

2.2 Combinaison : Nous combinons les regles de decision des E ex-perts.


3.1 Prediction : Nous appliquons les politiques de decisions sur l’en-semble C.

3.2 Validation : Idem 3.1 sur l’ensemble V .

3.3 Statistiques : Nous calculons differents criteres de performance.

Fig. 12.2: Cadre de travail de l’approche SPSDR

La regle de decision employee dans l’approche SPSDR est la suivante :

qnt+1 =Rt∑ν=1

vνt δDνt (σnt ), (12.6)

avec σnt = (d0, dn1 , . . . d

nt ).

Optimisation Robuste

L’approche RO consiste a reduire l’ensemble des solutions a celles quigarantissent que les contraintes seront satisfaites pour toutes les valeurspossibles des realisations de l’alea, definit a travers l’ensemble d’incertitude.Dans cette formulation, toutes les contraintes faisant intervenir les elementsincertains doivent etre des inegalites, et l’objectif lui-meme est converti enla minimisation d’une variable auxiliaire plus grande que l’objectif original.

Les ensembles d’incertitude dans [12] sont soit de simples polyhedrescentres sur une valeur nominale, soit des ellipses. Une solution qui preservela realisabilite au sein de l’ensemble d’incertitude est dite robuste. Plusl’ensemble d’incertitude est grand, plus l’ensemble des solutions robustes estpetit. Les ensembles d’incertitude peuvent etre reduits ou elargis par simplehomothecie. Un large ensemble d’incertitude reduit l’espace des solutions a

125


celles qui sont les plus conservatives, mais augmente l’immunisation face ades evenements risques.

RO est initialement prevu pour resoudre des problemes statiques. Pourtraiter le cas dynamique, les auteurs de [13] ont introduit le concept desolution robuste lineairement ajustable ou solution AAR, pour affinely ad-justable robust, qui n’est autre qu’une regle de decision lineaire : le recoursest une fonction affine des realisations passees. Les parametres de ces fonc-tions sont les variables inconnues de cette formulation. La regle employeepar l’approche RO est la suivante :

qt+1 = v0t +

t∑τ=1

vτt × dτ , (12.7)

avec σT = (d0, d1, . . . dT ) un scenario appartenant a l’ensemble d’incertitude

Uρ = σT ∈ do × RT : | dt − 100 | ≤ ρ× 70, t = 1, . . . T (12.8)

de niveau d’immunisation ρ.Une solution est donc un ensemble de valeurs pour ces variables vτt et

les fonctions lineaires resultantes peuvent etre vues comme des politiquesde decision qui decrivent l’action a prendre, en fonction des realisations. Leprobleme multi-etapes utilisant les AAR est nomme AARC, le C correspon-dant a counterpart. La fonction objectif du probleme robuste dans le cas deRSFC est la suivante :

minx,w,q,E,σ∈Uρ

E (12.9)

Aux contraintes (12.1b) a (12.1d) de la version deterministe, qui doiventetre verifiees pour toute valeur de l’ensemble de l’incertitude, et a la regle(12.7), nous ajoutons la contrainte suivante pour tout scenario, traduisantavec la variable E le critere min-max de la fonction objectif :

E ≥ −s[xT ]+ +T∑t=1

ctqt +T∑t=1

ht[xt]+ + pt[−xt]+

+T∑t=1

α+t [qt − wt]+ + α−t [wt − qt]+ (12.10)

+T∑t=1

β+t [wt − wt−1]+ + β−t [wt−1 − wt]+.

126


Cette politique peut etre implementee2 sur l’ensemble V et la perfor-mance de RO peut etre evaluee. Les criteres de performance sont les memesque pour l’approche SPSDR.

En optimisation robuste, l’objectif est de minimiser le pire cout pourtoutes les demandes incluses dans un ensemble d’incertitude. Le resultatest une politique realisable sur l’ensemble de validation. Cette politique esttres conservative. Elle controle parfaitement le pire cas, mais est mauvaisesur le reste des demandes. Ce n’est pas surprenant, puisque nous ne nousinteressons pas au cout moyen. Une alternative a cette approche trop pru-dente consiste a rechercher une politique sous-optimale sur un ensembled’incertitude reduit. Cette reduction s’opere par exemple en appliquant uncoefficient a la variation reelle de l’ensemble d’incertitude. Les scenariosde l’ensemble de validation qui ne sont pas dans l’ensemble d’incertitudesont plus nombreux, et la performance sur le pire cas va se deteriorer. Ce-pendant, la reduction de l’ensemble d’incertitude facilite la resolution descontraintes dans le modele AARC et lui permet d’etre plus performant surle cout moyen. C’est du moins ce que nous observons en pratique.

Dans le modele present, les donnees incertaines sont les demandes. Rap-pelons qu’elles sont independantes et identiquement distribuees sur l’inter-vale 100 ± 70. Un probleme d’optimisation robuste de niveau d’immunisa-tion ρ resout un probleme alternatif avec les demandes i.i.d. sur l’intervalle100± (ρ× 70), avec 0 ≤ ρ ≤ 1.

La procedure de programmation robuste dans notre cadre de travail estpresente en figure 12.3.

SP

Pour calculer les ensembles de decision formant un raffinement, nous em-ployons un algorithme inspire de [44]. C’est un algorithme glouton qui pourchaque periode temporelle va choisir iterativement un scenario a conserver,puis un second, etc.. La condition d’arret n’est pas un nombre (par exempleR1 en periode 1) mais une distance d’affectation minimale a atteindre. Nousallons decrire une construction prospective (forward en anglais) de l’arbred’evenements. Le terme prospectif signifie que l’on travaille periode parperiode en commencant par la premiere. Cet algorithme est a opposer a unalgorithme retrospectif, ou backward, qui travaille depuis la derniere periodejusqu’a la premiere.

2En fonction du niveau d’immunisation, certains scenarios de l’ensemble de valida-tion peuvent ne pas appartenir a l’ensemble d’incertitude. Certaines contraintes et enparticulier les limites sur les commandes, pourraient alors ne pas etre respectees.

127


1 Initialisation : Nous disposons d’un large ensemble de validation Vde cardinalite N , d’un niveau d’immunisation ρ et d’un ensembled’incertitude Uρ, defini comme dans (12.8).

2 Optimisation : Nous resolvons le probleme AARC de fonction objectif(12.9) grace a RobCOP. Le resultat de l’optimisation nous donne uneborne superieure de cout, pour des decisions optimales appliquees ades scenarios de l’ensemble d’incertitude Uρ.


3.1 Prediction : En l’absence de C, cette phase n’est pas realisee. Laprediction consiste en la valeur optimale resultant de la resolution.

3.2 Validation : Nous appliquons les politiques de decision sur l’en-semble V . La regle de decision appliquee a un scenario σ /∈ Uρ peutcreer des decisions inferieures a Lt ou superieures a Ut. Si tel est lecas, les decisions sont tronquees afin de ne pas violer les contraintes.

3.3 Statistiques : Nous calculons differents criteres de performance(uniquement sur V).

Fig. 12.3: Cadre de travail de l’approche RO

Nous allons nous concentrer sur la facon dont un element Dνt de lapartition Pt est lui meme partitionne a la periode t+ 1.

Pour simplifier nous considerons en place de Dνt un ensemble D′ conte-nant N ′ indices de scenarios, et nous allons decrire une operation sur l’en-semble D′, qui sera finalement realisee pour l’ensemble D1

1, puis pour lesensembles Dν2 , et ainsi de suite jusqu’en periode T − 1. L’algorithme estpresente en figure 12.4.

A la premiere periode, la procedure est faite sur l’ensemble de calcul, ouplus precisement sur l’ensemble des indices des scenarios de l’ensemble decalcul N . A la periode 2, la procedure est realisee K fois sur les K sous-ensembles issus des parties Dk1 de la partition P1. La meme procedure estrepetee sur chaque sous-ensembles de parties.

Pour rendre cette methode applicable, nous devons specifer la metriquec et le parametre εt. Soient σat and σbt deux sous-scenarios avec commedernieres realisations respectivement ξat and ξbt . Alors nous prenons :

c(σat , σbt ) = ||ξat − ξbt ||2.

128


Entree Un ensemble D′, une metrique c permettant de mesurer ladistance separant des sous-scenarios terminant en t + 1 et un parametrede tolerance εt+1.

Sortie Une partition Dkt+1′k=1,...,K de D′ et un ensemble R′t+1 d’indices

de scenarios reference avec leurs probabilites associees πk, avec la proprieteque la distance, au sens de (6.17), entre la distribution de probabilitedes scenarios reference et la distribution uniforme de tous les scenariosappartenant a D′ n’excede pas εt+1.

Pseudo-code

Initialisation µ =∞, K = 0 and D′t+1 = ∅.while µ ≥ εt+1 do

for all n ∈ D′ \ R′t+1 dofor all m ∈ D′ dorm = arg min

i∈R′t+1∪nc(σmt+1, σ

it+1)

end forµn =

∑m∈D′

πmc(σmt+1, σ

rmt+1)

end forn∗ = arg min

n∈D′\R′t+1

µn

µ← µn∗R′t+1 ← R′t+1 ∪ n∗K ← K + 1for all k ∈ 1, . . . , K do

Soit k′ le keme element de l’ensemble R′t+1

Dkt+1′= n | arg min

m∈R′t+1

c(σnt+1, σmt+1) = k′, n ∈ D′

end forend while

Fig. 12.4: Algorithme glouton type forward pour partitionner un ensemblede decision

129


Le parametre εt se definit a travers la fonction :

εt =εrel × εmax

T

(1 + q(1− t

T)

),

εmax etant la plus grande distance entre deux scenarios dans l’ensemble decalcul et q et εrel, tous deux entre 0 et 1, les veritables parametres a definir.

Les meilleures valeurs3 pour ces derniers, sur base de nombreux tests,sont q = εrel = 1.

Nous avons aussi a choisir les εt,k. En effet, la condition d’arret de laboucle while doit etre adaptee pour chaque sous-ensemble cree. Supposonsque l’algorithme trouve K medianes a la periode t, alors il y a K problemesindependants de p-medianes a resoudre en periode t + 1, chacun avec sonpropre εt+1,k defini tel que

∑Kk=1 εt+1,k ≤ εt+1. Sans plus d’indications sur

les valeurs choisies notamment dans [44], nous choisissons les εt+1,k de telle

sorte que :∑K

k=1 εt+1,k = εt+1. Les valeurs sont proportionnelles a la taillede l’ensemble Dkt+1 par rapport a la taille de l’ensemble D′t dont il est issu.

La procedure de programmation stochastique dans notre cadre de travailest comme la figure 12.5.

1 Initialisation : Nous disposons d’un large ensemble de validation Vde cardinalite N , d’un ensemble de calcul C, et des parametresnecessaires a la reduction de l’arbre (c, εrel, q, etc).

2 Optimisation :

2.1 Reduction de l’arbre par l’algorithme presente en figure 12.4.

2.2 Optimisation : resolution du probleme deterministe equivalentgrace a CPLEX.


3.1 Prediction : Nous appliquons les politiques de decision sur l’en-semble C.

3.2 Validation : Idem 3.1 mais sur l’ensemble V .

3.3 Statistiques : Nous calculons differents criteres de performance.

Fig. 12.5: Cadre de travail de l’approche SP

3Les valeurs qui donnent le meilleur resultat lors de la validation sur l’ensemble V.

130

CVaR applique au modele RSFC

12.3 CVaR applique au modele RSFC

Dans l’approche SPSDR, nous allons employer des fonctions objectifsdifferentes, et notamment des criteres de CVaR. Dans cette section nousnous interessons a l’approche CVaR comme decrite au chapitre 11. La for-mulation est la meme que pour l’approche SPSDR standard. Les parametreset les methodes employees sont elles-aussi identiques. Le changement residedans la repetition de la phase d’optimisation. Nous considerons que le de-sign des ensembles Se type 1 n’est qu’une version simplifiee du type 2. Nousne developpons donc que le type 2, comme presente en figure 12.6.

131


1 Initialisation : Nous disposons d’un large ensemble de validation V decardinalite N , d’un ensemble de calcul C, des parametres necessairesaux calculs des ensembles de decision (Rt, c, E), et de la valeur γ.

2 Optimisation :

2.1 Expertise : Nous calculons les ensembles de decision avec l’al-gorithme presente en figure 12.1 sur E sous-ensembles Se, puisresolvons E problemes a l’aide de CPLEX.


2.3 Creation des ensembles Se : Nous definissons les nouveaux en-sembles Se envoyes aux experts, sur base de l’ensemble M, commedefini dans la figure 11.4.

2.4 Expertise : Nous calculons les ensembles de decision avec l’al-gorithme presente en figure 12.1 sur E sous-ensembles Se, puisresolvons E problemes a l’aide de CPLEX.



3.1 Prediction : Nous appliquons les politiques de decision sur l’en-semble C.

3.2 Validation : Idem 3.1 sur l’ensemble V .

3.3 Statistiques : Nous calculons differents criteres de performanceavec les regles calculees sur les Se, mais aussi avec les regles cal-culees sur les Se afin de pouvoir mesurer l’apport de la creation desensembles Se.

Fig. 12.6: Cadre de travail de l’approche SPSDR avec objectif CVaR etensembles Se type 2

132

Chapitre 13

Les resultats numeriques

Sommaire

13.1 Ensemble de calcul de 2000 scenarios . . . . . . . . . . 134

Regles de decision constantes par morceaux (SPSDR) . 134

Programmation stochastique standard (SP) . . . . . . . 136

Optimisation robuste (RO) . . . . . . . . . . . . . . . . 138

13.2 Ensemble de calcul de 5000 scenarios . . . . . . . . . . 139

13.3 Les decisions de premiere periode . . . . . . . . . . . . 142

13.4 Les politiques de recours . . . . . . . . . . . . . . . . . 145

13.5 Gestion du risque avec SPSDR . . . . . . . . . . . . . . 146

13.6 Temps de calcul . . . . . . . . . . . . . . . . . . . . . . 147

Une partie des resultats numeriques de ce chapitre sont tires de [87].Dans ce chapitre, nous comparons la performance des politiques de decisiongenerees par les trois methodes : programmation stochastique avec regles dedecision constantes par morceaux (SPSDR), programmation stochastiquestandard (SP), et programmation robuste (RO). L’ensemble de validationest le meme pour toutes les experiences et contient 100.000 scenarios. Pourles approches SPSDR et SP, nous utilisons successivement des ensemblesde calcul de 2000 puis 5000 scenarios. Dans les deux cas, les deux methodesrecoivent le meme ensemble de calcul tire aleatoirement depuis V .

133

13. Les resultats numeriques

13.1 Ensemble de calcul de 2000 scenarios

Regles de decision constantes par morceaux (SPSDR)

Le tableau 13.1 presente les resultats avec SPSDR. Chaque colonnecorrespond a une fonction objectif differente : esperance de cout (coutmoyen), la moyenne entre le cout moyen et un CVaR0,05 (cout combine), unCVaR0.05, un CVaR0.01, et la minimisation du cout maximum (cout maxi-mum). Plus on se deplace vers la droite, et plus on prend en compte lerisque, jusqu’au risque extreme. Les lignes du tableau nous donne les per-formances mesurees, realisees, pour plusieurs criteres sur les ensembles C etV . La premiere partie horizontale du tableau nous donne les performancessur C. La premiere ligne nous donne la valeur que la fonction objectif (coutmoyen, cout combine, etc.) realise sur C, alors que la seconde nous donne lecout moyen calcule. La seconde partie horizontale nous donne des resultatsplus complet sur l’ensemble V .

La performance sur C peut etre interpretee comme une valeur predictivede la SPSDR a comparer aux valeurs realisees sur V .

Fonction objectifcout cout CVaR cout

moyen combine 5% 1% maximum

Performance sur Cfonction objectif 15985 18306 19689 21829 25205cout moyen 15985 16554 17105 17409 17409

Performance sur Vcout moyen 15980 16587 17140 17441 17441cout combine 18965 18400 18547 18671 18670CVaR0.05 21950 20214 19954 19901 19899CVaR0.01 24644 22748 22271 22031 22028cout maximum 31200 31251 30458 29674 29676

Tab. 13.1: Performance de SPSDR avec differents objectifs (| C |= 2000)

Les valeurs en gras formant une diagonale dans la partie s’interessant aV doivent etre comparees a la premiere s’interessant a C. Pour chaque paire,la difference relative entre les deux valeurs est interpretee comme une erreurde prediction, epred. Nous calculons aussi l’erreur sur le cout moyen, valeurabsolue de la difference relative du cout moyen sur C et du cout moyen surV , note ecout moyen.

134

Ensemble de calcul de 2000 scenarios

Nous presentons les erreurs de prediction dans le tableau 13.2.



epred 0.03% 0.51% 1.33% 0.92% 15.0 %ecout moyen 0.03% 0.20% 0.20% 0.18% 0.18%

Tab. 13.2: Les erreurs de prediction avec SPSDR (| C |= 2000)

De facon assez surprenante, les politiques de decision calculees par SPSDRrealisent quasiment les memes performances sur C et sur V . Les valeursdu tableau 13.2 montrent que SPSDR se comporte tres bien (en terme deprediction) avec le cout moyen comme fonction objectif. Elle est par contremoins performante lorsque la fonction objectif prend en compte la mesurede risque. Nous notons aussi que quelle que soit la fonction objectif, le coutmoyen est sensiblement le meme sur C et sur V .

Revenons sur le tableau 13.1. Nous observons que lorsque la fonctionobjectif est de plus en plus sensible au risque, le cout moyen augmente (ilempire), le cout combine est stable, et les trois derniers criteres diminuent.Cependant, SPSDR n’est pas tres efficace avec la mesure de risque extreme.Il est difficile de creer une politique qui minimise le cout maximum sur desensembles envoyes a chaque expert ne contenant que 200 scenarios.

Le tableau 13.3 nous donne des informations sur la dispersion des couts,et l’ecart relatif (=(cout maximum − cout minimum)/cout moyen) pour lesdivers objectifs.



Performance sur Vcout maximum 31200 31251 30458 29674 29676cout minimum 12744 14748 15612 16007 16011ecart-type 2047 1131 857 768 767ecart relatif 115.5% 99.5% 86.6% 78.4% 78.3%

Tab. 13.3: Dispersion des couts pour les differents objectifs avec SPSDR(| C |= 2000)

135


Programmation stochastique standard (SP)

Pour la programmation stochastique, nous considerons generalementque la valeur optimale obtenue apres optimisation sur l’arbre d’evenementsreduit est la solution, ou tout du moins une valeur predictive de f ]. Dansle cas de SPSDR, l’optimisation est realisee sur l’ensemble C, et non surun sous-ensemble de ce dernier. La valeur de ce que l’on a appele la fonc-tion objectif est obtenu par application de la regle combinee sur C. Voilapourquoi nous allons dans notre approche SP aussi appliquer les regles dedecision successivement sur C puis sur V .

Nous travaillons avec le meme ensemble que celui qu’a utilise SPSDR.Apres construction de l’arbre d’evenements par la methode decrite en sec-tion 12.2, nous construisons des politiques de decision en utilisant les memesfonctions objectifs que pour SPSDR. Le tableau 13.4 reporte les memesresultats que le tableau 13.1, mais pour l’approche SP.



Performance sur Cfonction objectif 15818 18288 20183 23920 25914cout moyen 15818 16393 17627 18442 19135

Performance sur Vcout moyen 16907 17532 18812 19642 20386cout combine 20736 20844 22194 23087 23915CVaR0.05 24565 24155 25576 26532 27445CVaR0.01 27655 27035 28503 29447 30390cout maximum 36171 35728 35614 36885 39016

Tab. 13.4: Performance de SP avec differents objectifs (| C |= 2000)

Pour faciliter les comparaisons, nous reproduisons dans le tableau 13.5les performances respectives de SPSDR et de SP sur V avec les differentsobjectifs.

SPSDR donne de meilleurs resultats que SP sur ce probleme. Les resultatss’ameliorent avec l’augmentation de la prise en compte du risque.

Les deux prochains tableaux sont les equivalents de ceux presentes dansl’approche SPSDR. Le tableau 13.6 correspond au tableau 13.2 et le tableau13.7 correspond au tableau 13.3.

Alors que SPSDR est capable de produire des predictions assez justes, a

136




SPSDR 15980 18400 19954 22031 29676SP 16907 20844 25576 29447 39016amelioration relative 5.5% 11.7% 22.0% 25.2% 23.9%

Tab. 13.5: Performances comparees de SPSDR et SP

Fonction Objectifcout cout CVaR cout


epred 6.88% 13.97% 22.16% 23.10% 50.56%ecout moyen 6.88% 6.94% 6.72% 6.51% 6.54%

Tab. 13.6: Les erreurs de prediction avec SP (| C |= 2000)

Objective functionscout cout CVaR cout


Performance sur Vcout maximum 36171 35728 35614 36885 39016cout minimum 12415 13948 15444 16494 17347ecart-type 2768 2248 2221 2254 2321ecart-relatif 140.5% 124.2% 107.2% 103.8% 106.3%

Tab. 13.7: Dispersion des couts pour les differents objectifs avec SP (| C |=2000)

l’exception du critere de cout maximum, SP fait des predictions optimistes.Le cout moyen predit (sur C) pour tous les objectifs est lui aussi tres sous-estime, au contraire de ce qu’a fait SPSDR. Le dernier tableau montre uneplus grand dispersion des couts avec SP. Notons que la dispersion et l’ecart-type ne diminuent que moderement lorsque les objectifs prennent en compteplus de risque.

137


Optimisation robuste (RO)

Pour l’approche RO, nous experimentons differents niveaux d’immu-nisation de ρ = 30% a ρ = 100% afin de traduire une prise en comptevariable du risque. Nous serons alors en mesure de plus facilement com-parer RO avec SPSDR et ses differentes fonctions objectif. Les politiquesde decision calculees sur les differents ensembles d’incertitude (de differentsniveaux d’immunisation) sont appliquees, validees sur le meme ensemble devalidation V , le meme qu’ont utilise les approches SP et SPSDR.

Dans le tableau 13.8, nous presentons les resultats des solutions robustesoptimales avec differents niveaux d’immunisation. La colonne de gauche listeles criteres de performance calcules.

niveau d’immunisationPerformance 29% 43% 57% 71% 86% 100%

prediction de ROcout maximum 15064 16595 18127 19659 21191 22722

Performance sur Vcout maximum 25998 24760 23724 22732 21840 22284cout moyen 18158 18367 18777 19386 20195 21204CVaR0.01 22555 21807 21295 21055 21152 21868cout minimum 14742 15755 16835 17940 19058 20187ecart-type 1458 1116 795 516 316 253ecart relatif 62.0% 49.0% 36.7% 24.7% 13.8% 9.9%

Tab. 13.8: Performance de RO avec differents niveaux d’immunisation

Nous observons que le cout moyen augmente, comme l’on pouvait s’y at-tendre, lorsque le niveau d’immunisation augmente, alors que le cout maxi-mum et le CVaR0.01 diminue, tout du moins sur les quatre premiers niveauxd’immunisation. Les deux dernieres lignes nous donnent une idee de la dis-persion. Il est interessant de noter que l’ecart-type et l’ecart relatif diminuede facon significative. De facon assez surprenante, il semble qu’une poli-tique de decision qui realise une bonne protection contre le pire cas, realisedes couts similaires sur tous les scenarios. La distribution des couts a unedispersion faible, et la performance de cout moyen est mediocre. (Nous rap-pelons que l’objectif de la RO n’est en aucun cas la minimisation du coutmoyen.)

Il est interessant de regarder les fonctions de densite des couts sur l’en-semble V avec RO et SPSDR. La figure 13.1 montre les couts pour trois

138


fonctions objectif utilisees avec l’approche SPSDR, et trois niveaux d’immu-nisation pour la RO. Le diagramme illustre notre observation que les deuxmethodes realisent differents objectifs et ont des performances differentes.RO realise un bon controle du pire cas, mais a un comportement moyenmediocre sur V . L’approche SPSDR est capable de faire des compromisentre les differents objectifs.

1.2 1.4 1.6 1.8 2 2.2 2.4

x 104

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6x 10−3

a: SPSDR, obj: mean costb: SPSDR, obj: mixturec: SPSDR, obj: max cost1: RO, immunization: 29%2: RO, immunization: 71%3: RO, immunization:100%

a

b

c

1

2 3

Fig. 13.1: Courbes de densite empirique avec RO (et 3 niveaux d’immuni-sation) et SPSDR (et 3 objectifs)

13.2 Ensemble de calcul de 5000 scenarios

Dans cette etude, nous nous interessons uniquement au critere de coutmoyen. Le tableau 13.9 donne les principaux resultats. La principale conclu-sion est que l’erreur de prediction avec SP est plus importante. De faconassez surprenante, l’erreur de prediction sur C represente la moitie de l’er-reur totale pour SP (l’erreur totale entre le resultat de l’optimisation et lavalidation sur V est de plus de 10.5%). Avec SPSDR, l’erreur est moindre.L’autre resultat important est que le cout moyen de SPSDR est meilleur

139


SP SPSDR∗ amelioration

optimisation 14992validation sur C 15815 15827 -0.08%validation sur V 16762 15961 4.78%epred 5.65% 0.85%∗L’ensemble C est divise en 10 sous-ensembles Se de tailleN = 500

Tab. 13.9: Couts moyens avec SP et SPSDR (| C |= 5000)

de pres de 5% par rapport a celui fournit par SP. Il est aussi interessantde comparer la performance de SPSDR sur V par rapport au calcul surun ensemble C de 2000 scenarios. Dans le tableau 13.1, SPSDR realise unevaleur de 15980, seulement 0.1% moins bien que 15961, en depit de la taillereduite de C.

Nous presentons dans le tableau 13.10 les valeurs d’autres criteres deperformance, et illustrons les distributions des couts dans la figure 13.2.

SP SPSDR amelioration

cout moyen 16762 15961 4.78%cout minimum 12266 12768 -4.09%cout maximum 35396 34423 2.75%CVaR0.01 27143 25658 5.47%CVaR0.05 24124 22518 6.66%CVaR0.10 22664 21030 7.21%

Tab. 13.10: Criteres complementaires sur les couts pour SP et SPSDR(| C |= 5000)

Le prochain tableau 13.11 nous donne une idee du comportement de SPet SPSDR lorsque l’ensemble de calcul varie.

La premiere colonne traite de SP avec un unique ensemble de calculde cardinalite 5000. Cette colonne est reproduite du tableau 13.9. Dans leseconde colonne, les valeurs correspondent a l’implementation de SP sur10 sous-ensembles de taille 500, a l’image des avis d’experts. Pour cha-cun d’eux, nous avons calcule la valeur optimale sur des Se, et valide letout sur V . On a ensuite calcule la moyenne des 10 validations. Commeon pouvait s’y attendre, plus l’ensemble de calcul est petit, et plus l’erreurde prediction est grande, et amene a des mauvais resultats pour la valida-tion. Les deux colonnes suivantes montrent l’equivalent des deux premieres

140


1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 3

x 104

0

0.5

1

1.5

2

2.5

3

3.5x 10

!4

SP

SPSDR

Fig. 13.2: Courbes de densite empiriques

SP SPSDR

E 1 10 1 10 10N 5000 500 5000 500 500combinaison non non ouivalidation sur C 14992 14681 15649 15520 15827validation sur V 16762 17394 16015 16322 15961epred 11.81% 18.48% 2.34 % 5.17% 0.85%

Tab. 13.11: Impact de la valeur de N et effet de la combinaison des regles(| C |= 5000)

141


dans une approche SPSDR. La derniere colonne reproduit la troisieme co-lonne du tableau 13.9. Elle confirme que combiner les regles avec SPSDRdonne de meilleurs resultats. Il est aussi interessant de noter que SPSDRen moyenne sur 10 ensembles de 500 scenarios donne de meilleurs resultatsque l’approche SP avec un ensemble de calcul de 5000 scenarios.

Le tableau 13.12 montre que SPSDR fait mieux que SP sur chaqueensemble Se de 500 scenarios. La performance de SPSDR est aussi plusstable, avec un ecart-type a peu pres quatre fois plus petit.

e SP SPSDR amelioration

1 17282 16276 6.18%2 17423 16391 6.30%3 17353 16388 5.89%4 17146 16302 5.18%5 17308 16329 6.00%6 17358 16315 6.39%7 17539 16305 7.57%8 17474 16297 7.22%9 17345 16353 6.07%10 17717 16270 8.89%

ecart-type 156.14 42.57

Tab. 13.12: Performances de SP et SPSDR sur V avec 10 ensembles Sedistincts, N = 500.

13.3 Les decisions de premiere periode

Dans cette section, nous nous interessons aux valeurs des variables depremiere periode (w1, . . . w12).

Nous representons en figure 13.3 les valeurs des engagements trouvesavec les differentes fonctions objectif utilisees pour l’approche SPSDR. Lesresultats avec les criteres CVaR10% et cout maximum sont identiques. Onobserve que plus le risque est pris en compte, et plus les engagements sonteleves. Un engagement eleve permet donc de faire face a moindre cout atout scenario. Cela s’explique par le cout de rupture cinq fois plus eleveque le cout de stockage. Les engagements trouves par chaque expert sontlineaires par morceaux, non croissants et possedant seulement 2 a 3 paliers.Cela permet de reduire les penalites de variations des engagements lies aucout β±t . La combinaison de ces engagements individuels efface l’aspect defonction en escalier.

La figure 13.4 presente les valeurs des engagements trouvees avec l’ap-proche RO, et differents niveaux d’immunisation. Un niveau d’immunisation

142

Les decisions de premiere periode

80

90

100

110

120

130

140

0 2 4 6 8 10 12

coût moyen

coût combiné

CVaR 5%

CVaR 1% et

coût maximum

Fig. 13.3: Les engagements de l’approche SPSDR avec differents criteresd’optimisation

100

110

120

130

140

150

160

0 2 4 6 8 10 12

14%

29%

43%

57%

71%

86%

100%

Fig. 13.4: Les engagements de l’approche SPSDR avec differents niveauxd’immunisation

a 14% est equivalent a 17, soit une variation de la demande de 1

7× 70 = 10

autour de la valeur centrale 100. Plus l’immunisation est importante, et plusles engagements sont eleves. Il semble que les engagements augmentent defacon lineaire, avec l’evolution de l’immunisation.

Enfin, la figure 13.5 presente les engagements trouves par approche SP.Le comportement par rapport au risque est identique aux precedentes ap-proches.

Il semble maintenant interessant de comparer les approches entre elles,et notamment SP et SPSDR. Commencons par les comparer sur le criteredu cout moyen, en figure 13.6. L’approche SPSDR propose un engagement

143


80

90

100

110

120

130

140

0 2 4 6 8 10 12

coût moyen

coût combiné

CVaR 5%

CVaR 1%

coût maximum

Fig. 13.5: Les engagements de l’approche SP avec differents criteres d’op-timisation

80

85

90

95

100

105

0 2 4 6 8 10 12

SPSDR

SP

Fig. 13.6: Les engagements des approches SP et SPSDR avec minimisationdu cout moyen

qui decline fortement sur la fin. SP semble plus confiant sur les ventes. Sil’on fait une moyenne mensuelle des engagements proposes, SPSDR passeun engagement moyen de 96, 75 unites, alors que SP passe un engagementmoyen de 98, 53. On pourrait croire a un exces de prudence de SPSDRpuisque la moyenne des demandes est de 100, et que le cout de rupturereste cinq fois plus eleve que le cout de stockage. Et pourtant les coutsmoyens finaux sont beaucoup plus faibles avec SPSDR (comme presentesdans les sections precedentes). Ce serait donc plutot SP qui manque deprudence.

La figure 13.7 compare les engagements de SPSDR et SP pour le critere

144

Les politiques de recours

de minimisation du CVaR5%. La premiere constatation est que l’engage-

100

105

110

115

120

125

0 2 4 6 8 10 12

SPSDR

SP

Fig. 13.7: Les engagements des approches SP et SPSDR avec minimisationdu CVaR5%

ment mensuel moyen passe par les deux methodes est quasiment identique :117.25 pour SPSDR et 116.65 pour SP. On constate ensuite que SPSDRpropose un engagement eleve les cinq premiers mois, qui decroit ensuitefortement, alors que SP propose des engagements beaucoup plus stablesdans le temps. Cependant, ces designs differents ne peuvent expliquer a euxseuls la difference de cout de 22% constatee par la validation sur V .

13.4 Les politiques de recours

La succession de decisions u′ = (u0, un′11 , . . . u

n′T−1

T−1 ) prises pour appliquerles regles optimisees sur un scenario σ′ de V est appelee une politique dedecision. On parle aussi de trajectoire decisionnelle. Une politique de recours

se limite a u′ = (un′11 , . . . u

n′T−1

T−1 ).Lorsque nous appliquons les decisions calculees avec SP, le nombre maxi-

mum de politiques potentiellement utilisees pour calculer fV est egale aunombre NT−1. Ce nombre ne peut etre superieur a NT qui dans notrepremiere etude est egale a 2000.

Lorsque nous appliquons les decisions SPSDR d’un unique expert, lenombre de politique utilisable est beaucoup plus important puisque egaleau produit des Nt, t < T , la decision en t+ 1 n’etant pas reduite a un sousensemble dependant de la decision prise en t, comme c’est le cas pour la SP.A cela nous ajoutons la combinaison des regles des experts, ce qui augmente

encore les combinaisons possibles :(∏T−1

t=1 Nt

)E.

145


Dans le cas de la programmation stochastique, l’arbre d’evenement construitcompte 1935 nœuds en T − 1, et nous utilisons 100% des trajectoires pos-sibles. Ainsi, les 100000 scenarios utilisent 1935 trajectoires de decisionsdifferentes.

Dans le cas de SPSDR, nous avons(∏T−1

t=1 Nt

)E> 10120. Ceci n’est

qu’un potentiel, car la metrique c employee doit certainement eliminer ungrand nombre de combinaisons (surtout entre experts) possibles. Apres vali-dation, il s’avere que les 100000 scenarios sont tous associes a une trajectoiredecisionnelle unique, soit 100000. Nous utilisons donc 10−113% du potentielpossible.

Ces chiffres nous parraissent tres interessants car, au premier abord,SPSDR semble reduire l’adaptabilite des politiques de recours aux aleas,etant donne l’absence de raffinement dans les partitions du peigne. Or, onse rend compte a travers les derniers chiffres que les politiques de decisionspotentielles sont beaucoup plus nombreuses que pour une approche utili-sant un arbre d’evenement et que les politiques effectivement employeessont, elles-aussi, beaucoup plus nombreuses. Bien sur, le nombre de poli-tiques utilisables est probablement tres en deca du nombre de politiquespotentielles.

Il faut noter que seules les trajectoires employees dans les ensembles Sesont controlees. Cela veut dire que l’approche SPSDR ne peut garantir unefaisabilite des politiques de decision si il y a :

– des contraintes sur les etats : au cours de la validation, une politiquede decision amenant a la violation de contraintes sur les etats pourraitetre construite. Dans ce cas, nous ne pourrions garantir la realisabilitede la politique de decision. La SP ne peut pas non plus garantir unetelle realisabilite.

– des contraintes cumulatives ou fonction des etats sur les decisions :SPSDR ne peut garantir la faisabilite sur tout scenario d’une contrainte(supposee saturee a l’optimum) sur le cumul de decision comme∑T

t=1 ut ≤ K avecK donne puisque certaines combinaisons de decisionspeuvent etre absente de la phase d’optimisation. La SP peut garantirla realisabilite dans le cas de contraintes cumulatives, mais pas si lescontraintes sont fonction des etats.

13.5 Gestion du risque avec SPSDR

Nous avons applique une re-optimisation sur des ensembles Se commedecrit en chapitre 11. Le tableau 13.13 montre les resultats d’applicationdes regles de decision (RD) calculees sur les Se (les chiffres proviennent du

146

Temps de calcul

tableau 13.1) et des regles de decision calculees sur les Se.

RD sur Se RD sur Se amelioration

Performance sur Cfonction objectif CVaR5% 19689 19031 3.34%cout moyen 17105 17327

Performance sur Vcout moyen 17140 17346CVaR5% 19954 19353 3.01%CVaR10% 22271 21131cout maximum 30458 31252

epred 1.35% 1.69%

Tab. 13.13: Performance des ensembles Se avec (| C |= 2000)

Le premier resultat interessant est l’amelioration de plus de 3% de l’ob-jectif (predit sur C et valide sur V). Ce resultat est trouve avec une erreurde prediction plus grande qu’a l’origine. Cette erreur reste cependant loinde celle obtenue avec l’approche SP qui etait, rappelons-le, de plus de 20%pour une valeur du CVaR sur V de plus de 25000.

13.6 Temps de calcul

Les informations delivrees ici sont indicatives et tres dependantes desimplementations que nous avons faites des methodes. Nous proposons lestemps de calcul des approches SP et SPSDR pour les ensembles de calcul de5000 scenarios. Les temps de calcul de l’approche RO sont beaucoup plusfaibles, de l’ordre de quelques secondes, et totallement independant de lacardinalite de C (non utilise) ou V .

L’information importante du tableau 13.14 est le temps passe par SPSDRa calculer les ensembles de decision. L’heuristique gloutonne de reductiond’arbre d’evenements pour SP a l’avantage de faire des reductions de plusen plus faciles au fur et a mesure du temps, les sous-ensembles sur lesquelselle travaille etant de plus en plus petit. Au contraire, notre heuristiqueest assez sophistiquee et en deux phases puisque nous resolvons d’abord leprobleme de p-medianes relaxe, puis nous construisons une solution entiere.De plus, l’effort de calcul est le meme pour chaque periode temporelle. Ilest cependant possible de resoudre ces sous-problemes, pour le cas present(T−1)×E = 110 problemes, en parallele. Chaque probleme est resolu en 60

147


Methode SP SPSDR

E 1 10phase de reduction 140 660† 6600phase d’optimisation 900 90 900

total 1040 750 7500

†60 secondes sont necessaires en moyenne pour ap-proximer le probleme de p-medianes. Il y a 11problemes de ce type pour T = 12. Ces 11 problemespeuvent etre resolus en parallele.

Tab. 13.14: Temps de calcul (en secondes) (| C |= 5000)

secondes environ. La phase d’optimisation est de meme duree pour les deuxapproches. Nous pouvons la aussi envisager de resoudre les E problemesd’optimisation de chaque expert en parallele, puisqu’ils sont independantsles uns des autres.

La phase de validation n’est pas presentee puisque ne comportant pasd’interet methodologique. Notons simplement que la validation avec SPSDRrequiert la recherche de politiques adaptees sur chaque expert avant decreer la politique combinee. La phase de validation est donc plus lente avecSPSDR qu’avec SP, et dependante du nombre d’experts.

148

Partie VI

Conclusion

149

Chapitre 14

Synthese

Dans la presente these nous avons propose une methode heuristiqued’approximation de problemes d’optimisation sous incertitude. Cette metho-de, appelee SPSDR, se base sur les concepts de regles de decision et d’en-sembles de decision. Elle permet de formuler un probleme multi-etapessur base d’un ensemble de scenarios, sans pour autant que ceux-ci soientpresentes sous la forme d’un arbre possedant de nombreux branchements.Les scenarios sont regroupes en ensembles de decision, calcules independam-ment d’une periode a l’autre. Cela permet d’eviter l’augmentation explosivedu nombre de variables et de contraintes du probleme tout en maintenantle respect de la non-anticipativite. La consequence de cette formulation estun oubli du passe : une limitation des observations comme base de prise dedecisions futures. Cependant, sur un grand nombre d’etapes, cela permet derendre le calcul d’une solution envisageable, et la perte d’information passeenous permet de maintenir une grande part d’incertitude residuelle. Il sembleimportant de devoir mettre en balance ces deux elements, puisque la pro-grammation stochastique standard est tres limitante sur ce second element.Cela peut expliquer les resultats trouves lors des etudes numeriques.

Nous avons applique cette methode sur un probleme de chaınes d’appro-visionnement comportant 12 etapes. Afin de comparer la solution trouveepar SPSDR, nous avons developpe des methodes standard comme les pro-grammations stochastique et robuste, et avons mis en place un mode opera-toire de validation, base sur l’application des politiques de decision sur ungrand ensemble de scenarios, que nous estimons beaucoup plus representatifque la solution de l’optimisation en elle-meme. Et nous avons d’ailleurs ob-serve que la programmation stochastique semble tres optimiste, au contrairede notre approche. Les erreurs d’approximation observees sont assez revela-trices. Afin de comparer notre approche a la programmation robuste, quisemble tres adaptee pour trouver rapidement une solution a un probleme

151

14. Synthese

a 12 etapes en prenant en compte une composante incertaine, nous avonsassocie la SPSDR avec une fonction objectif prenant en compte le risque,la programmation robuste ne s’interessant pas a un critere d’esperance. Laprogrammation robuste reste tres performante sur les pires cas, mais ren-contre des difficultes lorsqu’on s’interesse a des esperances de couts.

Dans le cadre de la prise en compte de risque dans le probleme d’op-timisation resolu avec SPSDR, nous avons constate quelques limitationsnotamment dues au fait que SPSDR travaille sur de petits ensembles, peuadaptes a la bonne gestion de pires cas. C’est pour cela que nous avons pro-pose une amelioration de la methode, par une reconstruction a posteriori denouveaux ensembles de calcul, permettant d’ameliorer de facon significativele comportement de notre methode sur les exemples proposes.

Nous avons utilise le concept d’avis d’experts au sein de la SPSDR, cequi permet une reduction drastique des temps de calculs d’optimisation, parparallelisation, meme si dans les faits nous n’avons pas mis en place un parcde calcul adapte. Nous avons observe que l’utilisation des experts amelioraitles performances de la methode sur les exemples etudies. A noter que lescalculs d’ensembles de decision peuvent etre independamment calcules parexpert, et par periode temporelle. La aussi, le recours a un grand nombre deCPU permet une reduction considerable du temps de calcul d’une solutionfinale. Cette methode heuristique est presentee comme une contributiontechnologique a la mise en œuvre de la programmation stochastique.

Nous avons aussi propose une contribution technologique avec les outilsDET2STO et AML4SP. Le premier est un outil permettant l’automatisationde la generation de la version stochastique d’un probleme deterministe for-mule avec GMPL. Le second est un site internet permettant de resoudre etde transformer les problemes de tout internaute en ligne, et uniquement avecdes outils libres. Pour permettre cette automatisation, nous avons edicte desregles de transformation apres avoir observe des similitudes dans les for-mulations deterministe et stochastique d’un meme probleme. Nous avonsaussi, afin de faciliter la mise en place de ces regles, edicte des conventionsd’ecriture du probleme dans le langage de modelisation algebrique librequ’est GMPL.

152

Chapitre 15

Perspectives

Nous avons applique l’approche par avis d’experts a la programmationstochastique utilisant des regles de decision constante par morceaux. Nouspouvons envisager de faire de meme avec la programmation stochastiquestandard. Nous pourrions alors probablement ameliorer le comportement dela programmation stochastique standard, surtout dans les cas ou l’informa-tion sur l’incertitude se limite a un ensemble de scenarios. Car dans ce cas,l’arbre d’evenements est plus delicat a construire que comme nous l’avonsfait dans nos applications numeriques, et la multiplicite des avis permettrade lisser des politiques de decision bien souvent trop adaptees aux arbresd’evenements utilises. Nous avons en effet observe que la programmationstochastique se comporte de facon optimiste, c’est a dire qu’elle proposeune solution tres adaptee a l’arbre sur lequel l’optimisation a lieu, mais queles politiques appliquees a un ensemble de validation se comportent moinsbien. Cette combinaison aurait aussi l’interet de multiplier le nombre depolitiques de decision de recours.

La SPSDR est appliquee ici a un probleme de supply chain, mais nouspouvons envisager de l’appliquer a d’autres problematiques d’optimisationsous incertitude si tant est que le probleme soit convexe et a variables d’etatnon contraintes. Il est vrai que cette derniere hypothese peut paraıtre assezrestrictive, mais il subsiste tout de meme un grand nombre de problemestraitables avec SPSDR.

Nous pouvons aussi envisager de combiner l’approche par regles de deci-sion et par arbre d’evenements. Nous pouvons par exemple penser a lagestion des premieres etapes du probleme en utilisant un arbre, puis le restedes etapes en utilisant des ensembles de decision. Il subsiste encore quelquesquestions pour la periode transitoire : comment passer d’un raffinement aune simple partition au cours de l’horizon. Nous n’avons que peu reflechia cette option, mais il nous semble qu’elle peut etre une alternative a des

153

15. Perspectives

problemes dont les recours des premieres periodes sont cruciaux, ou biencela peut etre une alternative, en horizon glissant, au contournement de ladifficulte des contraintes sur les etats, qui seraient alors garantis au moinspour les periodes gerees avec l’arbre d’evenements.

De nouvelles questions se posent si nous desirons appliquer SPSDR ades problemes contenant des variables aleatoires multidimensionnelles (enchaque etape), par exemple plusieurs produits. Nous avions un temps en-visage de creer des ensembles de decision specifiques a chaque dimension,puis de creer des intersections de ces ensembles. Cependant cette approcheva construire une solution uniquement pour les combinaisons presentes ausein de l’ensemble de calcul, ne pouvant garantir une solution realisablepour des combinaisons autre. Ainsi, une seconde approche a ete pensee.Elle consiste a resoudre des problemes de p-medianes avec des points a plu-sieurs dimensions, et donc de creer des ensembles de decision par variablemultidimensionnelle. On peut bien sur dans cette approche envisager deregrouper les points prioritairement par rapport a l’une des dimensions.

De facon plus concrete, nous desirons rediger un article sur la gestiondu risque avec SPSDR et l’utilisation de nouveaux ensembles de decision detype 1 et 2. Une ebauche a ete redigee, il faut maintenant etoffer cette article,peut etre en proposant d’autres alternatives, ou d’autres applications.

Nous pouvons entrevoir la possibilite d’automatiser l’application de reglesde decision dans des problemes deterministes. En somme, une nouvelle uti-lite donnee a l’outil DET2STO. L’application de regles de decision lineairessemblent plus facile a implementer au premier abord. Cela nous permettraita la fois d’ameliorer notre outil, et de promouvoir l’utilisation des regles dedecision.

Enfin, la perspective la plus excitante est sans conteste la combinaisondes approches RO et SPSDR : la RO a l’avantage de ne generer que peude contraintes alors qu’elle gere difficilement un bon niveau d’esperance decouts. Au contraire, la programmation stochastique permet une bonne ges-tion de l’esperance de couts alors qu’elle souffre d’une explosion du nombrede contraintes. Nous envisageons de coupler ces deux methodes et de ti-rer partie des avantages des deux methodes. Nous pensons faire cohabi-ter un ensemble d’incertitude et un ensemble de scenarios. Les contraintesdu probleme seraient alors robustifiees, alors que la fonction objectif se-rait calculee sur un ensemble de scenarios auxquels nous appliquerions lesdecisions guidees par les contraintes robustes. Il semble plus aise de fairel’hypothese que les scenarios doivent appartenir a l’ensemble d’incertitude,et qu’il doivent etre assez nombreux pour etre representatif. Par ce biaisnous calculerions une solution robuste, mais dont les politiques de decisionseraient orientes dans le but de maximiser l’esperance de profit et non de

154

maximiser le pire cas. Nous aurions alors certainement une solution in-termediaire a celles trouvees dans notre application. Un cout moyen certai-nement legerement en deca de celui de la SPSDR, mais avec un comporte-ment sur les mauvais scenarios plus performants que celui propose par laSPSDR.

155

Annexes

157

Annexe A

Le programme DET2STO

Cette premiere annexe presente le code informatique de DET2STO ecriten language Perl, qui est disponible en version electronique sur le site in-ternet


Il est soumis a une licence de l’organisation Creative Commons dispo-nible page suivante, juste avant le code informatique.

159

Creative Commons License Deed

Paternité-Pas d'Utilisation Commerciale-Partage des Conditions Initiales à l'Identique 3.0Unported

Vous êtes libres :

de reproduire, distribuer et communiquer cette création au public

de modifier cette création

Selon les conditions suivantes :

Paternité. Vous devez citer le nom de l'auteur original de la manièreindiquée par l'auteur de l'oeuvre ou le titulaire des droits qui vousconfère cette autorisation (mais pas d'une manière qui suggéreraitqu'ils vous soutiennent ou approuvent votre utilisation de l'oeuvre).

Pas d'Utilisation Commerciale. Vous n'avez pas le droit d'utilisercette création à des fins commerciales.

Partage des Conditions Initiales à l'Identique. Si vous modifiez,transformez ou adaptez cette création, vous n'avez le droit dedistribuer la création qui en résulte que sous un contrat identique àcelui-ci.

A chaque réutilisation ou distribution de cette création, vous devez faire apparaître clairementau public les conditions contractuelles de sa mise à disposition. La meilleure manière de lesindiquer est un lien vers cette page web.Chacune de ces conditions peut être levée si vous obtenez l'autorisation du titulaire des droitssur cette oeuvre.Rien dans ce contrat ne diminue ou ne restreint le droit moral de l'auteur ou des auteurs.

Ce qui précède n'affecte en rien vos droits en tant qu'utilisateur (exceptions au droit d'auteur : copies réservées à l'usage privédu copiste, courtes citations, parodie...)

#!/usr/bin/perl -w # program name : det2sto # version : 2.4 # date : April, the 28. 2008 # changes : header's update. # authors : J. Thenie and J.-Ph. Vial # web site : http://www.ordecsys.com/det2sto # contact : [email protected] # copyright : see http://creativecommons.org/licenses/by-nc-sa/2.5/ # reference: # Julien Thenie & Jean-Philippe Vial & Christian van Delft: # "Automatic formulation of stochastic programs via an algebraic modeling language", # Computational Management Science, 4, 17-40, 2007. #--------------------------------------+ # Main Function | #--------------------------------------+ # recognize the name of the input files my $input = shift(@ARGV); my $filename = read_parameters($input,0); # read the input files my @pbsequence = read_files($filename); # transform the input problem into a deterministic equivalent @pbsequence = transform_problem(@pbsequence); # write the output files write_detequidat(@pbsequence,$filename); write_detequimod(@pbsequence,$filename); #--------------------------------------+ # SUBROUTINES | #--------------------------------------+ #--------------------------------------+ # read_parameters | #--------------------------------------+ # READ_PARAMETERS reads the input parameter of the program, # change the STDERR in the case of a debug use, and return # the generic name of all input and output files of the Ampl # Problem sub read_parameters my ($id,$debug) = @_; if ($debug==0) close STDERR; open (STDERR,"> $id.sto.err"); return $id; #--------------------------------------+ # read_files | #--------------------------------------+ # READ_FILES launches the reading procedure for each input # files and load all data in the structure pbsequence sub read_files my $fileN = shift(@_); local @pbseq; read_deterdat($fileN); read_determod($fileN); read_stochdat($fileN); return @pbseq;

#--------------------------------------+ # read_deterdat | #--------------------------------------+ # read the deterministic data file sub read_deterdat my $i; my $type; my $name; my $info; my $filename = shift(@_); $filename .= ".dat"; my @comm = loading($filename); for ($i = 0; $i < scalar(@comm); ++$i) ($type,$name,$info) = commandID($comm[$i]); $pbseq[$i] = type => $type, name => $name, model => '', data => $comm[$i], source => 'DET', info => $info ; if ($pbseq[$i]->type eq 'SET') $pbseq[$i]->idx = 99999; #--------------------------------------+ # read_stochdat | #--------------------------------------+ # read the stochastic data file sub read_stochdat my $i; my $j; my $type; my $name; my $info; my $index; my $filename = shift(@_); $filename .= ".sto"; my @comm = loading($filename); for ($i = 0; $i < scalar(@comm); ++$i) ($type,$name,$info) = commandID($comm[$i]); $index = -1; for ($j = 0; $j < scalar(@pbseq); ++$j) if (($pbseq[$j]->type eq 'PAR') and ($pbseq[$j]->source eq 'DET')) my $name2 = $pbseq[$j]->name; if (($name2 eq $name)||($name2 =~ /\b$name\b/)) $index = $j; last; if ($index == -1) $pbseq[scalar(@pbseq)] = type => $type, name => $name, model => '', data => $comm[$i], source => 'STO', info => $info

; else if ($pbseq[$index]->info eq 'MULTI') die "The parameter $pbseq[$index]->name must be separatly defined in the deterministic data file.\nStop"; $pbseq[$index]->data =$comm[$i]; $pbseq[$index]->source='STO'; $pbseq[$index]->info ='REDEF'; #--------------------------------------+ # read_determod | #--------------------------------------+ # read the deterministic model file sub read_determod my $i; my $j; my $type; my $name; my $info; my $index; my $filename = shift(@_); $filename .= ".mod"; my @comm = loading($filename); my $nbsets = 0; for ($i = 0; $i < scalar(@comm); ++$i) ($type,$name,$info) = commandID($comm[$i]); if ($type eq 'SET') $nbsets +=1; $index = -1; for ($j = 0; $j < scalar(@pbseq); ++$j) if (($pbseq[$j]->type eq 'PAR') or ($pbseq[$j]->type eq 'SET')) my $name2 = $pbseq[$j]->name; if (($name2 eq $name)||($name2 =~ /\b$name\b/)) $index = $j; last; if ($index == -1) if ($type eq 'SET') $pbseq[scalar(@pbseq)] = type => $type, name => $name, model => $comm[$i], data => '', source => 'DET', info => '', idx => $nbsets ; else $pbseq[scalar(@pbseq)] = type => $type, name => $name, model => $comm[$i], data => '', source => 'DET',

info => '' ; else if ($pbseq[$index]->info eq 'MULTI') die "The parameter $pbseq[$index]->name must be separatly defined in the deterministic data file.\nStop"; $pbseq[$index]->model .= ' '.$comm[$i]; if ($type eq 'SET') $pbseq[$index]->idx = $nbsets; #--------------------------------------+ # loading | #--------------------------------------+ # load an ampl file in the command structure sub loading my $filename = shift(@_); my $line; my @comm; my $nbcomm = 0; my @command; open (INPUT,$filename) or die "the data file $filename does not exist.\nStop"; while ($line = <INPUT>) @command = split(/\#/, $line,2); chomp($command[0]); if ($command[0] =~/\S+/) $comm[$nbcomm] .= ' '.$command[0]; if ($command[0] =~ /\;/) $nbcomm += 1; close(INPUT); return @comm; #--------------------------------------+ # commandID | #--------------------------------------+ #find the type and the name of a given Ampl command (model or data). sub commandID my $comm = shift(@_); my @tab; $tab[2] = ''; if ($comm =~ /^\s*param/i) $tab[1] = $'; $tab[0] = 'PAR'; elsif ($comm =~ /^\s*set/i) $tab[1] = $'; $tab[0] = 'SET'; elsif ($comm =~ /^\s*var/i) $tab[1] = $';

$tab[0] = 'VAR'; elsif ($comm =~ /^\s*(min|max)imize/i) $tab[1] = $'; $tab[0] = 'OBJ'; elsif ($comm =~ /^\s*subject\s+to/i) $tab[1] = $'; $tab[0] = 'CON'; if ($tab[1] =~ /^\s*(\w+)\b/) $tab[1] = $1; elsif (($tab[0] eq 'PAR')&&($tab[1] =~ /^\s*\:(\s*(\w+\s*)2,)\:/)) $tab[1] = $1; $tab[2] = 'MULTI'; else die "$comm is not an Ampl standard command.\nStop"; return @tab; #--------------------------------------+ # transform_problem | #--------------------------------------+ # TRANSFORM_PROBLEM modifies the instance of the problem to # create a stochastic version of the problem sub transform_problem my @pbseq = @_; my $kindoftree = whicheventtree(@pbseq); @pbseq = transform_variables(@pbseq); if ($kindoftree eq 'scenario') @pbseq = transform_parameters_SCEN(@pbseq); elsif ($kindoftree eq 'transition') @pbseq = transform_parameters_TRAN(@pbseq); @pbseq = transform_objective(@pbseq); @pbseq = transform_constraints(@pbseq); if ($kindoftree eq 'scenario') @pbseq = add_primitives_SCEN(@pbseq); elsif ($kindoftree eq 'transition') @pbseq = add_primitives_TRAN(@pbseq); return @pbseq; #--------------------------------------+ # whicheventtree | #--------------------------------------+ # find the type of event tree definition (scenario- or transition- based) sub whicheventtree local @pbseq = @_; my $i; my $kind = 'not known'; my @SCENkey = ('scen','scenprob','parent','meet'); my @TRANkey = ('transnb','transprob'); if (scalar(@SCENkey)==providedInfo(@SCENkey)) $kind = 'scenario';

elsif (scalar(@TRANkey)==providedInfo(@TRANkey)) $kind = 'transition'; else die "The kind of definition of the event tree cannot be recognized.\nStop"; my $definedagain = 0; for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->info eq 'REDEF') ++$definedagain; last; if ($definedagain) return $kind; else die "No stochastic process definition has been found.\nStop"; #--------------------------------------+ # providedInfo | #--------------------------------------+ # return the number of keys found in pbseq sub providedInfo my @keys = @_; my $key; my $nb = 0; foreach $key (@keys) for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->name =~ /\b$key\b/i) ++$nb; last; return $nb; #--------------------------------------+ # transform_variables | #--------------------------------------+ # transform the variables definition and declaration (rule 1) sub transform_variables my @pbseq = @_; my $i; my $j; my $n; for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->type eq 'VAR') $n = $pbseq[$i]->name; if ($pbseq[$i]->model =~ /(^.*\b$n\s*\\s*)(TIME\w*\s*)(\|\,)/i) $pbseq[$i]->model = $1."t in ".$2.",n in NodeSet[t]".$3.$'; elsif($pbseq[$i]->model =~ /(^.*\b$n\s*\\s*)(\w+)(\s+in\s+TIME\w*\s*)(\|\,)/i) $pbseq[$i]->model = $1.$2.$3.",n in NodeSet[$2]".$4.$';

else $n =''; if ($n) for ($j = $i+1; $j < scalar(@pbseq); ++$j) if (($pbseq[$j]->type eq 'VAR')||($pbseq[$j]->type eq 'PAR')) if ($pbseq[$j]->model =~ /(^.*TIME.*\b$n\s*\[\s*\w+\s*)(\,|\])/i) $pbseq[$j]->model =$1.",n".$2.$'; elsif ($pbseq[$j]->model =~ /(^.*TIME.*\b$n\s*\[\s*(\w+)\-\s*(\d+|\w+)\s*)(\,|\])/ i) $pbseq[$j]->model =$1.",kancest($2,n,$3)".$4.$'; elsif($pbseq[$j]->model =~ /(^.*\b$n\s*\[)([^\[\]]+)(\])/i) die "At least one constraint in the declaration of $pbseq[$j]->name cannot be managed.\nStop"; elsif(($pbseq[$j]->type eq 'OBJ')||($pbseq[$j]->type eq 'CON')) $pbseq[$j]->model =~ s/(\b$n\b\s*\[\s*\w+\s*)(\,|\])/$1\,n$2/ig; $pbseq[$j]->model =~ s/(\b$n\b\s*\[\s*(\w+)\-\s*(\d+|\w+)\s*)(\,|\])/$1\, kancest\[$2\,n\,$3\]$4/ig; return @pbseq; #--------------------------------------+ # transform_parameters_SCEN | #--------------------------------------+ # transform the parameters definition and declaration in the case of a scenario-based process (rule 2) sub transform_parameters_SCEN my @pbseq = @_; my $i; my $j; my $n; for ($i = 0; $i < scalar(@pbseq); ++$i) if (($pbseq[$i]->type eq 'PAR')&&($pbseq[$i]->info eq 'REDEF')) $n = $pbseq[$i]->name; if ($pbseq[$i]->model =~ /(^.*\b$n\s*\\s*)(TIME\w*\s*)(\|\,)/i) $pbseq[$i]->model = $1."t in ".$2.",n in NodeSet[t]".$3.$'; elsif($pbseq[$i]->model =~ /(^.*\b$n\s*\\s*)(\w+)(\s+in\s+TIME\w*\s*)(\|\,)/i) $pbseq[$i]->model = $1.$2.$3.",n in NodeSet[$2]".$4.$'; else die "The declaration of the stochastic parameter $n seems to be wrong.\nStop"; for ($j = $i+1; $j < scalar(@pbseq); ++$j) if (($pbseq[$j]->type eq 'VAR')||($pbseq[$j]->type eq 'PAR')) if ($pbseq[$j]->model =~ /(^.*TIME.*\b$n\s*\[\s*\w+\s*)(\,|\])/i) $pbseq[$j]->model =$1.",n".$2.$';

elsif ($pbseq[$j]->model =~ /(^.*TIME.*\b$n\s*\[\s*(\w+)\-(\d+)\s*)(\,|\])/i) $pbseq[$j]->model =$1.",kancest[$2,n,$3]".$4.$'; elsif($pbseq[$j]->model =~ /(^.*\b$n\s*\[)([^\[\]]+)(\])/i) die "At least one constraint in the declaration of $pbseq[$j]->name cannot be managed.\nStop"; elsif(($pbseq[$j]->type eq 'OBJ')||($pbseq[$j]->type eq 'CON')) $pbseq[$j]->model =~ s/(\b$n\b\s*\[\s*\w+\s*)(\,|\])/$1\,n$2/ig; $pbseq[$j]->model =~ s/(\b$n\b\s*\[\s*(\w+)\-(\d+)\s*)(\,|\])/$1\,kancest\[$ 2\,n\,$3\]$4/ig; return @pbseq; #--------------------------------------+ # transform_parameters_TRAN | #--------------------------------------+ # transform the parameters definition and declaration in the case of a transition-based process (rule 5) sub transform_parameters_TRAN my @pbseq = @_; my $i; my $j; my $n; for ($i = 0; $i < scalar(@pbseq); ++$i) if (($pbseq[$i]->type eq 'PAR')&&($pbseq[$i]->info eq 'REDEF')) $n = $pbseq[$i]->name; if ($pbseq[$i]->model =~ /(^.*\b$n\s*\\s*)(TIME\w*\s*)(\|\,)/i) $pbseq[$i]->model = $1."t in ".$2.",n in 1..transnb[t]".$3.$'; elsif($pbseq[$i]->model =~ /(^.*\b$n\s*\\s*)(\w+)(\s+in\s+TIME\w*\s*)(\|\,)/i) $pbseq[$i]->model = $1.$2.$3.",n in 1..transnb[$2]".$4.$'; else die "The declaration of the stochastic parameter $n seems to be wrong.\nStop"; for ($j = $i+1; $j < scalar(@pbseq); ++$j) if (($pbseq[$j]->type eq 'VAR')||($pbseq[$j]->type eq 'PAR')) if ($pbseq[$j]->model =~ /(^.*TIME.*\b$n\s*\[\s*(\w+)\s*\-\s*1\s*)(\,|\])/i) $pbseq[$j]->model =$1.",lastmove[$2,n]".$3.$'; # elsif($pbseq[$j]->model =~ /(^.*\b$n\s*\[)([^\[\]]+)(\])/i) # die "At least one constraint in the declaration of $pbseq[$j]->name cannot be managed.\nStop"; # elsif(($pbseq[$j]->type eq 'OBJ')||($pbseq[$j]->type eq 'CON')) $pbseq[$j]->model =~

s/(\b$n\b\s*\[\s*(\w+)\s*\-\s*1\s*)(\,|\])/$1\,lastmove \[$2,n\]$3/ig; return @pbseq; #--------------------------------------+ # transform_objective | #--------------------------------------+ # transform the objective function according to rules 1 and 2 (rule 4) sub transform_objective my @pbseq = @_; my $i; for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->type eq 'OBJ') $pbseq[$i]->model =~ s/(sum\s*\\s*(\w+)\s*in\s*TIME\w*\s*)(\,?[^\\]*\)([^\ \]+)((\+|\-)\s*sum)/$1\,n in NodeSet\[$2\]$3 nodeprob\[$2\,n\]\*$$4$$5/ig; # old command: $pbseq[$i]->model =~ s/(sum\s*\\s*(\w+)\s*in\s*TIME\w*\s*)(\,?[^\\]*\)([^\\ ]+)(\;)/$1\,n in NodeSet\[$2\]$3 nodeprob\[$2\,n\]\*$$4$$5/i; # comment: the lack of curly braquet is not a necessary condition. I have to replace the (.+) by a sentence without "TIME". $pbseq[$i]->model =~ s/(sum\s*\\s*(\w+)\s*in\s*TIME\w*\s*)(\,?[^\\]*\)(.+) (\;)/$1\,n in NodeSet\[$2\]$3 nodeprob\[$2\,n\]\*$$4$$5/i; last; return @pbseq; #--------------------------------------+ # transform_constraints | #--------------------------------------+ # transform the constraints according to rules 1 and 2 (rule 3) sub transform_constraints my @pbseq = @_; my $i; for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->type eq 'CON') # old command: $pbseq[$i]->model =~ s/(^[^\:]+\\s*(\w+)\s*in\s*TIME\w*\s*)(\,|\)/$1\,n in NodeSet\[$2\]$3/i; # comment: can now manage t-1 (a figure) or t-k (a variable) $pbseq[$i]->model =~ s/(^[^\:]+\.*\b(\w+)\s*in\s*TIME\w*\s*)(\,|\|\:)/$1\,n in NodeSet\[$2\]$3/i; return @pbseq; #--------------------------------------+

# add_primitives_SCEN | #--------------------------------------+ # add the primitives in the case of a scenario-based process sub add_primitives_SCEN my @pbseq = @_; my $i; for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->name =~ /\bscen\b/i) $pbseq[$i]->model .= 'set Scen;'; else if ($pbseq[$i]->name =~ /\bscenprob\b/i) $pbseq[$i]->model .= 'param scenprob Scen;'; if ($pbseq[$i]->name =~ /\bparent\b/i) $pbseq[$i]->model .= "param parent \Scen\ symbolic in Scen union \\'root\'\\;"; if ($pbseq[$i]->name =~ /\bmeet\b/i) $pbseq[$i]->model .= 'param meet Scen;'; $pbseq[$i]->model =~ s/\;(\w)/\;\n$1/ig; $pbseq[scalar(@pbseq)] = type => 'SET', name => 'NodeSet', model => 'set NodeSet t in 0..T:= if t = 0 then \'root\' else s in Scen: meet[s]<t;', data => '', source => 'STO', info => 'COMPUTED' ; $pbseq[scalar(@pbseq)] = type => 'PAR', name => 'ancest', model => 'param ancest t in 1..T,n in NodeSet[t] symbolic in Scen union \'root\':= if t = 1 then \'root\' else if t > meet[n] + 1 then n else parent[n];', data => '', source => 'STO', info => 'COMPUTED' ; # if k=0, kancest(t,n,k) = n ! $pbseq[scalar(@pbseq)] = type => 'PAR', name => 'kancest', model => 'param kancest t in 0..T, n in NodeSet[t], k in 0..t symbolic in Scen union \'root\':= if k =0 then n else if t = 1 or k = 1 then ancest[t,n] else kancest[t-1,ancest[t,n],k-1];', data => '', source => 'STO', info => 'COMPUTED' ; $pbseq[scalar(@pbseq)] = type => 'SET', name => 'Reverse', model => 'set Reverse := T..0 by -1;', data => '', source => 'STO', info => 'COMPUTED' ; $pbseq[scalar(@pbseq)] = type => 'PAR',

name => 'nodeprob', model => 'param nodeprob t in Reverse, n in NodeSet[t]:= if t = T then scenprob[n] else if t = 0 then 1 else nodeprob[t+1,n] + summ in NodeSet[t+1]: meet[m]=t and parent[m]=n nodeprob[t+1,m];', data => '', source => 'STO', info => 'COMPUTED' ; return @pbseq; #--------------------------------------+ # add_primitives_TRAN | #--------------------------------------+ # add the primitives in the case of a transition-based process sub add_primitives_TRAN my @pbseq = @_; my $i; for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->name =~ /\btransnb\b/i) $pbseq[$i]->model = 'param transnb t in 0..T-1;'; elsif ($pbseq[$i]->name =~ /\btransprob\b/i) $pbseq[$i]->model = 'param transprob t in 0..T-1,k in 1..transnb[t];'; $pbseq[scalar(@pbseq)] = type => 'PAR', name => 'nodenb', model => 'param nodenb t in 0..T := if t = 0 then 1 else nodenb[t-1]*transnb[t-1];', data => '', source => 'STO', info => 'COMPUTED' ; $pbseq[scalar(@pbseq)] = type => 'SET', name => 'NodeSet', model => 'set NodeSet t in 0..T:= 1..nodenb[t];', data => '', source => 'STO', info => 'COMPUTED' ; $pbseq[scalar(@pbseq)] = type => 'PAR', name => 'ancest', model => 'param ancest t in 1..T, n in NodeSet[t]:= if t = 1 then 1 else if n = 1 then 1 else if n <= ancest[t,n-1]*transnb[t-1] then ancest[t,n-1] else ancest[t,n-1]+1;', data => '', source => 'STO', info => 'COMPUTED' ; # maybe I will have to manage the case of a null k.. $pbseq[scalar(@pbseq)] = type => 'PAR', name => 'kancest', model => 'param kancest t in 1..T, n in NodeSet[t], k in 1..t:= if t = 1 or k = 1 then ancest[t,n] else kancest[t-1,ancest[t,n],k-1];', data => '',

source => 'STO', info => 'COMPUTED' ; $pbseq[scalar(@pbseq)] = type => 'PAR', name => 'lastmove', model => 'param lastmove t in 1..T, n in NodeSet[t]:= n-(ancest[t,n]-1)*transnb[t-1];', data => '', source => 'STO', info => 'COMPUTED' ; $pbseq[scalar(@pbseq)] = type => 'PAR', name => 'nodeprob', model => 'param nodeprob t in 0..T, n in NodeSet[t]:= if t = 0 then 1 else transprob[t-1,lastmove[t,n]]*nodeprob[t-1,ancest[t,n]];', data => '', source => 'STO', info => 'COMPUTED' ; return @pbseq; #--------------------------------------+ # write_detequidat | #--------------------------------------+ # write the output data file (deterministic equivalent) sub write_detequidat my @pbseq = @_; my $fileN = pop(@pbseq); my $i; $fileN .= '.sto.dat'; open (OUTPUT,"> $fileN") or die "the output data file $fileN cannot be created.\nStop"; for ($i = 0; $i < scalar(@pbseq); ++$i) if (($pbseq[$i]->type eq 'PAR')||($pbseq[$i]->type eq 'SET')) print OUTPUT "$pbseq[$i]->data\n" if ($pbseq[$i]->data); close(OUTPUT); #--------------------------------------+ # write_detequimod | #--------------------------------------+ # write the output model file (deterministic equivalent) sub write_detequimod my @pbseq = @_; my $fileN = pop(@pbseq); $fileN .= '.sto.mod'; open (OUTPUT,"> $fileN") or die "the output model file $fileN cannot be created.\nStop"; for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->name eq 'T') print OUTPUT "$pbseq[$i]->model\n"; $pbseq[$i]->info = 'LOADED'; last;

for ($i = 0; $i < scalar(@pbseq); ++$i) if (($pbseq[$i]->type eq 'SET')&&($pbseq[$i]->name =~ /^\s*TIME\w*\s*$/i)) print OUTPUT "$pbseq[$i]->model\n"; $pbseq[$i]->info = 'LOADED'; for ($i = 0; $i < scalar(@pbseq); ++$i) if (($pbseq[$i]->source eq 'STO')&&($pbseq[$i]->info ne 'COMPUTED')&&($pbseq[$i]->info ne 'REDEF')) print OUTPUT "$pbseq[$i]->model\n"; $pbseq[$i]->info = 'LOADED'; for ($i = 0; $i < scalar(@pbseq); ++$i) if (($pbseq[$i]->source eq 'STO')&&($pbseq[$i]->info eq 'COMPUTED')) print OUTPUT "$pbseq[$i]->model\n"; $pbseq[$i]->info = 'LOADED'; # old loop: #for ($i = 0; $i < scalar(@pbseq); ++$i) # if (($pbseq[$i]->type eq 'SET')&&($pbseq[$i]->source eq 'DET')) # print OUTPUT "$pbseq[$i]->model\n" if ($pbseq[$i]->info ne 'LOADED'); # $pbseq[$i]->info = 'LOADED'; # # #the new loop maintains the original order of the sets my $minidx; my $minset; do $minset = 99999; $minidx = -1; for ($i = 0; $i < scalar(@pbseq); ++$i) if (($pbseq[$i]->type eq 'SET')&&($pbseq[$i]->source eq 'DET')) if (($pbseq[$i]->info ne 'LOADED')&&($pbseq[$i]->idx < $minset)) $minset = $pbseq[$i]->idx; $minidx = $i; if ($minidx>=0) print OUTPUT "$pbseq[$minidx]->model\n"; $pbseq[$minidx]->info = 'LOADED'; until ($minidx < 0); for ($i = 0; $i < scalar(@pbseq); ++$i) if (($pbseq[$i]->type eq 'PAR')&&($pbseq[$i]->source eq 'DET')) print OUTPUT "$pbseq[$i]->model\n" if ($pbseq[$i]->info ne 'LOADED'); $pbseq[$i]->info = 'LOADED'; for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->info eq 'REDEF') print OUTPUT "$pbseq[$i]->model\n"; $pbseq[$i]->info = 'LOADED';

for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->type eq 'VAR') print OUTPUT "$pbseq[$i]->model\n"; for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->type eq 'OBJ') print OUTPUT "$pbseq[$i]->model\n"; last; for ($i = 0; $i < scalar(@pbseq); ++$i) if ($pbseq[$i]->type eq 'CON') print OUTPUT "$pbseq[$i]->model\n"; close(OUTPUT);

Annexe B

Illustrations de l’outilinteractif en ligne AML4SP

Cette annexe regroupe les principales interfaces de l’outil interactif AML4SPdisponible a l’adresse


L’interface AML4SP pour DET2STO est composee de 5 pages successives,elles-memes decomposees en plusieurs etapes (Steps).

175

B. Illustrations de l’outil interactif en ligne AML4SP

Fig. B.1: Menu principal

La Figure B.1 represente la premiere page de l’outil, le menu princi-pal. La premiere etape permet de selectionner un probleme que l’on desiretransformer/optimiser. Nous avons mis a disposition de l’utilisateur desproblemes standards, utilises notamment lors d’un seminaire du cours deGestion de Production du Master en gestion d’entreprise d’HEC. L’utili-sateur a aussi le choix de charger son propre probleme. La version de ceprobleme est deterministe. Dans la suite de cette illustration, nous allonsutiliser l’exemple simple example scn. L’etape 2 permet de lancer la secondepage de l’interface afin d’editer les fichiers AMPL du probleme deterministe.

176

Fig. B.2: Edition des fichiers du probleme deterministe

La figure B.2 est la seconde page du processus. L’etape 1 permet d’editerles fichiers AMPL du probleme deterministe. L’utilisateur peut les consulterou les modifier. Une fois les fichiers prets, l’utilisateur passe a l’etape 2, quiva lancer l’optimisation du probleme deterministe grace a GLPK. L’opti-misation est obligatoire pour acceder a la transformation. Elle garantit queles fichiers AMPL du probleme deterministe respectent la syntaxe d’AMPL,condition necessaire au bon fonctionnement du script DET2STO.

177


Fig. B.3: Resultat d’optimisation du probleme deterministe

La figure B.3 represente la premiere etape de la troisieme page. C’est leresultat de l’optimisation par GLPK. Nous pouvons voir ici qu’une solutionoptimale a ete trouvee : optimal solution found. En cliquant sur lelien result file, l’utilisateur a acces au fichier resultat genere par GLPKcontenant notamment la valeur des variables, de la fonction objectif, et desinformations duales.

178

Fig. B.4: Edition du fichier de donnees aleatoires

La figure B.4 represente la seconde etape de la troisieme page. Ellepermet a l’utilisateur d’editer le fichier AMPL contenant les informationsstochastiques. Lancer la transformation via DET2STO en cliquant sur lebouton permet a l’utilisateur de passer a la page suivante.

179


Fig. B.5: Resultat de la transformation par DET2STO

La figure B.5 represente la quatrieme page, permettant dans une premiereetape d’editer le fichier AMPL du probleme stochastique genere. Une foisle fichier verifie ou modifie, l’etape 2 propose de resoudre le probleme sto-chastique a l’aide de GLPK et de passer a l’ultime page.

180

Fig. B.6: Resultat de l’optimisation du probleme stochastique

La figure B.6 represente la cinquieme et derniere page de l’interface. Ellepermet de verifier le bon deroulement de l’optimisation, et notamment siune solution optimale a ete trouvee. On peut de nouveau consulter le fichierresultat de l’optimisation dont une illustration est donnee en Figure B.7.

181


Fig. B.7: Fichier de sortie d’optimisation de GLPK

182

Liste des figures

1.1 La chaıne de valeur de Porter . . . . . . . . . . . . . . . . . . . 71.2 Une partie de la chaıne logistique . . . . . . . . . . . . . . . . . 81.3 Les differents types de flux au sein de la chaıne logistique . . . 81.4 Propagation de l’effet Forrester dans une chaıne d’approvision-

nement de vetements [88] . . . . . . . . . . . . . . . . . . . . . 13

6.1 Un arbre d’evenements a 4 etapes (T = 3) . . . . . . . . . . . . 456.2 Structure de la matrice du deterministe equivalent, dans le cas

ou les contraintes dynamiques ne sont pas separees . . . . . . . 476.3 Differents types d’arbres d’evenements . . . . . . . . . . . . . . 496.4 Partitionnement des nœuds d’un peigne pour agregation . . . . 506.5 Les (sous-) scenarios references dans le peigne en cours d’agre-

gation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506.6 L’arbre apres agregation au sein des ensembles de decision . . . 51

8.1 Le role de l’AML dans la resolution d’un probleme . . . . . . . 648.2 Un constat simple et une absence d’outils adequats . . . . . . . 64

9.1 Model and data for the deterministic problem in ampl . . . . . 759.2 Stochastic process in the illustrative example . . . . . . . . . . . 769.3 The deterministic equivalent problem in ampl . . . . . . . . . . 779.4 Scenario description for the illustrative example . . . . . . . . . 799.5 Event tree parameters for a scenario-based representation . . . . 829.6 Transition-based representation for the example . . . . . . . . . 849.7 Event tree parameters for a transition-based representation . . . 859.8 ampl formulation of the dynamics of the perturbation . . . . . . 88

10.1 Ensembles de decision de formant pas de raffinement . . . . . . 105

11.1 Representation du VaR10% d’une v.a. qui suit N (0, 1) . . . . . 11211.2 Representation du CVaR10% d’une v.a. qui suit N (0, 1) . . . . . 11311.3 Methode de calcul sur les ensembles Se, type 1. . . . . . . . . . 115

183

Liste des figures

11.4 Methode de calcul sur les ensembles Se, type 2. . . . . . . . . . 116

12.1 Algorithme de calcul des ensembles de decision dans l’approcheSPSDR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

12.2 Cadre de travail de l’approche SPSDR . . . . . . . . . . . . . . 12512.3 Cadre de travail de l’approche RO . . . . . . . . . . . . . . . . 12812.4 Algorithme glouton type forward pour partitionner un ensemble

de decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12912.5 Cadre de travail de l’approche SP . . . . . . . . . . . . . . . . 13012.6 Cadre de travail de l’approche SPSDR avec objectif CVaR et

ensembles Se type 2 . . . . . . . . . . . . . . . . . . . . . . . . 132

13.1 Courbes de densite empirique avec RO (et 3 niveaux d’immuni-sation) et SPSDR (et 3 objectifs) . . . . . . . . . . . . . . . . . 139

13.2 Courbes de densite empiriques . . . . . . . . . . . . . . . . . . 14113.3 Les engagements de l’approche SPSDR avec differents criteres

d’optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14313.4 Les engagements de l’approche SPSDR avec differents niveaux

d’immunisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 14313.5 Les engagements de l’approche SP avec differents criteres d’op-

timisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14413.6 Les engagements des approches SP et SPSDR avec minimisation

du cout moyen . . . . . . . . . . . . . . . . . . . . . . . . . . . 14413.7 Les engagements des approches SP et SPSDR avec minimisation

du CVaR5% . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

B.1 Menu principal . . . . . . . . . . . . . . . . . . . . . . . . . . . 176B.2 Edition des fichiers du probleme deterministe . . . . . . . . . . 177B.3 Resultat d’optimisation du probleme deterministe . . . . . . . 178B.4 Edition du fichier de donnees aleatoires . . . . . . . . . . . . . 179B.5 Resultat de la transformation par DET2STO . . . . . . . . . . 180B.6 Resultat de l’optimisation du probleme stochastique . . . . . . 181B.7 Fichier de sortie d’optimisation de GLPK . . . . . . . . . . . . 182

184

Liste des tableaux

9.1 Data on the transition process . . . . . . . . . . . . . . . . . . . 87

12.1 Donnees pour le probleme RSFC, instance W12 dans [12] . . . 12112.2 Parametrage pour les comparaisons de SPSDR avec RO et SP. 12312.3 Parametrage pour les comparaisons de SPSDR avec SP. . . . . 123

13.1 Performance de SPSDR avec differents objectifs (| C |= 2000) . 13413.2 Les erreurs de prediction avec SPSDR (| C |= 2000) . . . . . . . 13513.3 Dispersion des couts pour les differents objectifs avec SPSDR

(| C |= 2000) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13513.4 Performance de SP avec differents objectifs (| C |= 2000) . . . . 13613.5 Performances comparees de SPSDR et SP . . . . . . . . . . . . 13713.6 Les erreurs de prediction avec SP (| C |= 2000) . . . . . . . . . 13713.7 Dispersion des couts pour les differents objectifs avec SP (| C |=

2000) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13713.8 Performance de RO avec differents niveaux d’immunisation . . . 13813.9 Couts moyens avec SP et SPSDR (| C |= 5000) . . . . . . . . . 14013.10Criteres complementaires sur les couts pour SP et SPSDR (|

C |= 5000) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14013.11Impact de la valeur de N et effet de la combinaison des regles

(| C |= 5000) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14113.12Performances de SP et SPSDR sur V avec 10 ensembles Se dis-

tincts, N = 500. . . . . . . . . . . . . . . . . . . . . . . . . . . 14213.13Performance des ensembles Se avec (| C |= 2000) . . . . . . . . 14713.14Temps de calcul (en secondes) (| C |= 5000) . . . . . . . . . . . 148

185

Bibliographie

[1] R. Anupindi et R. Akella : An inventory model with commitments.Rapport technique, NorthWestern University, 1993.

[2] R. Anupindi et Y. Bassok : Analysis of supply contracts with totalminimum commitment and flexibility. Rapport technique, NorthWes-tern University, 1997.

[3] R. Anupindi et Y. Bassok : Approximations for multiproductcontracts with stochastic demands and business volume discounts :single supplier case. IIE Transactions, 30:723–734, 1998.

[4] R. Anupindi et Y. Bassok : Supply contracts with quantity commit-ments and stochastic demand. In Quantitative Models for Supply ChainManagement, S. Tayur, R. Ganeshan et M. Magazine, chapitre 7. Klu-wer, 1999.

[5] P. Artzner, F. Delbaen, J.-M. Eber et D. Heath : Coherentmeasures of risk. Mathematical Finance, 9:203–229, 1999.

[6] F. Babonneau, C. Beltran, O. du Merle, C. Tadonki et J.-Ph.Vial : The proximal analytic center cutting plane method. Rapporttechnique, Logilab, HEC, University of Geneva, 2003.

[7] F. Babonneau, C. Beltran, A. Haurie, C. Tadonki et J.-Ph.Vial : Proximal-ACCPM : a versatile oracle based optimization me-thod. In Optimisation Econometric and Financial Analysis, E. J. Kon-toghiorghes. Springer Verlag, 2006.

[8] G. Baglin, O. Bruel, A. Garreau, M. Greif et C. van Delft :Management industriel et logistique. Economica, cinquieme edition,2007.

[9] Y. Bassok et R. Anupindi : Analysis of supply contracts with totalminimum commitment. IIE Transactions, 29:373–381, 1997.

[10] R. Bellman : dynamic programming. Princeton University Press,1957.

187

Bibliographie

[11] R. Bellman : Adaptive control processes - a guided tour. NavalResearch Logistics Quarterly, 8(3):315–316, 1961.

[12] A. Ben-Tal, B. Golany, A. Nemirovski et J.-Ph. Vial : Retailer-supplier flexible commitments contracts : a robust optimization ap-proach. Manufacturing and service operations management, 7:248–271,2005.

[13] A. Ben-Tal, A. Goryashko, E. Guslitzer et A. Nemirovski :Adjustable robust solutions of uncertain linear programs. MathematicalProgramming, 99(2):351–376, 2004.

[14] A. Ben-Tal et A. Nemirovski : A robust optimization - methodologyand applications. Mathematical Programming Series B, 99:453–480,2002.

[15] J. R. Birge et F. Louveaux : Introduction to stochastic programming.Springer-Verlag New York, Inc., 1997.

[16] J. Bisschop et M. Roelofs : Aimms - user’s guide. World Wide Web,http ://www.aimms.com/aimms/downloads/documentation/manuals.html.

[17] A. Brooke, D. Kendrick et A. Meeraus : GAMS : A User’s Guide.The Scientific Press, 1992.

[18] N. Cesa-Bianchi, Y. Freund, D. Haussler, D. P. Helmbold,R. E. Schapire et M. K. Warmuth : How to use expert advice.Journal of the ACM,, 44(3):427–485, 1997.

[19] F.-R. Chang : Stochastic optimization in Continuous time. CambridgeUniversity Press, 2004.

[20] F. Chen, Z. Drezner, J. K. Ryan et D. Simchi-Levi : The bullw-hip effect : managerial insights on the impact of forecasting and infor-mation on variability in a supply chain. In Quantitative Models forSupply Chain Management, S. Tayur, R. Ganeshan et M. Magazine,chapitre 14. Kluwer, 1999.

[21] C. Condevaux-Lanloy, E. Fragniere et A. J. King : Sisp : Sim-plified interface for stochastic programming. Optimization methods andsofware, 17:423–443, 2002.

[22] A. Dormer, A. Vazacopoulos et H. Tipi : Modeling and solvingstochastic programming problems in supply chain management usingxpress-sp. Rapport technique, Dash Optimization, Inc, 560 SylvanAvenue, Englewood Cliffs, NJ 07632, 2005.

188

[23] O. du Merle et J.-Ph. Vial : Proximal ACCPM, a cutting planemethod for column generation and Lagrangian relaxation : applicationto the p-median problem. Rapport technique, Logilab, HEC, Universityof Geneva, 2002.

[24] A. Dubois, J. Thenie et J.-Ph. Vial : Stochastic programming : thedet2sto tool. Rapport technique, Logilab, HEC, University of Genevaand Ordecsys, 2005.

[25] J. Dupacova, N. Growe-Kuska et W. Romisch : Scenario reduc-tion in stochastic programming. an approach using probability metrics.Mathematical Programming, 95(3):493–511, 2003.

[26] M. Dyer et L. Stougie : Computational complexity of stochasticprogramming problems. Mathematical Programming, 106(3):423–432,2006.

[27] J. Edwards, J. Birge, A. King et L. Nazareth : A standard in-put format for computer codes which solve stochastic programs withrecourse and a library of utilities to simplify its use. Rapport tech-nique WP-85-03, International Institute for Applied Systems Analysis,Laxenburg, Austria, 1985.

[28] J. W. Forrester : Industrial dynamics. The M.I.T. Press, premiereedition, 1961.

[29] Free Software Foundation : site internet du projet glpk. World WideWeb, http ://www.gnu.org/software/glpk/.

[30] R. Fourer et D. M. Gay : Proposals for stochastic programming inthe ampl modeling language. International Symposium on Mathema-tical Programming, August 1997.

[31] R. Fourer, D. M. Gay et B. W. Kernighan : AMPL a modelinglanguage for mathematical programming. The scientific Press, premiereedition, 1993.

[32] E. Fragniere, J. Gondzio, R. Sarkissian et J.-Ph. Vial : Struc-ture exploiting tool in algebraic modeling languages. ManagementScience, 46:1145 – 1158, 2000.

[33] E. Fragniere, J. Gondzio et J.-Ph. Vial : Building and solvinglarge-scale programs on an affordable distributed computing system.Annals of Operations Research, 99(1/4):167–187, 2000.

189

Bibliographie

[34] Y. Freund et R. Schapire. : Experiments with a new boostingalgorithm. Proceedings of the Thirteenth International Conference onMachine Learning, pages 148–156, 1996.

[35] Y. Freund et R. Schapire. : A decision-theoretic generalization ofon-line learning and an application to boosting. Journal of Computerand System Sciences, 55(1):119–139, 1997.

[36] J. E. F. Friedl : Mastering regular expressions. O’Reilly & Associates,1997.

[37] S. J. Garstka et R. J.-B. Wets : On decision rules in stochasticprogramming. Mathematical Programming, 7:117–143, 1974.

[38] H.I. Gassmann et A. M. Ireland : Conference presentation on sto-chastic programming. Annals of Operations Research, 44:83–112, 1996.

[39] H.I. Gassmann et E. Schweitzer : A comprehensive input formatfor stochastic linear programs. Annals of Operations Research, 104:89–125, 2001.

[40] C. R. Givens et R. M. Shortt : A class of wasserstein metrics forprobability distributions. Michigan Mathematical Journal, 31:231–240,1984.

[41] W. K. Klein Haneveld et M. H. van der Vlerk : Stochastic integerprogramming : General models and algorithms. Annals of OperationalResearch, 85:39–57, 1999.

[42] F. W. Harris : How many parts to make at once. Factory, themagazine of management, 10:135–152, 1913.

[43] H. Heitsch et W. Romisch : Generation of multivariate scenariotrees to model stochasticity in power management. ComputationalOptimization and Applications, 24(2-3):187 – 206, 2003.

[44] H. Heitsch et W. Romisch : Scenario reduction algorithms in sto-chastic programming. Computational optimization and applications,24:187–206, 2003.

[45] H. Heitsch et W. Romisch : Scenario tree modelling for multistagestochastic programs. Rapport technique, Humboldt-University Berlin,2005.

[46] J. L. Heskett : Logistics - essential to strategy. Harvard BusinessReview, 55(6):85 – 96, 1977.

190

[47] R. Hochreiter et G. Ch. Pflug : Financial scenario generation forstochastic multi-stage decision processes as facility location problems.Annals of Operations Research, 152(1):257–272, 2007.

[48] C.C. Holt, F. Modigiliani, J.F. Muth et H. Simon : PlanningProduction, Inventories, and Work Force. Prentice-Hall, New Jersey,1960.

[49] IBM : OSL Stochastic Extensions : Guide and Reference. IBM Cor-poration, 1998.

[50] ILOG : The cplex optmizer. World Wide Web,http ://www.ilog.com/products/cplex/.

[51] P. Kall et J. Mayer : The slp-ior interface. World Wide Web,http ://www.ior.uzh.ch/Pages/English/Research/StochOpt/index en.php.

[52] P. Kall et S. W. Wallace : Stochastic Programming. John Wiley &Sons, Chichester, seconde edition, 1994.

[53] O. Kariv et L. Hakimi : An algorithmic approach to network locationproblems ii : the p-medians. SIAM Journal of Applied Mathematics,37(3):539–560, 1979.

[54] D.L. Keefer : Certainty equivalents for three-points discrete distri-bution approximations. Management Science, 40:760–773, 1994.

[55] K. K. Lau et R. S. Womersley : Multistage quadratic stochasticprogramming. Journal of Computational and Applied Mathematics,129(1-2):105–138, 2001.

[56] P. L’ecuyer : Pseudorandom number generators. in Encyclopediaof Quantitative Finance, Rama Cont, Ed., in volume Simulation Me-thods in Financial Engineering, Eckhart Platen and Peter Jaeckel Eds.,Wiley, 2008.

[57] H. L. Lee et V. Padmanabhan : Information distortion in a supplychain : The bullwhip effect. Management Science, 43(4):546 – 558,1997.

[58] H. L. Lee, V. Padmanabhan et Seungjin Wang : The bullwhip effectin supply chains. Sloan Management Review, 38(3):93 – 102, 1997.

[59] F.V. Louveaux et R. Schultz : Stochastic integer programming.Handbooks in Operations Research and Mangament Science, 10, 2003.

[60] J. P. Monahan : Quantity discount pricing models to increase vendorprofits. Management Science, 30:720–726, 1984.

191

Bibliographie

[61] MOSEK : The mosek optimization software. World Wide Web,www.mosek.com.

[62] B. Murtagh : Advanced Linear Programming : Computation andPractice. McGraw-Hill, 1981.

[63] Y. Nesterov et J.-Ph. Vial : Confidence level solutions for stochasticprogramming. Automatica, 2008.

[64] Dash Optimization : The xpress mp suite. World Wide Web,www.dashoptimization.com.

[65] G. Ch. Pflug : Scenario tree generation for multiperiod financialoptimization by optimal discretization. Mathematical programming,89(2):251–271, 2001.

[66] M. E. Porter : Competitive Strategy. Techniques for analysing indus-tries and competitors. Free Press, premiere edition, 1980.

[67] A. Prekopa : Stochastic Programming. Kluwer, Dordrecht, 1995.

[68] Committee On Stochastic Programming : site internet de lacommunaute de programmation stochastique. World Wide Web,http ://www.stoprog.org.

[69] S. T. Rachev : Probability metrics and the stability of stochasticmodels. Wiley and Sons, Chichester, UK, 1991.

[70] S. T. Rachev et L. Ruschendorf : Mass transportation Problems.Springer, Berlin, 1998.

[71] S. T. Rachev et M. Taksar : Kantorovich’s functionals in space ofmeasures, pages 248–261. Springer Berlin / Heidelberg, 1992.

[72] P. Raghavan et C.D. Thompson : Randomized rounding : a tech-nique for provably good algorithms and algorithmic proofs. Combina-torica, 7(4):365–374, 1987.

[73] J. Reese : Methods for solving the p-median problem : An annotatedbibliography. Rapport technique, Department of Mathematics, TrinityUniversity, August 11, 2005.

[74] R. T. Rockafellar et S. Uryasev : Conditional value-at-risk forgeneral loss distributions. Journal of Banking & Finance, 26:1443–1471, 2002.

[75] A. Ruszczynski et A. Shapiro : Handbook in Operations Researchand Management Science : Stochastic Programming, volume 10. Else-vier, 2003.

192

[76] H. Scarf : The optimality of (s,s) policies in the dynamic inventoryproblems. In Mathematical methods in the social sciences, K. J. Arrow,S. Karlin, P. Suppes. Stanford university press, Stanford, CA, 1960.

[77] R. Schultz, L. Stougie et M. H. van der Vlerk : Two-stage sto-chastic integer programming : A survey. Journal of the NetherlandsSociety for Statistics and Operations Research, 50(3):404–416, 1996.

[78] S. Sen : Algorithms for stochastic mixed-integer programming models.Rapport technique, MORE Institute, SIE Department, University ofArizona, Tucson, AZ, 2003.

[79] A. Shapiro : Stochastic programming by monte carlo simulation me-thods. Stochastic Programming E-Print Series (SPEPS), 2000.

[80] A. Shapiro et A. Nemirovski : On complexity of stochastic pro-gramming problems. In Continuous Optimization : Current Trends andApplications, V. Jeyakumar et A.M. Rubinov, pages 111–144. Springer-Verlag New York, Inc., 2005.

[81] E. A. Silver, D. F. Pyke et R. Peterson : Inventory Managementand Production Planning and Scheduling. Wiley and Sons, 1998.

[82] D. Simchi-Levi, P. Kaminsky et E. Simchi-Levi : Designing andmanaging the supply chain. Irwin Mc Graw-Hill, 2000.

[83] H. Simon : Administrative Behavior. Macmillan, New York, NY, 1947.

[84] C. Strugarek : On the fortet-mourier metric for the stability of sto-chastic optimization problems, an example. Rapport technique, EDF,Paris, France, 2004.

[85] J. Thenie, Ch. van Delft et J.-Ph. Vial : Automatic formulationof stochastic programs via an algebraic modeling language. Computa-tional Management Science, 4:17–40, 2007.

[86] J. Thenie et J.-Ph. Vial : Stochastic programming with linear deci-sion rules, an application to the evaluation of option contracts. 10thInternational Conference on Stochastic Programming, October 2004.

[87] J. Thenie et J.-Ph. Vial : Step decision rules for multistage stochasticprogramming : a heuristic approach. Automatica, 44(6):1569–1584,2008.

[88] D. Towill : The impact of business policy on bullwhip induced riskin supply chain management. International Journal of Physical Dis-tribution and Logistics Management, 35(8):555–575, 2005.

193

Bibliographie

[89] A. A. Tsay, S. Nahmias et N. Agrawal : Modeling supply chaincontracts : a review. In Quantitative Models for Supply Chain Mana-gement, S. Tayur, R. Ganeshan et M. Magazine, chapitre 10. Kluwer,1999.

[90] S. S. Vallander : Calculation of the wasserstein distance betweenprobability distributions on the line. Theory of probability and its ap-plications, 18(4):784–786, 1973.

[91] Ch. van Delft et J.-Ph. Vial : A practical implementation of stochas-tic programming : an application to the evaluation of option contractsin supply chains. automatica, 40:743–756, 2004.

[92] A. F. Veinott : The status of mathematical inventory theory. Ma-nagement Science, 12(11):745–777, 1966.

[93] L. Wall, T. Christiansen et J. Orwant : Programming Perl.O’Reilly & Associates, troisieme edition, 2001.

[94] S. G. Wallace et K Høyland : Generating scenario trees for multi-stage decision problems. Management Science, 47:295–307, 2001.

[95] R. J.-B. Wets : Stochastic programming models : wait-and-see versushere-and-now. Rapport technique, University of California, September2000.

[96] R. J.-B. Wets et R. Van Slyke : L-shaped linear programs withapplications to optimal control and stochastic programming. SIAMJournal of Applied Mathematics, 17:638–663, 1969.

[97] R. H. Wilson : A scientific routine for stock control. Harvard BusinessReview, 13:116–128, 1934.

[98] Sun Zi : L’art de la guerre. bibliotheque strategique. Economica, 1999.

[99] V. M. Zolotarev : Probability metrics. Theory of probability and itsapplications, 28:278–302, 1983.

194

Documents

Décisions séquentielles dans l'incertain : nouvelles approches par