Beyond Vehicle Routing: a general purpose branch-cut-and-price code for applications where pricing is a resource constrained shortest path (RCSP) Pricing
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | PESSOA, Artur | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | SADYKOV, Ruslan | |
| hal.structure.identifier | Universidade Federal Fluminense [Rio de Janeiro] [UFF] | |
| dc.contributor.author | UCHOA, Eduardo | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | VANDERBECK, François | |
| dc.date.accessioned | 2024-04-04T03:03:03Z | |
| dc.date.available | 2024-04-04T03:03:03Z | |
| dc.date.issued | 2018 | |
| dc.date.conference | 2018-04-11 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193041 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.title.en | Beyond Vehicle Routing: a general purpose branch-cut-and-price code for applications where pricing is a resource constrained shortest path (RCSP) Pricing | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | ISCO 2018 - 5th International Symposium on Combinatorial Optimization | |
| bordeaux.country | MA | |
| bordeaux.conference.city | Marrakesh | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-01958155 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2018-04-13 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-01958155v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.date=2018&rft.au=PESSOA,%20Artur&SADYKOV,%20Ruslan&UCHOA,%20Eduardo&VANDERBECK,%20Fran%C3%A7ois&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||