A tutorial on Branch-Price-and-Cut algorithms

被引:0
作者
Petris, Matteo [1 ,5 ]
Archetti, Claudia [2 ]
Cattaruzza, Diego [3 ,4 ]
Ogier, Maxime [4 ]
Semet, Frederic [4 ]
机构
[1] Univ Lille, Cent Lille, UMR 9189,CRIStAL, Inria,CNRS, F-59000 Lille, France
[2] Univ Brescia, Dept Econ & Management, I-25122 Brescia, Italy
[3] Univ Udine, Dept Math Comp Sci & Phys, Via Sci 206, Udine 33100, Italy
[4] Univ Lille, CNRS, UMR 9189, INRIA,Cent Lille,CRIStAL, F-59000 Lille, France
[5] Inst Polytech Paris, CERMICS, ENPC, Marne La Vallee, France
来源
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH | 2025年 / 23卷 / 01期
关键词
Branch-Price-and-Cut; Column generation; Labelling algorithm; Shortest path with resource; VEHICLE-ROUTING PROBLEM; SHORTEST-PATH PROBLEM; RESOURCE CONSTRAINTS; COLUMN GENERATION; TABU SEARCH; OPTIMIZATION; INEQUALITIES; RELAXATION;
D O I
10.1007/s10288-025-00585-z
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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.
引用
收藏
页码:1 / 52
页数:52
相关论文
共 67 条
[1]  
Achterberg T., 2007, Constraint integer programming
[2]  
[Anonymous], 2005, Column Gener, DOI DOI 10.1007/0-387-25486-21/COVER
[3]  
Applegate D., 1995, FINDING CUTS TSP
[4]   Optimal solutions for routing problems with profits [J].
Archetti, C. ;
Bianchessi, N. ;
Speranza, M. G. .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (4-5) :547-557
[5]   New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem [J].
Baldacci, Roberto ;
Mingozzi, Aristide ;
Roberti, Roberto .
OPERATIONS RESEARCH, 2011, 59 (05) :1269-1283
[6]   Branch-and-price: Column generation for solving huge integer programs [J].
Barnhart, C ;
Johnson, EL ;
Nemhauser, GL ;
Savelsbergh, MWP ;
Vance, PH .
OPERATIONS RESEARCH, 1998, 46 (03) :316-329
[7]   AN ALGORITHM FOR THE RESOURCE CONSTRAINED SHORTEST-PATH PROBLEM [J].
BEASLEY, JE ;
CHRISTOFIDES, N .
NETWORKS, 1989, 19 (04) :379-394
[8]   Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem [J].
Bode, Claudia ;
Irnich, Stefan .
OPERATIONS RESEARCH, 2012, 60 (05) :1167-1182
[9]   Accelerated label setting algorithms for the elementary resource constrained shortest path problem [J].
Boland, N ;
Dethridge, J ;
Dumitrescu, I .
OPERATIONS RESEARCH LETTERS, 2006, 34 (01) :58-68
[10]   An efficient and general approach for the joint order batching and picker routing problem [J].
Briant, Olivier ;
Cambazard, Hadrien ;
Cattaruzza, Diego ;
Catusse, Nicolas ;
Ladier, Anne-Laure ;
Ogier, Maxime .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 285 (02) :497-512