Scholarlink

<p>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 <i>Elementary Shortest Path Problem with Resource Constraints</i>. 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 <i>Capacitated Vehicle Routing Problem</i>, which is a well-known problem belonging to the class we consider.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A tutorial on Branch-Price-and-Cut algorithms

  • 期刊论文

  • 发表日期：

    2025年3月14日

查看全文
  • Matteo Petris,
  • Claudia Archetti,
  • Diego Cattaruzza,
  • Maxime Ogier,
  • Frédéric Semet

摘要

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.