2016 Optimization Days

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

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

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

May 3, 2016 10:30 AM – 12:10 PM

Location: EY

Chaired by Frédéric Quesnel

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:30 AM - 10:55 AM

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

    • Diego Pecin, presenter, 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
    10:55 AM - 11:20 AM

    I2SUD: An improved integral simplex using decomposition algorithm

    • Omar Foutlane, presenter, 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
    11:20 AM - 11:45 AM

    An improved model for the integral simplex using decomposition algorithm

    • Abdelouahab Zaghrouti, presenter, 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
    11:45 AM - 12:10 PM

    A general uncapacitated multiple allocation p-hub median problem

    • Jack Brimberg, presenter, 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.