HEC Montréal, Canada, 2 - 4 mai 2011

Journées de l'optimisation 2011

HEC Montréal, Canada, 2 — 4 mai 2011

Horaire Auteurs Mon horaire

MB7 Réduction dynamique de contraintes / Dynamic Reduction of Constraints

2 mai 2011 15h30 – 17h10

Salle: Hélène-Desmarais

Présidée par Issmail El Hallaoui

4 présentations

  • 15h30 - 15h55

    A Stabilized Dynamic Constraint Aggregation Method in Column Generation

    • Pascal Benchimol, prés., É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.

  • 15h55 - 16h20

    Integral Simplex Using Decomposition

    • Francois Soumis, prés., 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.

  • 16h20 - 16h45

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

    • Mehdi Towhidi, prés., 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.

  • 16h45 - 17h10

    Dynamic Constraint Aggregation for Crew Pairing

    • Hatem Ben Amor, prés., 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.