4 présentations

• 
  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.

• 
  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.

• 
  11h20 - 11h45

  An improved model for the integral simplex using decomposition algorithm

  • Abdelouahab Zaghrouti, prés., GERAD - Polytechnique Montréal
  • Francois Soumis, GERAD et Polytechnique
  • 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.

• 
  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.