4 Presentations

• 
  01:30 PM - 01:55 PM

  Integral simplex for the partitioning problem

  • Francois Soumis, presenter, GERAD et Polytechnique
  • Alpha Saliou Barry, Gerad
  • Frédéric Quesnel, Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  For the set partitioning problem, the existence of a sequence of integer solutions with non-increasing costs produced by simplex pivots, permitting to reach optimality was proved by Balas, Padberg 1972. Finding the following term in the sequence can be very time-consuming due to degeneracy. When there is no entering variable that leads to a better integer solution, we use a linear programming sub-problem to find a group of variables to enter the basis to obtain an improved solution which is integer most of the time. When this solution is not integer, we solve a small integer programming problem to obtain a better integer solution.
  We first, present results for large-scale problems (with up to 500 000 variables) for which optimal integer solutions are obtained, most of the time, without any branching. We also, present the integration of this new approach with column generation and parallelism to solve large-scale bus driver and airline pilot problems. Problems with many thousand tasks are solved 5 to 10 faster than with branch and price based on CPLEX.

• 
  01:55 PM - 02:20 PM

  Integral simplex for the generalized set partitioning problem

  • Alpha Saliou Barry, presenter, Gerad
  • Francois Soumis, GERAD et Polytechnique
  • Frédéric Quesnel, Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  The set partitioning problem can be generalized. One generalization is to consider that certain tasks must be covered several times. So it's no longer a partition that's sought, but a set of parts that verify the right number of coverages.

  Unlike the set partitioning problem, the graph of integer solutions is no longer connected when the possible arcs are simplex pivots. However, to restore the connectedness of the graph, it is possible to add artificial variables locally, which allows new pivots to be made while preserving the integrity of the solution.

  We give priority to pivots that keep the solution integer. When this is no longer possible, we solve a linear program to obtain a non-degenerate sequence of simplex pivots to perform to improve the solution. When this improved solution is still not integer, in some cases the pivot sequence allows to add an artificial column associated with an integer artificial point. The linear program is solved again from this point to find the remaining pivots to be performed to obtain a better integer solution. If integrity is still not reached, a branching is performed.

  We present results for large pairing problems (around 2,000 constraints and 300,000 variables) and show that the method is around 2 to 5 times faster than traditional methods (CPLEX) and that in many cases, the addition of the artificial variable effectively allows moves on integer points not directly accessible by pivot.

• 
  02:20 PM - 02:45 PM

  Fast algorithm for the crew rostering problem combining machine learning and column generation

  • Philippe Racette, presenter, Polytechnique Montréal
  • Andrea Lodi, Polytechnique Montreal
  • Francois Soumis, GERAD et Polytechnique

  The crew rostering problem (CRP) is a complex crew scheduling task where pairings, or sequences of flights starting and ending at the same airport, are assigned to pilots. These assignments form a collection of schedules (called roster) spanning one month. The CRP typically seeks to optimize some criterion such as cost or crew satisfaction.
  In this presentation, we describe a new line of research concerning the CRP. We address the possibility of generating very fast solutions to the problem with the help of machine learning (ML) techniques. Using a sequential assignment procedure whose arc weights are computed with ML weights, we generate solutions to infer the quality of a CRP instance's configuration. We also use a partial reoptimization technique with windowing to improve the solutions. The rosters obtained in this way are high-quality and produced in 5% to 20% of the time normally taken by a state-of-the-art solver. In each case, the ML weights are learned with reinforcement learning and an evolutionary algorithm (CMA-ES).
  We conclude with a discussion of the methodological framework introduced and outline future efforts, such as extensions of our method to other crew scheduling tasks, and its relationship with different ML models, such as GNNs.

• 
  02:45 PM - 03:10 PM

  New complementary problem formulation for the improved primal simplex

  • Youssouf Emine, presenter, GERAD
  • Francois Soumis, GERAD et Polytechnique
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  The primal simplex algorithm is still one of the most used algorithms by the operations research community. It moves from basis to adjacent one until optimality. The number of bases can bef very huge, even exponential, due to degeneracy or when we have to go through all of the extreme points very close to each other. The improved primal simplex algorithm (IPS) is efficient against degeneracy but when there is no degeneracy, it behaves exactly as a primal simplex and consequently, it may suffer from the same limitations.

  We present a new formulation of the complementary problem, i.e., the auxiliary subproblem used by the improved primal simplex to find descent directions, that guarantees a significant improvement of the objective value at each iteration until we reach an $\epsilon-$approximation of the optimal value. We prove that the number of needed directions is polynomial.