4 Presentations

• 
  10:30 AM - 10:55 AM

  Machine-learning-based arc selection for constrained shortest path problems in column generation

  • Mouad Morabit, presenter, Polytechnique Montréal
  • Andrea Lodi, Polytechnique Montreal
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  Column generation is an iterative method used to solve a variety of optimization problems. It decomposes the problem into two parts: a master problem, and one or more pricing problems (PP). The total computing time taken by the method is divided between these two parts. In routing or scheduling applications, the problems are mostly defined on a network, and the PP is usually an NP-hard shortest path problem with resource constraints. In this work, we propose a new heuristic pricing algorithm based on machine learning. By taking advantage of the data collected during previous executions, the objective is to reduce the size of the network and accelerate the PP, keeping only the arcs that have a high chance to be part of the linear relaxation solution. The method has been applied to two specific problems: the vehicle and crew scheduling problem in public transit and the vehicle routing problem with time windows. Reductions in computational time of up to 40% can be obtained.

• 
  10:55 AM - 11:20 AM

  Learning to Enumerate Shifts for Large-Scale Flexible Personnel Scheduling Problems

  • Farin Rastgar Amini, presenter, Polytechnique Montreal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Claudio Contardo, ESG UQÀM / GERAD
  • Maxime Gasse, Polytechnique Montréal

  Personnel scheduling consists in determining employee work schedules (sequences of work shifts and days off) to cover the demands of multiple jobs over a planning horizon. We consider finding a near-optimal set of personnel schedules via the solution of a generalized set-covering model with side constraints in a flexible context where a large number of potential shifts can be considered as in the retail industry. Commercial solvers applied to this model often require very long computational times for practical problem sizes, and as such rely on enumeration heuristics for filtering non-promising shifts/schedules and, thus, reducing problem size. We propose a deep learning-based heuristic to drive the enumeration of promising potential shifts based on the information collected from previously solved instances. Our model predicts a subset of time points at which promising shifts are more likely to either start or end, thus filtering out those that do not start nor end at those time points. Our computational results on realistic instances show that personnel scheduling problems can be solved considerably faster with an acceptable optimality gap if shifts are enumerated according to the time points predicted by our model.

• 
  11:20 AM - 11:45 AM

  The Parameter Configuration Problem for MILP Solvers

  • El Mehdi Er Raqabi, presenter, GERAD, Polytechnique Montréal
  • Ilyas Himmich, Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal
  • Francois Soumis, GERAD et Polytechnique

  We address the parameter configuration problem. We introduce a multi-phase tuner based on the iterated local search metaheuristic to find good, if not optimal, configuration(s) for efficiently solving large-scale optimization problems by MILP solvers. The tuner tunes on a small pool of parameters, which is dynamically enhanced with new promising parameters. It benefits from the accumulated information to forbid less promising parameter combinations using statistical learning. Numerical results on instances from the MIPLIB library and a real large-scale optimization problem are shown.

• 
  11:45 AM - 12:10 PM

  Apprentissage automatique servant à construire les partitions initiales pour l’agrégation dynamique de contraintes afin de résoudre des problèmes d’horaire de conducteur d’autobus.

  • Jonathan Brasseur, presenter, GERAD

  Le problème d’horaire de conducteurs d’autobus (DSP) constitue à déterminer les horaires de chauffeurs de bus sur un réseau de transport en commun. Ceci doit être fait de manière à minimiser le nombre de conducteurs nécessaires. Les trajets de bus sont déterminés au préalable suite à la résolution d’un problème de construction des itinéraires d’autobus (VSP). Le DSP est généralement résolu à l’aide d’algorithmes de génération de colonne. Celui-ci utilise l’agrégation dynamique de contrainte afin d’accélérer sa résolution. Nous utilisons le paradigme “Machine Learning → Mathematical Programming” où à partir de solutions de problème similaires, nous produisons des prédictions sur des parties de la solution d’un nouveau problème. Dans notre cas, nous créons la partition d’origine du DSP à l’aide d’algorithmes d’apprentissage automatique. Nous montrons que cette nouvelle méthode permet de résoudre les problèmes plus rapidement qu’avec les partitions créées à l’aide de la solution construite à partir du VSP résolu au préalable. La nouvelle partition est créée en prédisant à l’aide de l’apprentissage automatique où des échanges de conducteur devraient avoir lieu sur le trajet des bus.