4 présentations

• 
  13h30 - 13h55

  Linear Fractional Approximations for Master Problems in Column Generation

  • Jacques Desrosiers, prés., GERAD, HEC Montréal
  • Jean-Bertrand Gauthier, GERAD - HEC Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Hocine Bouarab, École Polytechnique de Montréal

  In the context of large-scale linear programs solved by a column generation algorithm, we present a primal algorithm for handling the master problem. Successive approximations of the latter are created to converge to optimality. The main properties are that, for every approximation except the last one, the cost of the solution decreases whereas the sum of the variable values increases. Moreover, the minimum reduced cost of the variables also increases and converges to zero with a super-geometric growth rate.

• 
  13h55 - 14h20

  Stabilization of Column Generation with the Primal-Dual Interior Point Method

  • Jacek Gondzio, prés., University of Edinburgh

  Advantages of interior point methods (IPMs) applied in the context of column generation will be discussed. In particular, IPMs deliver
  a natural stabilization to the column generation process and guarantee its fast convergence, measured with merely a few master iterations needed to localize the solution. New features of the approach such as the use of primal-dual regularization and efficient IPM warm starts will be discussed. Computational experience obtained with the Primal-Dual Column Generation Method (PDCGM) software:
  http://www.maths.ed.ac.uk/~gondzio/software/pdcgm.html
  will be reported. This is a joint work with Pablo Gonzalez-Brevis and Pedro Munari.

• 
  14h20 - 14h45

  Interior point column generation for the dynamic vehicle allocation problem

  • Pedro Munari, prés., Federal University of Sao Carlos (UFSCar)
  • Cesar Cruz, Federal University of Sao Carlos (UFSCar)
  • Reinaldo Morabito, Federal University of São Carlos

  Stabilization is an important issue in column generation (CG), especially for solving large-scale problems. The primal-dual column generation method (PDCGM) is a stabilized CG variant that relies on central dual solutions obtained by the primal-dual interior point algorithm. We apply the PDCGM to the Dynamic Vehicle Allocation Problem, which emerges as a crucial activity in Logistic operations. Computational experiments using real-life data provided by a transportation company that operates in Brazil show that this approach allows us to quickly solve large-scale problems that cannot be solved in practical times by the standard CG neither by a general-purpose MIP solver.

• 
  14h45 - 15h10

  An improved Branch-Cut-and-Price algorithm for the heterogeneous vehicle routing problem

  • Eduardo Uchoa, prés., Universidade Federal Fluminense
  • Artur Pessoa, Universidade Federal Fluminense
  • Ruslan Sadykov, INRIA

  This work proposes a Branch-Cut-and-Price algorithm that adapts for the HVRP several state-of-the-art techniques known to be efficient for homogeneous routing problems : bi-directional ng-path based labeling algorithm to solve the pricing subproblems, generation of limited arc memory rank-1 cuts with up to 5 rows, reduced cost fixing of arc variables, enumeration of elementary routes, automatic dual price smoothing stabilization, and multi-phase strong branching with pseudo-costs. The proposed labeling and fixing algorithms can handle efficiently instances with both discrete and continuous demands. To improve the master problem relaxation, we may additionally generate cuts over a pseudo-polynomial extended formulation. We computationally show that these cuts, even in the presence of rank-1 cuts, are important for solving difficult instances of the problem. Other contributions include pricing subproblem dependent memory for rank-1 cuts, and the concept of « enumerated mode » for pricing subproblems. The proposed algorithm was tested on standard sets of instances, including multi-depot and site-dependent variants. The dimension of instances that can solved to optimality was doubled in comparison with the state-of-the-art algorithm by Baldacci and Mingozzi (2009). Several best-known solutions were improved.