Branch-Price-and-Cut
Abstract
Abstract Our aim from the very beginning is to solve an integer linear program. Yet, all that we have algorithmically accomplished so far is to solve the linear relaxation of a Dantzig-Wolfe reformulation. When the solution is fractional, we need to cut it, or branch. From a bird’s eye view, all that remains to do is to use the column generation algorithm to solve the relaxation, and possibly strengthen it by additional valid inequalities, in every node of the branch-and-bound tree. Zooming in, we see that some subtleties have to be respected or can even be exploited.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Optimization Algorithms Research
Vehicle Routing Optimization Methods
Publication details
- Journal / source
- Springer eBooks
- Pages
- 443–543
- Publication date
- 1 January 2026
- Language
- EN
- Document type
- Book chapter