Beyond Vehicle Routing: a general purpose branch-cut-and-price code for applications where pricing is a resource constrained shortest path (RCSP) Pricing - Archive ouverte HAL Access content directly
Conference Papers Year : 2018

Beyond Vehicle Routing: a general purpose branch-cut-and-price code for applications where pricing is a resource constrained shortest path (RCSP) Pricing

(1) , (1) , (2) , (1)
1
2

Abstract

Column generation algorithms where the pricing is solved as a resource constrained shortest path problem have been used in a variety of applications, as surveyed in [5]. Pioneering work on a generic solver using column generation based on a resource constrained shortest path subproblem was the GenCol software [13]. Our aim is to develop such a platform that includes both generic modeling tools and an highly efficient branch-cut-and-price. Our solver relies on generalizing the most advanced techniques that were recently developed for classical variants of the vehicle routing problem. It considers several resource constraints simultaneously , even allowing for continuous resources (as opposed to the discrete assumptions made by traditional dynamic programming approaches), sometimes even allowing zero or negative resource consumptions. The pricing is done by a bi-directional labeling algorithm, implemented over the so-called bucket graph (as proposed in [11]). Besides the good performance of the pricing oracle, the overall efficiency of the branch-cut-and-price relies on advanced features such as a procedure for fixing arc variables by reduced costs [4,8]; an algorithm for gradually enforcing total or partial elementarity of subproblem solution paths [10]; an self-adjusting dual price smoothing stabilization for improving the convergence of the column generation [7]; a heuristic local search separation procedure for limited-memory rank-1 Chvatal-Gomory cuts [6]; a labeling dynamic programming algorithm for enumerating elementary subproblem solution paths [1]; a multi-phase pseudo-costs based strong branching procedure [6]; and the generic diving heuristic for improving the initial primal bound of [12]. In this presentation we will focus on the scope of applications that are amenable to our branch-cut-and-price solver. The goal is to convey the ease of access to an efficient solver for the many combinatorial optimization problems that can be decomposed into resource constrained shortest path subproblems, once linking constraints have been dualized in a Lagrangian way. Beyond the case of vehicle routing problems (VRP) for which the solver was originally developed, we will focus on problems where the VRP-like structure is not evident, including machine scheduling, packing, resource allocation, and network design problems [8,2,9,3]. After showing how such problems reduce to our approach, we evaluate how it performs in practice when compared to the best existing approaches.
Fichier principal
Vignette du fichier
Sadykov_genBCP_slides.pdf (258.17 Ko) Télécharger le fichier
Vignette du fichier
isco2018.pdf (124.66 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01958155 , version 1 (17-12-2018)

Identifiers

  • HAL Id : hal-01958155 , version 1

Cite

Artur Alves Pessoa, Ruslan Sadykov, Eduardo Uchoa, François Vanderbeck. Beyond Vehicle Routing: a general purpose branch-cut-and-price code for applications where pricing is a resource constrained shortest path (RCSP) Pricing. ISCO 2018 - 5th International Symposium on Combinatorial Optimization, Apr 2018, Marrakesh, Morocco. ⟨hal-01958155⟩
166 View
176 Download

Share

Gmail Facebook Twitter LinkedIn More