Journées de l'optimisation 2018

HEC Montréal, Québec, Canada, 7 — 9 mai 2018

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

WA8 Primal and dual methods for integer programming

9 mai 2018 10h30 – 12h10

Salle: Metro inc. (72)

Présidée par Issmail El Hallaoui

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10h30 - 10h55

    Primal integer optimization: A new paradigm

    • Issmail El Hallaoui, prés., GERAD, Polytechnique Montréal

    After some very interesting progress in solving the set partitioning problems (clustering problems for example), we introduce in this presentation a new primal paradigm, called Primal Integer Optimization (PIO), for the exact solution of general ILP, thus opening up a huge field of applications. These primal methods make it possible to go from an integer solution to a better one until the optimality is proven. To do this, they use a new method of decomposition that benefits, rather than suffer, from the degeneracy inherent in these problems. This translates in practice by two great advantages: i) this paradigm makes it possible to generate quite quickly several high-quality solutions, contrary to the "dual" methods of the Branch & Cut type. The other major advantage of this paradigm is its great flexibility: we can easily integrate the metaheuristics, often used in practice, without sacrificing the exactness (optimality), which is the major drawback of the latter.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10h55 - 11h20

    A multidirectional dynamic programming algorithm for the shortest path problem with resource constraints

    • Ilyas Himmich, prés., GERAD
    • Issmail El Hallaoui, GERAD, Polytechnique Montréal
    • François Soumis, Polytechnique Montréal

    The shortest path problem with resource constraints finds the least cost path between two nodes in a network while respecting constraints on resource consumption. The problem is mainly used as a subproblem inside column generation for crew scheduling and vehicle routing problems. The standard approach for the subproblems is based on dynamic programming. This class of methods is generally effective in practice when there are only a few resources, but it seems to be time-consuming for huge instances with many resources. To handle this problem, we propose a new exact primal algorithm called the multidirectional dynamic programming algorithm (MDDPA). The proposed approach splits the state space into small disjoint subspaces. These subspaces are sequentially explored in several iterations, where each iteration builds on the previous ones, to reduce the dimension of the subspaces to explore and to quickly generate better paths. Computational experiments on vehicle and crew scheduling instances show the excellent performance of our approach compared to the standard dynamic programming method. In particular, MDDPA is able to generate feasible paths with up to 90% of the optimal cost in less than 10% of the time required by standard dynamic programming. This feature is useful in column generation and may greatly reduce the computational effort, because we can stop the MDDPA solution process once columns with sufficiently negative reduced costs are obtained.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11h20 - 11h45

    The shortest path problem with congestion and waiting times

    • Jeremy Omer, prés., Univ Rennes, INSA Rennes, CNRS, IRMAR - UMR 6625, F-35000 Rennes, France
    • Michael Poss, LIRMM-CNRS

    We focus on a shortest path problem in a congested network where the driver can wait at vertices to avoid wasting time in traffic. The objective is to minimize the driving time. We study the time complexity of the problem. Then, we describe two approaches by integer programming and dynamic programming.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11h45 - 12h10

    A new Lagrangian relaxation for multicommodity capacitated network design problem

    • Mohammad Rahim Akhavan Kazemzadeh, prés., Université de Montréal
    • Teodor Gabriel Crainic, Université du Québec à Montréal
    • Bernard Gendron, Université de Montréal, CIRRELT

    The usual Lagrangian relaxations for multicommodity capacitated network design are the so-called shortest path and knapsack relaxations, which are obtained, respectively, by relaxing linking constraints and flow conservation equations. We present a new reformulation and Lagrangian relaxation for the problem. We show that the Lagrangian dual bound improves upon the so-called strong LP bound (known to be equal to the Lagrangian dual bounds of the shortest path and knapsack relaxations).