HEC Montréal, Canada, May 6 - 8, 2013

2013 Optimization Days

HEC Montréal, Canada, 6 — 8 May 2013

Schedule Authors My Schedule

MA6 Problèmes d'horaires de grandes tailles / Large-Scale Scheduling Problems

May 6, 2013 10:30 AM – 12:10 PM

Location: Mary Husny

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.