Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012


HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire

MB8 Programmation linéaire / Linear Programming

7 mai 2012 10h30 – 12h10

Salle: Transat

Présidée par Jacques Desrosiers

4 présentations

  • 10h30 - 10h55

    Stabilized Dynamic Constraint Aggregation for Solving Set Partitioning Problems

    • Jacques Desrosiers, prés., 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.

  • 10h55 - 11h20

    Improved Column Generation for Degenerate Master Problems

    • Jean-Bertrand Gauthier, prés., 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.

  • 11h20 - 11h45

    Parallel Integral Simplex Using Decomposition

    • Younes Skandrani, prés., É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.

  • 11h45 - 12h10

    Stabilization of a Complementary Problem

    • Hocine Bouarab, prés., É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.