A tutorial on Branch-Price-and-Cut algorithms

Matteo Petris (), Claudia Archetti (), Diego Cattaruzza (), Maxime Ogier () and Frédéric Semet ()
Additional contact information
Matteo Petris: Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL
Claudia Archetti: University of Brescia
Diego Cattaruzza: University of Udine
Maxime Ogier: Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRIStAL
Frédéric Semet: Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRIStAL

4OR, 2025, vol. 23, issue 1, No 1, 52 pages

Abstract: Abstract This paper provides a tutorial on Branch-Price-and-Cut (BPC) algorithms for a generic class of problems whose objective is to find a set of feasible paths in a graph while optimising a given objective function. The tutorial is split into two main parts. First, we describe the building blocks of a BPC algorithm: the Branch-and-Bound algorithm, the column generation procedure and the Branch-and-Cut algorithm. Then, we focus on the description of a BPC algorithm for the class of problems we consider. Precisely, we present the classical and advanced techniques that should be embedded in an efficient algorithm. Particular attention is devoted to the solution of the pricing problem in the case where it is formulated as an Elementary Shortest Path Problem with Resource Constraints. The aim of the tutorial is pedagogical. Hence, its intended reader is someone facing the first implementation of a BPC algorithm. Implementation tips and examples accompany the techniques and concepts to ease their comprehension. Precisely, the examples are based on the Capacitated Vehicle Routing Problem, which is a well-known problem belonging to the class we consider.

Keywords: Branch-Price-and-Cut; Column generation; Labelling algorithm; Shortest path with resource; 90-01; 90C06 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-025-00585-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:23:y:2025:i:1:d:10.1007_s10288-025-00585-z

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-025-00585-z

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().