Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012


HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TD9 Optimisation stochastique / Stochastic Optimization

8 mai 2012 15h30 – 17h10

Salle: Xerox Canada

Présidée par Patrick Jaillet

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h30 - 15h55

    A Trust-Region Regularization for Progressive Hedging Algorithm

    • Shohre Zehtabian, prés., Université de Montréal
    • Fabian Bastin, Université de Montréal

    Progressive hedging algorithm, while twenty years old, remains popular in multistage stochastic programming due to the natural parallelization opportunities it offers. In particular, the method is still of importance for linear and convex problems, and has also received attention for mixed integer linear stochastic programs. The use of a penalty quadratic term to enforce the non-anticipative decisions is important to ensure good numerical properties, but inherently produces a nonlinear problem. We explore here the use of a trust-region regularization in place of the quadratic penalty term, preserving linearity when present. This allows the use of dedicated linear solvers, while enforcing that non-anticipativity constraints are not violated in a too large extent.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h55 - 16h20

    Stochastic Dual Dynamic Programming on Reservoir Operation with Uncertainty

    • Ziming Guan, prés., University of British Columbia
    • Ziad Shawwash, University of British Columbia
    • Alaa Abdalla, BC Hydro
    • Amr Ayad, University of British Columbia
    • Mohammadhossein Alipour, University of British Columbia

    We present a stochastic dual dynamic programming model that generates water value functions for multi-year reservoir operation in BC Hydro’s multi-reservoir hydro-electric system with uncertainty in inflow, market price and domestic load.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h20 - 16h45

    Modèle avec contraintes probabilistes et une méthode de branch-and-cut : le problème d’horaire de salles d’audience.

    • Vincent Martin, prés., École Polytechnique de Montréal

    Le problème d’horaire de salles d’audience affecte des causes d’une durée incertaine à des salles de différents types en minimisant les délais judiciaires. Le modèle tient compte de l’incertitude avec des contraintes probabilistes non-linéaires associées à chaque type de salle et chaque jour. La méthode proposée est une énumération implicite générant des coupes linéaires lors du viol des contraintes probabilistes.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h45 - 17h10

    Stochastic Online Bipartite Resource Allocation Problems

    • Antoine Legrain, prés., GERAD - Polytechnique Montréal
    • Patrick Jaillet, Massachusetts Institute of Technology

    We are interested in an online resource allocation problem (online auction) whereby buyers with
    a limited budget want to purchase items consuming a limited quantity of resources. The Google
    Adwords problem is the most famous example. There are two ways of dealing the uncertainties of
    this problem. On one side, a performance guarantee of the worst case is sought ; the primal-dual
    algorithm obtains a good bound in this case. On the other side, algorithms are studied under a chosen distribution of the information : stochastic optimization is good way to handle those uncertainties. Instead of these general approaches, we propose an innovative hybrid method that uses strengths of the two previous : under a small assumption, we propose a stochastic primal dual algorithm. We further test this procedure on sets of data whom have been randomly generated.