4 présentations

• 
  10h30 - 10h55

  Multi-Class Advance Patient Scheduling: A Data-Driven Robust Approach

  • Hamid Arzani, prés., University of Toronto

  In this paper, we study a multi-class advance patient scheduling problem where patients of different classes have different service times and incur different waiting costs to the system. It is known in the literature that dynamic advance patient scheduling is a challenging problem due to the high variability in the daily arrivals and high dimensionality of the problem. To overcome these challenges, we focus on analyzing the regret of any online scheduling policy relative to an offline controller. This helps us to develop a novel dynamic optimization framework where the problem can be approximately decomposed into multiple single-stage stochastic problems. Each single-stage problem determines how patients who arrived in that period should be scheduled over a booking horizon. We then extend the framework to a data-driven setting where the true distribution of demand in each period is unknown. We propose an algorithm to solve the robust model and examine its performance by leveraging the MRI data from hospitals in Ontario. We observe that the proposed approach schedules patients such that the system is efficiently protected against the high variability in the daily and performs well compared to an offline policy that is endowed with the full knowledge of demand.
• 
  10h55 - 11h20

  Capacity Planning in Stable Matching: An Application to School Choice

  • Federico Bobbio, prés., Université de Montréal

  A successful application of Matching Theory is school choice (SC), i.e., the admission process of students to schools. We introduce the problem of jointly allocating extra spots to schools and finding the best stable allocation for the students in the expanded market. We analyze theoretically the problem, focusing on the trade-off behind the multiplicity of student-optimal assignments, and discussing the problem’s complexity. We generalize existent mixed-integer linear programming (MIP) formulations and we propose a novel one. We show that its stability constraints can be separated in linear time, leading to an effective cutting-plane method. We evaluate the performance of our approaches in a detailed computational study, and we find that our cutting-plane method outperforms MIP solving the natural generalizations of existing formulations. Moreover, we propose two heuristics that are effective for large instances. Finally, we use the Chilean SC system data to demonstrate the impact of capacity planning under stability constraints. Our results show that each additional school seat can benefit multiple students. Additionally, our methodology can prioritize the assignment of previously unassigned students or improve the assignment of several students through improvement chains. These insights empower the decision-maker in tuning the matching algorithm to provide a fair application-oriented solution.
• 
  11h20 - 11h45

  Learning Consumer Preferences from Bundle Sales Data

  • Setareh Farajollahzadeh, prés.,

  Product bundling is a common selling mechanism used in online retailing. To set profitable bundle prices, the seller needs to learn consumer preferences from the transaction data. When customers purchase bundles or multiple products, classical methods such as discrete choice models cannot be used to estimate customers’ valuations. In this paper, we propose an approach to learn the distribution of consumers’ valuations toward the products using bundle sales data. The approach reduces it to an estimation problem where the samples are censored by polyhedral regions. Using the EM algorithm and Monte Carlo simulation, our approach can recover the distribution of consumers’ valuations. The framework allows for unobserved no-purchases and clustered market segments. We provide theoretical results on the identifiability of the probability model and the convergence of the EM algorithm. The performance of the approach is also demonstrated numerically.
• 
  11h45 - 12h10

  A Machine Learning Approach to Solving Large Bilevel and Stochastic Programs: Application to Cycling Network Design

  • Bo Lin, prés., University of Toronto

  We present a machine learning-based approach to solving bilevel programs that involve a large number of independent followers, which as a special case include two-stage stochastic programming. We propose an optimization model that considers a sampled subset of followers and exploits a machine learning model to estimate the objective values of unsampled followers. Unlike existing approaches, we embed machine learning model training into the optimization problem, which allows us to employ general follower features that can not be represented using leader decisions. We prove bounds on the optimality gap of the generated leader decision as measured by the original objective function that considers the full follower set. We then develop follower sampling algorithms to tighten the bounds and a representation learning approach to learn follower features. Using synthetic instances of a cycling network design problem, we compare the performance of our approach versus baselines. Our approach provides more accurate predictions for follower objectives and generates leader decisions of higher quality. Finally, we perform a real-world case study on cycling infrastructure planning, where we apply our approach to solve a network design problem with over one million followers. Our approach presents favorable performance compared to the current cycling network expansion practices.