4 Presentations

• 
  10:30 AM - 10:55 AM

  Stabilized Dynamic Constraint Aggregation for Solving Set Partitioning Problems

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

  In column generation,dynamic constraint aggregation and dual variable stabilization reduce the negative impact of degeneracy. The stabilized dynamic constraint aggregation combines these methods for solving set partitioning problems. Computational results indicate a reduction of the average CPU time of the master problem by a factor of up to 7.

• 
  10:55 AM - 11:20 AM

  Improved Column Generation for Degenerate Master Problems

  • Jean-Bertrand Gauthier, presenter, GERAD - HEC Montréal
  • Jacques Desrosiers, GERAD, HEC Montréal
  • Marco E. Lübbecke, RWTH Aachen University

  Column generation suffers from tailing-off effect. The Improved Column Generation takes advantage of degeneracy and operates with a row-reduced master problem, the size of it being only the number of positive variables. The generation of a convex combination of variables allows for a strict decrease of the objective function.

• 
  11:20 AM - 11:45 AM

  Parallel Integral Simplex Using Decomposition

  • Younes Skandrani, presenter, École Polytechnique de Montréal
  • Abdelouahab Zaghrouti, GERAD - Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal
  • Pierre Hansen, HEC Montréal

  This work aims at solving to optimality huge set partitioning problems by the parallel integral simplex using decomposition algorithm. We decompose the problem into sub-problems by fast, self-adjusted and non-problem-dependent procedure in order to solve them in parallel. The solutions of sub-problems are concatenated at each iteration in order to improve the current solution.

• 
  11:45 AM - 12:10 PM

  Stabilization of a Complementary Problem

  • Hocine Bouarab, presenter, École Polytechnique de Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal

  We present an algorithm for stabilizing a highly degenerate linear program
  (LP) solved by column generation. The (LP) optimizes the objective
  function over the null space of a matrix. It is particularly used in the Improved
  Primal Simplex Algorithm as a complementary problem to find feasible
  descent directions. We report computational results obtained for the multidepot
  vehicle scheduling problem.