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

2011 Optimization Days

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

Schedule Authors My Schedule

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

May 2, 2011 03:30 PM – 05:10 PM

Location: Hélène-Desmarais

Chaired by Issmail El Hallaoui

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.