4 Presentations

• 
  10:30 AM - 10:55 AM

  Logic-based Benders Decomposition and Hybrid Column Generation for the Network Migration Problem

  • Maryam Daryalal, presenter, University of Toronto
  • Hamed Pouya, University of Toronto

  Migrating legacy telecommunication networks to the latest technology involves planning synchronized technicians. We propose the first exact method for the network migration problem, a logic-based Benders decomposition approach that benefits from a hybrid constraint programming-based column generation in its master problem and a constraint programming model in its subproblem. This integrated solution technique is applicable to any integer programming problem with similar structure, most notably the vehicle routing problem with node synchronization constraints. Comprehensive evaluation of our method over instances based on six real networks demonstrates the computational efficiency of the algorithm in obtaining quality solutions.

• 
  10:55 AM - 11:20 AM

  Solving the doubly open park-and-loop routing problem via column generation

  • Nicolas Cabrera, presenter, HEC Montréal
  • Jorge Mendoza, HEC Montréal
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT

  The doubly open park-and-loop routing problem is a variation of the vehicle routing problem in which routes involve a main tour that is completed using a vehicle and subtours that are carried out on foot after parking the vehicle. Additionally, routes start and end at any customer, and their duration and total walking distance are bounded. We propose a column-oriented approach in which a master problem assigns technicians to paths generated by a pricing subproblem. To efficiently solve this subproblem we extend the well-known pulse algorithm to include problem-specific pruning and acceleration strategies. To illustrate the effectiveness of our method, we present computational experiments on a set of instances with up to 50 customers in which the method finds 24/40 optimal solutions. Moreover, the average optimality GAP is less than 0.01%. We also present results on a related problem called the vehicle routing problem with transportable resources, where the method finds 8/40 new best-known solutions on standard instances.

• 
  11:20 AM - 11:45 AM

  Boosting the Convergence of Column Generation by Graph Neural Networks

  • Behrouz Babaki, presenter, Wise Systems
  • Sanjay Dominik Jena, Université du Québec à Montréal
  • Laurent Charlin, HEC Montréal

  Column generation is a technique to solve linear programs with an exponential number of variables. It has been successfully applied to efficiently solve important applications such as the vehicle routing problem. Unfortunately, in practice, convergence is often slow, adding too many columns. In this work, we frame the problem of selecting which columns to add as one of sequential decision-making. We propose a neural column generation architecture that iteratively selects columns to be added to the problem. The architecture, inspired by stabilization techniques, first predicts the optimal duals. These predictions are then used to obtain the columns to add. We show using VRP instances that in this setting several machine learning models yield good performance on the task and that our proposed architecture learned using imitation learning outperforms a modern stabilization technique.

• 
  11:45 AM - 12:10 PM

  Interpretable multiclass text classification using column generation

  • Krunal Patel, presenter, CERC, Polytechnique Montréal, Montréal, Canada
  • Andrea Lodi, CERC, Polytechnique Montréal, Montréal, Canada and Jacobs Technion-Cornell Institute, Cornell Tech and Technion - IIT, New York, USA
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  In this presentation, we start by discussing a binary classification model for interpretable boolean decision rule generation by Dash et al. 2018 that is solved using column generation. We then talk about how we extended it to a multiclass text classification framework for a prediction problem in the aviation industry, where we needed to classify a set of text messages (NOTAMs) into a specific set of categories (Qcodes). Specifically, we present the techniques we used to tackle the issues related to one-vs-rest classification such as multiple outputs, class imbalances etc. We also talk about using a CP-SAT solver as a heuristic to speed up the training process. Finally, we conclude the presentation with the comparison of our results with the results of some standard machine learning algorithms, and the discussion of future ideas we want to implement for this task.