2022 Optimization Days

HEC Montréal, Québec, Canada, 16 — 18 May 2022

Schedule Authors My Schedule

MA9- Contextual optimization under uncertainty

May 16, 2022 10:30 AM – 12:10 PM

Location: Groupe Cholette (yellow)

Chaired by Erick Delage

4 Presentations

  • 10:30 AM - 10:55 AM

    Risk-Aware Bid Optimization for Online Display Advertisement

    • Rui Fan, presenter, HEC Montreal
    • Delage Erick, Professor, Department of Decision Sciences, HEC Montréal

    This research focuses on the bid optimization problem in the real-time bidding setting for online display advertisement, where an advertiser or the advertiser's agent has access to the features of the website visitor and the type of ad slots, to decide the optimal bidding prices. We propose a risk-aware data-driven bid optimization model that maximizes the expected profit for the advertiser by exploiting historical data to design upfront a bidding policy, mapping the type of advertisement opportunity to a bidding price, to be applied in a given period of time with a predetermined budget. After employing a Lagrangian relaxation, we derive a parametrized closed-form expression for the optimal bidding strategy. Using a real-world dataset, we demonstrate that our risk-averse method can effectively control the risk of spending over the budget for a period of time while achieving a competitive level of profit compared with the risk-neutral model and the other risk-aware bidding strategy.

  • 10:55 AM - 11:20 AM

    Data-driven stochastic VRP with routing-dependent travel time uncertainty using non-parametric methods

    • Shanshan Wang, presenter, HEC Montreal
    • Erick Delage, GERAD, HEC Montréal
    • Leandro C. Coelho, Université Laval

    In this work, we study a novel data-driven stochastic decision-dependent vehicle routing problem, where the travel time is dependent on the routing decisions. We employ non-parametric methods to estimate the routing-dependent probability distribution. In order to solve the resulting non-linear problem of more realistic sizes, we propose a logic-based Benders decomposition algorithm together with several enhancements, including a warm-start strategy, local search heuristic, and novel optimality cuts. A case study for a food delivery routing problem using real-world data is conducted to show the efficiency of the proposed solution scheme and the benefit of our model over the benchmark models in the literature through an out-of-sample analysis.

  • 11:20 AM - 11:45 AM

    Data-Driven Conditional Robust Optimization

    • Abhilash Reddy, presenter,
    • Nymisha Bandi, McGill
    • Delage Erick, Professor, Department of Decision Sciences, HEC Montréal

    In this work, we propose a novel approach for data-driven decision-making under uncertainty in the presence of contextual information. Our approach benefits from the expressive power of deep neural network structures to construct uncertainty sets conditional on contextual information. Given a finite collection of observations of the uncertain parameters and the contextual information, our approach learns to reduce the side information to a set of K classes while jointly constructing the compact uncertainty sets on the parameters. Our proposed loss function trades off these two tasks to give conditional uncertainty sets.

  • 11:45 AM - 12:10 PM

    Data-Driven EMS Network Design Models: A Distributionally Robust Stochastic Dominance Approach

    • Chun Peng, presenter, GERAD & HEC Montreal
    • Erick Delage, GERAD, HEC Montréal

    In this paper, we study an Emergency Medical Services (EMS) network design problem and propose two novel data-driven optimization models that account for uncertainty about emergency demand with contextual information using a time-dependent Wasserstein ambiguity set. The first model considers both a distributionally robust second-order stochastic dominance (SSD) constraint on the coverage of the realized emergency demand and minimizing the expected cost of doing so, while the second one considers an alterantive data-driven formulation from a SSD feasibility viewpoint under a robustness optimization framework. We compare the two models through an out-of-sample analysis using both synthetic and real-life data.