8671 articles  [english version]

hal-00753578, version 1

Two methods of pruning Benders' cuts and their application to the management of a gas portfolio

Laurent Pfeiffer (, http://www.cmap.polytechnique.fr/~pfeiffer/english.html) 12, Romain Apparigliato () 3, Sophie Auchapt () 3

N° RR-8133 (2012)

  • 1 :  Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP)
  • http://www.cmap.polytechnique.fr/
    Polytechnique - X – CNRS : UMR7641 CMAP UMR 7641 École Polytechnique CNRS Route de Saclay 91128 Palaiseau Cedex France
  • 2 :  COMMANDS (INRIA Saclay - Ile de France)
  • http://www.cmap.polytechnique.fr/commands/
    INRIA – CNRS : UMR7641 – Polytechnique - X – ENSTA ParisTech Centre de Mathématiques Appliquées Ecole Polytechnique Route de Saclay 91128 Palaiseau France
  • 3 :  Centre de Recherche en Etudes et Modélisation Economiques (CEEME (GDF-Suez))
  • http://www.gdfsuez.com/
    GDF-SUEZ 1 rue d'Astorg 75 392 Paris Cedex 08 France

Références bibliographiques

  • Type de publication : Rapports
  • Domaine : Mathématiques/Optimisation et contrôle
  • Titre : Two methods of pruning Benders' cuts and their application to the management of a gas portfolio
  • Résumé : In this article, we describe a gas portfolio management problem, which is solved with the SDDP (Stochastic Dual Dynamic Programming) algorithm. We present some improvements of this algorithm and focus on methods of pruning Benders' cuts, that is to say, methods of picking out the most relevant cuts among those which have been computed. Our territory algorithm allows a quick selection and a great reduction of the number of cuts. Our second method only deletes cuts which do not contribute to the approximation of the value function, thanks to a test of usefulness. Numerical results are presented.
  • Résumé français : Dans cet article, nous décrivons un problème de gestion d'un portefeuille gazier, résolu avec l'algorithme SDDP (Stochastic Dual Dynamic Programming). Nous présentons quelques améliorations de cette algorithme et nous nous concentrons sur des méthodes d'élagage des coupes de Benders, c'est-à-dire, des méthodes pour sélectionner les coupes les plus pertinentes parmi celles déjà calculées. Notre algorithme des territoires permet une sélection rapide et une grande réduction du nombre de coupes. Notre seconde méthode ne supprime que les coupes qui ne contribuent pas à l'approximation de la fonction valeur, à l'aide d'un test d'utilité. Nous présentons des résultats numériques.
  • Langue du document : Anglais
  • Type de rapport : Rapport de recherche
  • Nombre de pages : 23
  • Date de publication : 19/11/2012
  • Mots-clés : SDDP algorithm – stochastic programming – energy management – pruning methods – Benders' cuts.
  • Référence interne : RR-8133
  • Contrat, financement : L'étude a été financée et réalisée au sein du Centre d'Expertise en Etudes et Modélisation Economiques.

Liste des fichiers attachés à ce document :

PDF
RR-8133.pdf(673.3 KB)
 
  • hal-00753578, version 1
  • oai:hal.inria.fr:hal-00753578
  • Contributeur : 
  • Soumis le : Lundi 19 Novembre 2012, 14:21:25
  • Dernière modification le : Dimanche 25 Novembre 2012, 18:58:52