Branch-and-Price

This open access book is a unique resource in computational mathematical optimization. It conveys the entire spectrum from the basic theory to the most advanced tricks in reformulations and decomposition approaches to solving mixed-integer linear programs. The book has useful and partly previously unpublished facts for students, teachers, and practitioners alike. The content covers algorithmic ideas like column generation, cutting planes, and branch-and-price, reformulation techniques like Dantzig-Wolfe decomposition and Lagrangian relaxation, the very important application domains of vehicle routing and crew scheduling, and has some practical advice when it comes to an implementation. Many notes and even more didactic illustrations and examples bring the theory to life, complemented by almost 140 exercises, including solutions. As a side effect, readers learn ways how to formulate integer programming models for a great variety of combinatorial optimization problems. The material draws from more than 400 references and the four authors' own decades of experience in the field. Several photos taken by the authors bring a personal touch to the writing, among other tiny anecdotal elements that the connoisseur will appreciate. The book is not, and cannot be encyclopedic, but it has the ambition to be the standard text and main reference in the field for the years to come.

Students, researchers, and practitioners aiming to solve large, complex discrete and combinatorial optimization problemswhether in industry, science, or technologywill find this book essential for exploring optimal and near-optimal solutions through decomposition methods and column generation.

This book is open access, which means that you have free and unlimited access Contains numerous notes, didactic illustrations, and examples, complemented by nearly 140 exercises with solutions Offers a comprehensive range from fundamental theory to advanced reformulations and decomposition Provides valuable insights and fresh information for students, educators, and professionals

Autorentext

Jacques Desrosiers obtained from Université de Montréal a bachelor's degree in mathematics in 1973, a master's degree in statistics in 1974, and a PhD (specialized in transportation) in 1979. From 1978 to 2024, he is a professor in the Department of Management Sciences at HEC Montréal. In 1993, he became partner in AD OPT Technologies which commercializes the Altitude software system for the management of air transport operations. This product line is powered by GENCOL, a state-of-the-art column generation solver developed at GERAD. The research, publications, and transfers carried out by Jacques during his career have been rewarded several times, notably in 1997 by the Prix d'Excellence en Partenariat Innovateur with his friend François Soumis, awarded jointly by the Natural Sciences and Engineering Research Council of Canada and the Conference Board of Canada. This Synergy Award for Innovation recognizes outstanding research and development partnerships between academia and industry.

Marco Lübbecke is a full professor and chair of operations research at RWTH Aachen University, Germany. He received his Ph.D. in applied mathematics from TU Braunschweig in 2001 and held positions as assistant professor for combinatorial optimization and graph algorithms at TU Berlin and as visiting professor for discrete optimization at TU Darmstadt. Marco's research and teaching interests are in computational integer programming and discrete optimization, covering the entire spectrum from fundamental research and methods development to industry scale applications. A particular focus of his work is on decomposition approaches to exactly solving large-scale real-world optimization problems. This touches on mathematics, computer science, business, and engineering alike and rings with his appreciation for fascinating interdisciplinary challenges.

Guy Desaulniers received his PhD in mathematics from Polytechnique Montreal, where he has been a professor in the department of Mathematics and Industrial Engineering since 2000. Between 2015 and 2019, he was the director of the GERAD research center. He has supervised more than 80 graduate students, co-authored more than 140 papers. His main research interests are in the areas of large-scale optimization (in particular, column generation/branch-and-price), integer programming, combinatorial optimization, and constrained shortest path problems with applications to vehicle routing and crew scheduling in ground, air, rail, and maritime transportation, as well as personnel scheduling. Since 2019, he is also a scientific advisor at IvadoLabs which delivers practical artificial intelligence/operations research solutions to industrial partners.

Jean Bertrand Gauthier obtained his PhD at HEC Montreal, Canada. He was awarded a few gratifying prizes during his studies notably the best master's thesis as well as the best doctoral dissertation in their respective years of submission. He worked on core aspects of the primal simplex algorithm and researched routing problems in exact and heuristic contexts. He worked at Fraunhofer ITWM where software development principally combines under-the-hood optimization with polished user interfaces tailored to industrial client needs.

Inhalt

Linear and Integer Linear Programming.- Column Generation.- Dantzig-Wolfe Decomposition for Linear Programming.- Dantzig-Wolfe Decomposition for Integer Linear Programming.- Vehicle Routing and Crew Scheduling Problems.- Dual Point of View.- Branch-Price-and-Cut.- Conclusion.