, , et

référence BibTeX

Integer (linear) programs are a standard way of formalizing a vast array of optimization problems in industry, services, management, science, and technology. By the logic of the underlying business problem, such models are often composed of independent building blocks that are kept together by, e.g., spatial, temporal, or financial constraints. Over the years, Branch-and-Price, i.e., column generation applied in every node of a search tree, became a, likely the standard approach to solving such structured integer programs. The charm of the method lies in its ability to leverage algorithms for the building blocks by way of decomposition. Hundreds and hundreds of papers have been written on successful applications in logistics, transportation, production, energy, health care, education, politics, sports, etc. Besides collecting and unifying the literature, the authors wanted to share their experience with the subject.

They expect the reader to have modeling experience with network, linear and integer linear programs. Essentials are presented in Chapter 1 (Linear and Integer Linear Programming). Column Generation is an algorithm for solving large scale linear programs: as such, there is the dedicated Chapter 2 in which we see the similarities and differences with the primal simplex algorithm. The Dantzig-Wolfe decomposition is, in fact, a reformulation method: Chapter 3 presents the classical way for linear programs; this is based on the convexification approach of a sub-domain. Chapter 4 goes further, adapting it to integer linear programs, and also presenting the reformulation based on the discretization approach. Chapter 5 (Vehicle Routing and Crew Scheduling Problems) follows and gives access to important applications. Chapter 6 explores the Dual Point of View: it notably presents another decomposition method, the Lagrangian relaxation approach. We see its relationships with the Dantzig-Wolfe reformulation. A better understanding of duality leads to stabilization approaches. Chapter 7 (Branch-Price-and-Cut) presents how to handle various branching and cutting decisions to get integer solutions, indeed, to solving the original model. The final chapter, Conclusion, is where the authors stop after several years of understanding, writing, classifying, etc. They tell the story of Montréal’s GENCOL group since the early 80s and list some possible writing subjects for interested people. The book comprises a set of exercises in every chapter and the authors give all the answers but two. Sometimes, these exercises provide new theory.

, 689 pages

Axe de recherche

Applications de recherche


G2436-2.pdf (17 Mo)