Journées de l'optimisation 2018

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

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

WB10 Exact methods for combinatorial optimization

9 mai 2018 15h30 – 17h10

Salle: Sony (48)

Présidée par Claudio Contardo

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h30 - 15h55

    Benders decomposition for tree-of-hubs location problems

    • Furkan Enderer, prés., Université Concordia
    • Claudio Contardo, GERAD - ESG UQÀM
    • Bernard Gendron, Université de Montréal, CIRRELT

    In this talk, we study the Tree-of-Hub Location Problems. First, we present relevant literature review and motivation for the problem. We present a mathematical formulation and a Benders Decomposition to solve the problem. In the second part of the talk we study the hop-constrained THLP. We reformulate the problem and present a Benders decomposition to solve the hop-constrained version of the problem. We discuss optimality-feasibility cuts and their relation to other valid inequalities for both variations of THLP. We present experimental results assessing the performance of the proposed solution methodologies. Finally, we draw conclusions and talk about possible future research.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h55 - 16h20

    Binary search for partitioning graphs using k-connected subgraphs

    • Claudio Contardo, prés., GERAD - ESG UQÀM

    We study the problem of partitioning a weighted graph G = (V, E, w) into p subgraphs, each of which must be k-connected. The weight of a cluster is the minimum weight of a k-connected subgraph, and the objective is to find the partition that minimizes the maximum such weight. We solve this problem using a binary search algorithm, for which the subproblems are solved by means of branch-and-price. Preliminary results will be provided

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h20 - 16h45

    A new branch-price-and-cut algorithm for the pickup and delivery problem with time windows

    • Luciano Costa, prés., Polytechnique Montréal / GERAD
    • Claudio Contardo, GERAD - ESG UQÀM
    • Guy Desaulniers, GERAD and Polytechnique Montreal

    The pickup and delivery problem with time windows aims at finding routes to satisfy a set of requests. We investigate the impact of disregarding precedence and paring relations within the routes to obtain less restrictive dominance rules in column generation algorithms. Multi-commodity paths are then generated to reinforce route feasibility.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h45 - 17h10

    Solving the optimum communication spanning tree problem

    • Ivan Contreras, prés., Concordia University
    • Carlos Zetina, CIRRELT
    • Elena Fernandez, Universitat Politècnica de Catalunya

    This talk presents an exact algorithm based on Benders decomposition to solve the optimum communication spanning tree problem. It integrates a strong reformulation, combinatorial bounds, in-tree heuristics, fast separation algorithms, and a tailored branching rule. Computational experiments show solution time savings of up to two orders of magnitude compared to state-of-the-art exact algorithms.