2022 Optimization Days

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

Schedule Authors My Schedule

TB9 - Integrated Machine Learning and Optimization for Decision Making under Uncertainty

May 17, 2022 03:30 PM – 05:10 PM

Location: Groupe Cholette (yellow)

Chaired by Erick Delage

4 Presentations

  • 03:30 PM - 03:55 PM

    Distributionally Robust Conditional Optimization via Optimal Transport

    • Viet Anh Nguyen, Stanford University
    • Fan Zhang, Stanford University
    • José Blanchet, Stanford University
    • Erick Delage, presenter, GERAD, HEC Montréal
    • Yinyu Ye, Stanford University

    Conditional estimation and decision making given specific covariate values is becoming ubiquitously useful with applications in engineering, social and natural sciences. Existing data-driven conditional optimization models can be very sensitive to adversarial noise and may perform poorly under a low sample size. To alleviate these issues, we propose a new class data-driven model that minimizes the worst-case conditional expected loss over all adversarial distributions in a Wasserstein ambiguity set. We show that despite being generally intractable, the optimal solution can be efficiently found via convex optimization under broadly applicable descriptive and prescriptive settings, including local non-parametric conditional estimation and risk-averse portfolio selection. Experiments with the MNIST dataset and US stock market data show the competitive performance of this new class of data-driven optimization model.

  • 03:55 PM - 04:20 PM

    Scalable stochastic dual dynamic programming (SDDP) approaches for supply chain applications

    • Simon Thevenin, IMT Atlantique - LS2N
    • Lingxiao Wu, HEC Montréal
    • Yossiri Adulyasak, presenter, HEC Montréal
    • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT

    Despite significant interest in stochastic programming and its applications, implementations of multi-stage stochastic programming models remain highly challenging from the computational perspective. Improving computational scalability in multi-stage stochastic programming models, in particular those based on scenario-tree-based representations, can help enhance applicability and practicability in various research domains and applications. In this talk, we present enhancements and scalable implementations of the stochastic dual dynamic programming (SDDP) technique in two supply chain applications under demand uncertainty, namely, multi-echelon lot-sizing and freight procurement in transportation-inventory systems, which can be leveraged to solve instances with more than 10^10 scenarios. Through numerical experiments, we also present insights how the multi-stage stochastic optimization framework can help improve the solution quality in a multi-stage decision process under uncertainty and enable significant cost savings. We further discuss how machine learning techniques can help enhance the solution process of SDDP.

  • 04:20 PM - 04:45 PM

    Fast Heuristic L-Shaped Method Through Machine Learning

    • Emma Frejinger, presenter, DIRO and CIRRELT
    • Eric Larsen, Université de Montréal
    • Andrea Lodi, Polytechnique Montreal

    We propose a methodology at the nexus of operations research and machine learning (ML) leveraging generic approximators available from ML to accelerate the solution of mixed-integer linear two-stage stochastic programming. We aim at solving problems where the second stage is highly demanding. Our core idea is to gain large reductions in online solution time while incurring small reductions in first-stage solution accuracy by substituting the exact second-stage solutions with fast, yet accurate supervised ML predictions. This upfront investment in ML would be justified when similar problems are solved repeatedly over time, for example, in operational transport planning related to fleet management, routing and container yard management.

    Our experimental results focus on the problem class seminally addressed with the integer and continuous L-shaped cuts. Our extensive empirical analysis is grounded in standardized families of problems derived from stochastic server location (SSLP) and multi knapsack (SMKP) problems available in the existing literature. The proposed method can solve the hardest instances of SSLP in less than 9% of the time it takes the state-of-the-art exact method, and in the case of SMKP the same figure is 20%. Average optimality gaps are in most cases less than 0.1%.

  • 04:45 PM - 05:10 PM

    Introducing IVADO’s Strategic Research Program in Integrated ML and OR for Decision Making under Uncertainty

    • Erick Delage, presenter, GERAD, HEC Montréal
    • Yossiri Adulyasak, HEC Montréal
    • Emma Frejinger, DIRO and CIRRELT

    Nearly all decision problems involve some form of uncertainty. This is especially true in supply chains where, e.g., demand, cost, capacity, and travel time variability considerably complicate the planning of procurement, production, distribution, and service activities. Due to constantly evolving environments and the high frequency of data acquisition, classical decision making that is based on training and validating models, and finally optimizing decisions does not suffice anymore. This research program aims at developing integrated machine learning and optimization methods for making the most effective and adaptive use of data in decision-making. In this session, we will introduce the program’s objectives and discuss with the participants possible opportunities for collaborations under the available funding. We will also present a call for postdoctoral project proposals and answer any related questions. We warmly welcome any interested researchers, students and practitioners to this interactive session!