Journées de l'optimisation 2016

HEC Montréal, Québec, Canada, 2 — 4 mai 2016

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TA3 Méthodes de décomposition en programmation en nombre entiers / Decomposition Methods for Integer Programming

3 mai 2016 10h30 – 12h10

Salle: EY

Présidée par Frédéric Quesnel

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10h30 - 10h55

    Selective pricing in branch-and-price algorithms for vehicle routing problems

    • Diego Pecin, prés., GERAD, Polytechnique Montréal
    • Claudio Contardo, GERAD - ESG UQÀM
    • Guy Desaulniers, GERAD - Polytechnique Montréal

    When solving VRPs by column generation, usually the set of feasible routes is enlarged with infeasible cyclic routes. Nevertheless, a lower bound is reached when no feasible route has negative reduced cost regardless of the cyclic route reduced costs. We explore this knowledge to improve the labeling algorithm used for pricing.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10h55 - 11h20

    I2SUD: An improved integral simplex using decomposition algorithm

    • Omar Foutlane, prés., Polytechnique Montréal

    We propose I2SUD, an improved version of the Integral Simplex Using Decomposition algorithm (ISUD). We develop dynamic self-adjusted decompositions to find likely orthogonal descent directions at each iteration. We solve related subproblems in parallel to get an improved integer solution until optimality. We also present some strategies to speed-up I2SUD. Keywords: Integral Simplex Using Decomposition algorithm, dynamic self-adjusted decomposition, parallel computing, orthogonal descent directions.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11h20 - 11h45

    An improved model for the integral simplex using decomposition algorithm

    • Abdelouahab Zaghrouti, prés., GERAD - Polytechnique Montréal
    • François Soumis, Polytechnique Montréal
    • Issmail El Hallaoui, GERAD, Polytechnique Montréal

    We introduce a new model that improves both quality and performance of the ISUD algorithm. The new model presents higher chances of finding the targeted integer solutions without branching. In our experimentation, optimal solutions are encountered, in less than a minute, for large instances with up to 570000 columns.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11h45 - 12h10

    A general uncapacitated multiple allocation p-hub median problem

    • Jack Brimberg, prés., GERAD, The Royal Military College of Canada
    • Nenad Mladenovic, Mathematical Institute SANU
    • Raca Todosijevic, LAMIH, Université de Valenciennes et du Hainaut- Cambrésis
    • Dragan Urosevic, Mathematical Institute SANU

    The uncapacitated multiple allocation p-hub median problem assumes that the triangle inequality applies on the edges of a complete graph. Hence the flow between any pair of nodes requires at most two hubs for the transfer process. Here we relax the triangle inequality restriction and present two new formulations that allow transfer through up to q hubs where q ≤ p is a given parameter. Some heuristic solution approaches are proposed and preliminary computational results given.