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

Artur Pessoa 1 Ruslan Sadykov 1 Eduardo Uchoa 2 François Vanderbeck 1
1 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [64 references]  Display  Hide  Download

https://hal.inria.fr/hal-01958155
Contributor : Ruslan Sadykov <>
Submitted on : Monday, December 17, 2018 - 5:19:41 PM
Last modification on : Friday, December 28, 2018 - 1:15:12 AM

Identifiers

  • HAL Id : hal-01958155, version 1

Citation

Artur 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⟩

Share

Metrics

Record views

126

Files downloads

154