4 Presentations

• 
  10:30 AM - 10:55 AM

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

  • Bo Lin, presenter, University of Toronto
  • Timothy Chan, University of Toronto
  • Shoshanna Saxe, University of Toronto

  We present a novel 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 explicitly 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, which can be used as inputs to the embedded machine learning model. Using synthetic instances of a cycling network design problem, we compare the computational performance of our approach versus baseline methods. Our approach provides more accurate predictions for follower objective values, and more importantly, 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.
• 
  10:55 AM - 11:20 AM

  Towards feasible ML optimization proxies

  • Mathieu Tanneau, presenter, Georgia Institute of Technology
  • Pascal Van Hentenryck, Georgia Institute of Technology

  Optimization proxies are machine learning models that, given an optimization instance data, seek to predict a close-to-optimal solution for that instance. Such models have received a lot of attention in power systems for their potential to speedup optimization algorithms and enable fast ML-based simulations. Two major challenges in training proxies are costly data-generation, and ensuring that predicted solutions satisfy physical and engineering constraints. This talk presents some recent work in addressing these two challenges for unit commitment and optimal power flow problems. Numerical results are reported on industry-size instances.
• 
  11:20 AM - 11:45 AM

  One-shot learning for MIPs with SOS1 constraints

  • Charly Robinson La Rocca, presenter, Université de Montréal
  • Emma Frejinger, DIRO and CIRRELT
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT

  Efficient algorithms and solvers are required to provide optimal or near-optimal solutions quickly, enabling organizations to react promptly to dynamic situations such as supply chain disruptions or changing customer demands. State-of-the-art mixed-integer programming (MIP) solvers are crafted to tackle a wide variety of problems, yet many real-world situations present problem instances that originate from a narrow distribution. This has inspired the creation of tailored approaches that exploit historical data to inform heuristic design. Deep learning (DL) methods are typically used in this context to extract patterns from data, but they require large datasets and comprehensive hyperparameter tuning for optimal performance. This presentation describes a one-shot learning heuristic that leverages solutions discovered within the branch-and-bound tree to construct a model with minimal overhead. We evaluate our method on the locomotive assignment problem (LAP), a recurring real-world problem that is challenging to solve at scale. Experimental results reveal a tenfold acceleration compared to a general-purpose solver (CPLEX) with a relative gap of less than 2%. We also demonstrate that the method is competitive with CPLEX on the majority of MIPLIB instances with SOS1 constraints.

  Keywords: Mixed-integer programming, Machine Learning, Fleet Management Problem, MIPLIB
• 
  11:45 AM - 12:10 PM

  Gaining insight into crew rostering instances through ML-based sequential assignment

  • Philippe Racette, presenter, Polytechnique Montréal
  • Frédéric Quesnel, Université du Québec à Montréal
  • Andrea Lodi, CERC, Polytechnique Montréal, Montréal, Canada and Jacobs Technion-Cornell Institute, Cornell Tech and Technion - IIT, New York, USA
  • Francois Soumis, GERAD et Polytechnique

  Crew scheduling is typically performed in two stages. First, sequences of flights called pairings are built. Then, the pairings are assigned to crew members to provide each person with a schedule. Solving the crew rostering problem (CRP) is one way of doing the latter. However, before solving the CRP, the problem instance considered must be parameterized by accounting for different factors related to pilot requests and to the number of pilots placed on reserve. In order to address this need, we present a new method for the parameterization of CRP instances for pilots by scheduling planners. A machine learning-based sequential assignment procedure (seqAsg) whose arc weights are computed using a policy over pilot-related features is implemented to generate quick solutions. We establish a relationship between the quality of the seqAsg-generated solutions and that of solutions produced by a state-of-the-art solver. We show how this method can be used by scheduling planners to reparameterize CRP instances as needed. We also discuss the potential of the seqAsg procedure to generate solutions of sufficient quality to forgo resolution in an optimization solver, therefore eliminating the need to accelerate the solving process altogether, by analyzing the impact of certain properties of the CRP instance.