4 Presentations

• 
  03:30 PM - 03:55 PM

  A Stabilized Dynamic Constraint Aggregation Method in Column Generation

  • Pascal Benchimol, presenter, École Polytechnique de Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Jacques Desrosiers, GERAD, HEC Montréal

  Stabilization of dual variables and dynamic constraint aggregation are two examples of approaches used to damp the effects of degeneracy. In this talk, we present how two combine the strength of both for set-partitioning problems. We report computational results for the multi-depot vehicle scheduling problem.

• 
  03:55 PM - 04:20 PM

  Integral Simplex Using Decomposition

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

  Since the early '70s, several authors proposed, without much success, adaptations of the simplex algorithm to reach an optimal integer solution to the set-partitioning problem, with a sequence of basic integer solutions. This paper presents an algorithm that iteratively finds improving integer solutions by solving small subproblems. Theoritical and experimental results are presented.

• 
  04:20 PM - 04:45 PM

  Positive Edge: A Pricing Criterion for the Identification of Non-Degenerate Simplex Pivots

  • Mehdi Towhidi, presenter, GERAD
  • Vincent Raymond, Omega Optimisation
  • Abdelmoutalib Metrane, École Nationale des Sciences Appliquées de Khouribga
  • Francois Soumis, GERAD et Polytechnique
  • Jacques Desrosiers, GERAD, HEC Montréal

  The positive edge is a new pricing rule for the primal simplex: it identifies, with a probability error less than 2^{−62}, variables allowing for non-degenerate pivots. Its computational complexity is the same as for the reduced cost. The integration of the positive edge rule within COIN-OR has been tested on 32 instances from Mittelmann's Benchmark.

• 
  04:45 PM - 05:10 PM

  Dynamic Constraint Aggregation for Crew Pairing

  • Hatem Ben Amor, presenter, AD OPT
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  Dynamic constraint aggregation (DCA) is known to improve routing problems solution based on column generation when a quite good initial task partition is known. We apply DCA on crew pairing problem where initial task partition is based on aircraft routes. Computational experimentation shows that even if initial task partition is not close to the final solution task partition, column generation performance could be improved substantially.