5 Presentations

• 
  10:30 AM - 10:55 AM

  Personalized Crew Pairing and Crew Assignment Problem

  • Atoosa Kasirzadeh, presenter, Polytechnique Montréal
  • Mohammed Saddoune, Polytechnique Montréal
  • Francois Soumis, GERAD et Polytechnique

  We present a set-covering formulation and a solution approach based on column generation for the personalized airline cabin crew scheduling problem in which the objective is optimizing the costs and the crew’s preferences. The computational results are provided based on a major US carrier data set.

• 
  10:55 AM - 11:20 AM

  Taking Advantage of Degeneracy in Mathematical Programming

  • Francois Soumis, presenter, GERAD et Polytechnique
  • Jacques Desrosiers, GERAD, HEC Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal

  I will introduce the basics concepts used by the presentations in the two following sessions. The Improved Primal Simplex and the integral simplex use a reduced master problem obtained by removing degenerated constraints and degenerated variables and a subproblem identifying non degenerated improving directions obtained by combining many degenerated variables

• 
  11:20 AM - 11:45 AM

  A New Formulation of the Integral Simplex Using Decomposition with Cutting-Planes Algorithm

  • Samuel Rosat, presenter, GERAD
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal
  • Francois Soumis, GERAD et Polytechnique

  We present a new formulation of the integral simplex using decomposition for the set-partitioning problem. This formulation is based on a geometrical approach of the decomposition, yielding an innovative cutting-plane algorithm. Numerical results will be shown for aircrew and bus-drivers scheduling.

• 
  11:45 AM - 12:10 PM

  Integral Simplex and Additional Constraints

  • Matthieu Delorme, presenter, GERAD
  • Francois Soumis, GERAD et Polytechnique

  We adapt the integral simplex algorithm of Zaghrouti and al to solve problems where besides the set partitioning constraints there are others constraints which do not have any particular structure. We use Lagrangian relaxation techniques to treat those constraints and present our results along with those of CPLEX.

• 
  12:10 PM - 12:35 PM

  Integral Simplex Using Decomposition for the Set Partitioning Problem

  • Abdelouahab Zaghrouti, presenter, GERAD - Polytechnique Montréal
  • Francois Soumis, GERAD et Polytechnique
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  The decomposition algorithm efficiently deals with the degenerate nature of Set Partitioning Problems. It's a constructive method that uses sub-problems to find compatible variables that improve an integer solution by only using normal simplex pivots. Optimal solutions are often obtained, for large-scale problems (up to 500000 variables), without any branching.