Journées de l'optimisation 2017

HEC Montréal, 8-10 mai 2017

1er Atelier Canadien sur l'optimisation des soins de santé (CHOW)

HEC Montréal, 10-11 mai 2017


HEC Montréal, 8 — 11 mai 2017

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

MD3 Optimisation combinatoire 1 / Combinatorial Optimization 1

8 mai 2017 15h30 – 17h10

Salle: Marie-Husny

Présidée par Ilyas Himmich

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h30 - 15h55

    Optimal design of data centers.

    • Eglantine Camby, Présentateur, Université Libre de Bruxelles
    • Gilles Caporossi, GERAD, HEC Montréal

    We present our current research on data centers design. Our goal is to find a network on 64 vertices with a small average distance and a bounded maximum degree, and some robustness properties. First, we establish some mathematical properties and then we find some interesting candidates by optimization.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h55 - 16h20

    Integer column generation using decomposition

    • Adil TAHIR, Présentateur, Gerad & Polymtl
    • Issmail El Hallaoui, GERAD, Polytechnique Montréal
    • Guy Desaulniers, GERAD and Polytechnique Montreal

    Integer column generation using decomposition (ICG) is a new primal method that aims to solve the popular set partitioning problem. This method finds a sequence of integer solutions, with non-increasing cost, leading to optimal or near-optimal solutions in reasonable time. Potential columns favoring integrality are generated using a suited dual vector. Some acceleration strategies improving the effectiveness of ICG will be discussed. Computational experiments on some large-scale bus drivers scheduling and aircrew pairing problems will be presented. The results obtained demonstrate the efficiency of ICG.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h20 - 16h45

    ANNULÉ / Pick-up and delivery with complex loading constraints: application to the gasoline distribution

    • Abderrahman BANI, Présentateur, GERAD & Polymtl
    • Issmail El Hallaoui, GERAD, Polytechnique Montréal
    • Ayoub Insa Correa, Université de Thies, Sénégal

    In this work, we present a Branch & Price method to solve a real-world pick-up and delivery problem arising in the sector of the distribution of gasoline. The underlying network consists of four distinct depots, a group of private carriers with heterogeneous tank trucks and five types of gasoline to replenish three groups of customers on a weekly basis. Complex loading and routing rules are handled in the sub-problem, a very difficult shortest path problem with resource constraints. Acceleration strategies will be discussed. Numerical results on real data show the high potential of the proposed approach.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h45 - 17h10

    Primal Neighbourhood Search Algorithm for solving the Shortest Path Problem with Resource Constraints

    • Ilyas Himmich, Présentateur, Polytechnique Montréal
    • Issmail El Hallaoui, GERAD, Polytechnique Montréal
    • Hatem Ben Amor, KRONOS
    • François Soumis, Polytechnique Montréal

    We propose a new exact primal method for solving the shortest path problem with resource constraints. Our algorithm performs a search in the neighbourhood of a set of source-task paths. We first define the notion
    of adjacency in the context of the SPPRC. Then, we develop some polyhedral properties that are useful in the definition and exploration of the neighbourhood. Computational results on the VCSP show that the proposed solution approach is more efficient than classical dynamic programming algorithm.