Journées de l'optimisation 2022
HEC Montréal, Québec, Canada, 16 — 18 mai 2022
MA7 - Column generation
16 mai 2022 10h30 – 12h10
Salle: Quebecor (jaune)
Présidée par Krunal Patel
10h30 - 10h55
Logic-based Benders Decomposition and Hybrid Column Generation for the Network Migration Problem
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.
10h55 - 11h20
Solving the doubly open park-and-loop routing problem via column generation
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.
11h20 - 11h45
Boosting the Convergence of Column Generation by Graph Neural Networks
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.
11h45 - 12h10
Interpretable multiclass text classification using column generation
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.